abc368题解

A

先输出后面的再输出前面的就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
signed main() {
    IOS;
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = n - m; i < n + n - m; i++)
    {
        cout << v[i % n] << ' ';
    }
    cout << endl;

    return 0;
}

B

数据范围很小,直接选一次排序一次就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
signed main() {
    IOS;
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    for (int i = 0; i < 10000000; i++) {
        sort(v.begin(), v.end(), greater<int>());
        if (v[0] && v[1]) {
            v[0]--;
            v[1]--;
        } else {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

C

注意三次一个循环,再写一个单独操作的次数,就可以线性实现,二分似乎也可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
signed main() {
    IOS;
    int n;
    cin >> n;
    vector<int> v(n);
    int res = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int t = x / 5;
        x -= t * 5;
        res += t * 3;
        while(x > 0) {
            res++;
            if (res % 3 == 0) {
                x -= 3;
            } else {
                x--;
            }
        }
    }
    cout << res << endl;
    return 0;
}

D

最简单的方法是找每一条边两边是不是都存在制定节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#define MAX 200005
int a[MAX], siz[MAX];
vector<int> G[MAX];
int n, m;
ll ans = 0;
void dfs(int u, int fa)
{
    if (a[u])
    {
        siz[u] = 1;
    }
    for (int v : G[u])
    {
        if (v == fa)
        {
            continue;
        }
        dfs(v, u);
        siz[u] += siz[v];
    }
}
void dfs1(int u, int fa)
{
    // cout << u << ' ' << siz[u] << endl;
    for (int v : G[u])
    {
        if (v == fa)
        {
            continue;
        }
        // cout << v << endl;
        dfs1(v, u);
        if (siz[v] && (siz[1] - siz[v]))
        {
            //cout << u << ' ' << v << endl;
            ans++;
        }
    }
}
signed main()
{
    IOS;
    cin >> n >> m;
    for (int i = 0; i < n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        a[x]++;
    }
    // cout << a[5] << endl;
    dfs(1, -1);
    dfs1(1, -1);
    cout << ans + 1 << endl;
    return 0;
}