Codeforces Round #613 (Div. 2)题解。

A . Mezo Playing Zoma

        答案就是$n+1$,没什么说的。

1
2
3
4
5
6
7
8
9
10
#include <bits/stdc++.h>
using namespace std;
char op[100005];
int main()
{
int n;
scanf("%d%s", &n, op);
printf("%d", n + 1);
return 0;
}

B. Just Eat It!

        前缀和二分一下就可以,特判全选的时候。

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
#include <bits/stdc++.h>
using namespace std;
int op[100005], n;
long long sum[100005], minn[100005];
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + op[i], minn[i] = min(minn[i - 1], sum[i]);
long long s = -(1ll << 60), p = 0;
for (int i = 1; i < n; i++) {
s = max(s, sum[i] - minn[i - 1]);
}
for (int i = n; i > 1; i--) {
p += op[i];
s = max(s, p);
}
if (sum[n] > s)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}

C. Fadi and LCM

        很明显,我们要找$a$和$b$使得$ab=x$且$gcd(a,b)=1$,最小化$max(a,b)$。
        这样的话,可以暴力去找。方法是对$x$跑一个$O(\sqrt n)$的质因分解,可以发现这些质因数的种类很少,最大大约有12左右,二进制暴力筛即可。

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
#include <bits/stdc++.h>
using namespace std;
vector<long long> vec;
long long minn = 1ll << 60, a, b, yuan;
void DFS(int at, long long v)
{
if (at == vec.size()) {
long long p = max(v, yuan / v);
if (p < minn) {
minn = p;
a = v, b = yuan / v;
}
return;
}
DFS(at + 1, v * vec[at]);
DFS(at + 1, v);
}
int main()
{
long long x;
scanf("%lld", &x);
yuan = x;
for (int i = 2; 1ll * i * i <= x; i++) {
long long tmp = 1;
while (x % i == 0) x /= i, tmp *= i;
if (tmp != 1) vec.push_back(tmp);
}
if (x != 1) vec.push_back(x);
DFS(0, 1);
printf("%lld %lld", min(a, b), max(a, b));
return 0;
}

D. Dr. Evil Underscores

        可以建一个01 Trie树,在树上进行DFS去找答案。在未出现分叉时,可以保证答案这一位为0,否则只能为1。未分叉时只能走一个方向,否则需要两边都走,然后取最小的那一个答案。

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
#include <bits/stdc++.h>
using namespace std;
int ch[7000005][2], cnt = 1, n, op[100005];
inline void add(int x)
{
int at = 1;
for (int i = 30; i >= 0; i--) {
if (ch[at][(x & (1 << i)) >> i] == 0) ch[at][(x & (1 << i)) >> i] = ++cnt;
at = ch[at][(x & (1 << i)) >> i];
}
}
int get(int x, int p = 30)
{
if (ch[x][0] == 0 && ch[x][1] == 0) return 0;
if (ch[x][0] && ch[x][1]) {
return (1 << p) | min(get(ch[x][0], p - 1), get(ch[x][1], p - 1));
}
else if (ch[x][0])
return get(ch[x][0], p - 1);
else
return get(ch[x][1], p - 1);
}
int main()
{
int ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i), add(op[i]);
printf("%d", get(1));
return 0;
}

E. Delete a Segment

        题意:给$n$个线段,去除其中一个,最小化剩余线段并集元素数量。
        上来想到的一个方法是将所有线段离散化后,将对应区间+1,删线段就是区间-1,用线段树维护非0线段段数。但是线段树虽然可以维护线段的段数,但是不支持修改,这个方法行不通。
        于是逆向思维。考虑删一个线段会引起那些“空洞”把原本连续的线段隔开。容易发现一个空洞会导致最后答案+1,而统计空洞的数量就是统计空洞的线段数,这可以用线段树维护,本题就解决了。
        注意有些空洞对答案不会产生贡献(甚至反贡献),需要对这种情况特判。

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
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#define N 800005
using namespace std;
struct P
{
int l, r, v;
} nd[N << 2];
int n, sv, op[N], x[N], y[N], ans, tot;
map<int, int> mmp;
void build(int l = 1, int r = sv, int k = 1)
{
if (l == r) {
nd[k].l = nd[k].r = nd[k].v = op[l] == 1;
return;
}
int mid = (l + r) >> 1;
build(l, mid, k << 1), build(mid + 1, r, k << 1 | 1);
if (nd[k << 1].r && nd[k << 1 | 1].l) {
nd[k].v = nd[k << 1].v + nd[k << 1 | 1].v - 1;
}
else {
nd[k].v = nd[k << 1].v + nd[k << 1 | 1].v;
}
nd[k].l = nd[k << 1].l, nd[k].r = nd[k << 1 | 1].r;
}
P get(int l, int r, int L = 1, int R = sv, int k = 1)
{
if (L >= l && R <= r) return nd[k];
int mid = (L + R) >> 1;
if (r <= mid)
return get(l, r, L, mid, k << 1);
else if (l > mid)
return get(l, r, mid + 1, R, k << 1 | 1);
P a = get(l, mid, L, mid, k << 1), b = get(mid + 1, r, mid + 1, R, k << 1 | 1), tmp;
if (a.r && b.l)
tmp.v = a.v + b.v - 1;
else
tmp.v = a.v + b.v;
tmp.l = a.l, tmp.r = b.r;
return tmp;
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i);
for (int i = 1, j = 1; i <= n; i++, j += 2) op[j] = x[i], op[j + 1] = y[i];
sort(op + 1, op + 2 * n + 1), mmp.clear(), tot = 0;
sv = unique(op + 1, op + 2 * n + 1) - op - 1;
for (int i = 1; i <= sv; i++) {
if (i == 1)
mmp[op[1]] = 1;
else
mmp[op[i]] = mmp[op[i - 1]] + 2;
}
sv = mmp[op[sv]];
for (int i = 1; i <= n; i++) x[i] = mmp[x[i]], y[i] = mmp[y[i]];
for (int i = 1; i <= sv + 5; i++) op[i] = 0;
for (int i = 1; i <= n; i++) ++op[x[i]], --op[y[i] + 1];
for (int i = 1; i <= sv; i++) op[i] += op[i - 1];
op[sv + 1] = 0, ans = 0;
for (int i = 1; i <= sv + 1; i++) {
if (op[i - 1] && !op[i]) ++tot;
}
build();
for (int i = 1, np; i <= n; i++) {
P s = get(x[i], y[i]);
np = s.v;
if (op[x[i]] == 1 && op[x[i] - 1] == 0) --np;
if (op[y[i]] == 1 && op[y[i] + 1] == 0) --np;
if (np == -1 && s.v == 1) {
ans = max(ans, tot - 1);
}
else {
np = max(np, 0);
ans = max(ans, tot + np);
}
}
printf("%d\n", ans);
}
return 0;
}

