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;
}