Codeforces Round #670 (Div. 2)。

A. Subset Mex

        贪心地选，如果有一个数有两个，就能放在两个集合里，否则只能放在一个里面。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 5;
typedef long long ll;
int num[N];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        memset(num, 0, sizeof(num));
        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &x);
            ++num[x];
        }
        int ans = 0, ss = 0;
        for (int i = 0; i <= 101; i++) {
            if (num[i] == 1 && ss == 0) ans += i, ++ss;
            if (num[i] == 0) {
                if (ss == 0)
                    ans += 2 * i, ss = 2;
                else
                    ans += i, ss = 2;
            }
            if (ss == 2) break;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B. Maximum Product

        分负数的数量为奇数和偶数讨论，然后贪心。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
ll dp[N][6][2], inf = 1ll << 60;
int n, op[N];
vector<int> fs, zs;
inline ll getZs(int x)
{
    ll ans = 1;
    for (int i = (int)zs.size() - 1; i >= zs.size() - x && i >= 0; i--) ans *= zs[i];
    return ans;
}
inline ll getFsMax(int x)
{
    ll ans = 1;
    for (int i = (int)fs.size() - 1; i >= fs.size() - x && i >= 0; i--) ans *= -fs[i];
    return ans;
}
inline ll getFsMin(int x)
{
    ll ans = 1;
    for (int i = 0; i < x && i < fs.size(); i++) ans *= -fs[i];
    return ans;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        fs.clear(), zs.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%d", op + i);
            if (op[i] >= 0)
                zs.push_back(op[i]);
            else
                fs.push_back(-op[i]);
        }
        sort(zs.begin(), zs.end());
        sort(fs.begin(), fs.end());
        ll ans = -inf;
        // cout << fs.size() << " " << zs.size() << endl;
        for (int i = 0; i <= 5; i++) {
            if ((int)fs.size() < i || (int)zs.size() < 5 - i) continue;
            ll tmpans = getZs(5 - i);
            if (i % 2 == 0) {
                tmpans *= getFsMax(i);
            } else {
                tmpans *= getFsMin(i);
            }
            // cout << i << " " << 5 - i << " " << getFsMax(i) << endl;
            ans = max(ans, tmpans);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

        先求出一个重心，然后找到这个重心最重的子树。如果这个子树的重量和其它部分相等，那么就会有至少两个重心，否则只有一个重心，随便删个边，再连回来即可。
        如果有多个重心，就从最重的子树上拿一个叶子，放到重心上，这样就可以削掉重儿子的重量，重心就唯一了。
        也有其它构造方法。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
struct Edge
{
    int next, to;
} edge[N << 1];
int head[N], cnt = 1, n, sz[N], minn = 0x3f3f3f3f, root, flag, yz;
inline void add(int x, int y)
{
    edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
void DFS(int x, int fa)
{
    sz[x] = 1;
    int t = 0;
    for (int i = head[x]; i; i = edge[i].next) {
        if (edge[i].to == fa) continue;
        DFS(edge[i].to, x), sz[x] += sz[edge[i].to];
        t = max(t, sz[edge[i].to]);
    }
    t = max(t, n - sz[x]);
    if (t < minn) minn = t, root = x;
}
void DFS2(int x, int fa)
{
    sz[x] = 1;
    for (int i = head[x]; i; i = edge[i].next) {
        if (edge[i].to == fa) continue;
        DFS2(edge[i].to, x), sz[x] += sz[edge[i].to];
    }
}
void DFS_find(int x, int fa)
{
    if (flag) return;
    if (sz[x] == 1 && flag == 0) {
        flag = 1;
        printf("%d %d\n", x, fa);
        yz = x;
        return;
    }
    for (int i = head[x]; i; i = edge[i].next) {
        if (edge[i].to == fa) continue;
        DFS_find(edge[i].to, x);
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n), cnt = 1, minn = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++) head[i] = sz[i] = 0;
        for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
        DFS(1, 0), DFS2(root, 0);
        int maxSz = 0, at;
        for (int i = head[root]; i; i = edge[i].next) {
            if (sz[edge[i].to] > maxSz) maxSz = sz[edge[i].to], at = edge[i].to;
        }
        // cout << root << " " << maxSz << " " << at << endl;
        if (maxSz < n - maxSz) {
            for (int i = head[1]; i; i = edge[i].next) {
                printf("%d %d\n", 1, edge[i].to);
                printf("%d %d\n", 1, edge[i].to);
                goto tag;
            }
        }
        flag = 0, DFS_find(at, root);
        printf("%d %d\n", yz, root);
 
    tag:;
    }
    return 0;
}

D. Three Sequences

        首先明确，每一次操作不能同时改变$b$和$c$序列，这样一定不优。
        在$a_i$变大时，提高$b$，否则降低$c$才能获得最优解。
        假设一开始$c_1=x$，则$b_1=a_1-x$，那么它需要升的总价值为$K=\sum_{i=2}^n\max(0,a_i-a_{i-1})$。最后的结果就是$\max(x,a_1-x+K)$，明显在$x=\lfloor\frac{a_1+k}{2}\rfloor$时最优。
        然后用差分维护这个值就可以了，复杂度是$O(n+q)$。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
int op[N], n;
ll K = 0, cha[N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", op + i);
    for (int i = 1; i <= n; i++) cha[i] = op[i] - op[i - 1];
    for (int i = 1; i <= n; i++) {
        if (i > 1 && cha[i] > 0) K += cha[i];
    }
    ll x = (cha[1] + K) / 2;
    printf("%lld\n", max(x, cha[1] - x + K));
    int q;
    scanf("%d", &q);
    while (q--) {
        int l, r, x;
        scanf("%d%d%d", &l, &r, &x);
        if (l > 1 && cha[l] > 0) K -= cha[l];
        if (r + 1 <= n && cha[r + 1] > 0) K -= cha[r + 1];
        cha[l] += x, cha[r + 1] -= x;
        if (l > 1 && cha[l] > 0) K += cha[l];
        if (r + 1 <= n && cha[r + 1] > 0) K += cha[r + 1];
        ll xx = (cha[1] + K) / 2;
        printf("%lld\n", max(xx, cha[1] - xx + K));
    }
    return 0;
}

E. Deleting Numbers

        神奇交互题。
        首先升序用$B$询问一遍所有质数，这样可以得到待求数的质因子种类，但是这些质因子中没有最小质因子。
        为了找到最小质因子，我们可以对$m$个质数进行分组，分为$\sqrt m$组。在第一步操作时，每经过一组，查询一次$A1$来考虑最小质因子是否在这个组中，若在，则遍历这个组，找到最小质因子。
        有了所有质因子种类后，只需要确定它们的指数，遍历指数用$B$查询即可。
        查询次数$m+2\sqrt m+log(n)$，时间复杂度$O(nlogn)$。

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
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
int b[N], tot, pr[N], n, ans = 1, num;
vector<int> spr[N];
inline int query(char e, int s)
{
    printf("%c %d\n", e, s), fflush(stdout), scanf("%d", &s);
    return s;
}
inline int sum(int x)
{
    int s = 0;
    for (int i = x; i <= n; i += x) s += b[i] == 0;
    return s;
}
inline void _set(int x)
{
    for (int i = x; i <= n; i += x) {
        if (b[i] == 0) --num;
        b[i] = 1;
    }
}
inline void solve(int x)
{
    int maxn = 1;
    for (ll i = x; i <= n; i *= x) {
        int tmp = query('A', i);
        if (tmp) maxn = max(maxn, (int)i);
    }
    ans *= maxn;
}
int main()
{
    scanf("%d", &n);
    for (int i = 2; i <= 100000; i++) {
        if (b[i]) continue;
        pr[++tot] = i;
        for (int j = 2; 1ll * i * j <= 100000; j++) b[i * j] = 1;
    }
    memset(b, 0, sizeof(b)), num = n;
    int base = sqrt(tot), flag = 1;
    for (int i = 1; i <= tot; i++) spr[i / base].push_back(pr[i]);
    for (int i = 0; i < tot; i++) {
        if (spr[i].empty() || spr[i][0] > n) break;
        for (int a : spr[i]) {
            if (a > n) continue;
            int ps = query('B', a);
            if (ps != sum(a)) solve(a);
            _set(a);
        }
        int tmp = query('A', 1);
        if (tmp != num && flag) {
            flag = 0;
            for (int a : spr[i]) {
                if (a > n) continue;
                tmp = query('A', a);
                if (tmp) {
                    solve(a);
                    break;
                }
            }
        }
    }
    printf("C %d", ans);
    return 0;
}