F. Classical?

        比较难的数论题。
        首先将所有数的因子集合找出来,计为$S$。
        对于$a\in S$以及$b \in S$,我们证明若$gcd(a,b)=1$,则$ab\leq ans$,这里$ans$就是本题的答案:
        假设$a|x_a$,$b|x_b$,那么$lcm(x_a,x_b)=\frac {x_ax_b}{d}$,这里$d=gcd(x_a,x_b)$。由于$gcd(a,b)=1$,因此可知$ad\leq x_a$并且$bd\leq x_b$,于是$ab\leq \frac {x_ax_b}{d}\leq ans$。
        并且,可以证明满足上面条件的$a$和$b$的乘积$ab$必然可以取到$ans$:
        假设$x_a$与$x_b$的$lcm(x_a,x_b)$最大,若$gcd(x_a,x_b)=d$,则$gcd(x_a,\frac {x_b}{d})=1$,并且$lcm(x_a,\frac {x_b}{d})=lcm(x_a,x_b)=ans$。而$x_a$与$\frac {x_b}{d}$显然在集合$S$中,因此等号一定可以取到。
        这样问题转化成从$S$中找两个互素的数,最大化乘积。
        考虑用栈辅助解决。将因子降序排列,从大到小枚举。当枚举到$x$时,考察当前栈中是否有数与$x$互素,若有,则弹栈,直到栈中没有与$x$互素的数,与此同时更新答案。然后$x$入栈。
        由于后来的数必然比$x$小,它们的乘积不会再比当前的打,因此可以弹栈,将其剔除。
        现在问题是如何判断栈中是否有与$x$互素的数。考虑维护一个$cnt$数组,$cnt[i]$记录当前栈中$i$的倍数的数目。那么这些数中与$x$互素的数的个数就是:

        $\mu(x)$为莫比乌斯函数,证明见后文。
        在弹栈出栈的时候维护一步$cnt$数组,然后用莫比乌斯函数来判断互素,本题就可以解决。

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
#include <bits/stdc++.h>
#define N 100000

using namespace std;
vector<int> vec[N + 5];
int mu[N + 5], pr[N + 5], mk[N + 5], cnt[N + 5], n, tot, ss[N + 5];
long long ans = -(1ll << 60);
stack<int> sta;
inline int get(int to)
{
int as = 0;
for (int s : vec[to]) as += mu[s] * cnt[s];
return as;
}
int main()
{
mu[1] = 1;
for (int i = 2; i <= N; i++) {
if (!mk[i]) pr[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot; j++) {
if (1ll * i * pr[j] > N) break;
mk[i * pr[j]] = 1;
if (i % pr[j] == 0) break;
mu[i * pr[j]] = -mu[i];
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j * j <= i; j++) {
if (i % j == 0) {
vec[i].push_back(j);
if (j * j != i) vec[i].push_back(i / j);
}
}
}
scanf("%d", &n);
for (int i = 1, x; i <= n; i++) scanf("%d", &x), ss[x] = 1, ans = max(ans, 1ll * x);
for (int i = 1; i <= N; i++) {
for (int j = 2; i * j <= N; j++) ss[i] |= ss[i * j];
}
for (int i = N, tp = 0; i >= 1; i--) {
if (!ss[i]) continue;
tp = 0;
while (get(i)) {
tp = sta.top(), sta.pop();
for (int j : vec[tp]) --cnt[j];
}
ans = max(ans, 1ll * tp * i), sta.push(i);
for (int j : vec[i]) ++cnt[j];
}
printf("%lld", ans);
return 0;
}

        关于其中莫比乌斯函数部分的证明:
        互素的数目就是:

        根据莫比乌斯函数的性质:

        枚举$d$:

        就是:

        证毕。