Codeforces Round #616 (Div. 2)

        Codeforces Round #616 (Div. 2)题解。脑子是个好东西。

A. Even But Not Even

        容易发现删去偶数对数位和的奇偶性没有影响,于是我们删末尾的偶数只剩下一个奇数,然后再删一些其它的奇数调一调即可。不能调就是无解。纯拼手速题。

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;
char op[3005];
int n, t;
int main()
{
scanf("%d", &t);
while (t--) {
scanf("%d%s", &n, op + 1);
int j = 0, last = n;
for (int i = 1; i <= n; i++) {
if ((op[i] - '0') & 1) ++j;
}
while (last >= 1 && op[last] % 2 == 0) --last;
if (last == 0 || j == 1) {
printf("-1\n");
}
else if (j % 2) {
--last;
while (last >= 1 && op[last] % 2 == 0) --last;
for (int i = 1; i <= last; i++) printf("%c", op[i]);
printf("\n");
}
else {
for (int i = 1; i <= last; i++) printf("%c", op[i]);
printf("\n");
}
}
return 0;
}

B. Array Sharpening

        可以发现如果正着能够化成符合题意的形式,那么一定可以化成:0、1、2……这样的形式(暂且称为最小形式)。反过来同理,这样我们只需要比较给定数组与最小形式的关系,然后枚举转折点即可解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
int op[300005], n, l[300005], r[300005];
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", op + i);
l[0] = 1, r[n + 1] = 1;
for (int i = 1; i <= n; i++) l[i] = l[i - 1] && (op[i] >= (i - 1));
for (int i = n; i >= 1; i--) r[i] = r[i + 1] && (op[i] >= (n - i));
for (int i = 1; i <= n; i++) {
if (l[i] && r[i]) {
printf("Yes\n");
goto to;
}
}
printf("No\n");
to:;
}
return 0;
}

C. Mind Control

        一道怡情的贪心。这个肯定是把前面$k$个人蛊惑了比较好。这样会留下我们想要的$n-k$这么大的一块区间。
        但是如果$k+1$到自己之间还有别人,这些人没有办法蛊惑,所以我们可以拿到的数是不确定的,但是可以肯定的是,它们必然是从一个间距固定的数对中取得的,并且取最大的。于是问题转化为求最大值的最小值,枚举即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int n, m, k, op[3600], sv[3600];
int main()
{
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++) scanf("%d", op + i);
int c = min(m - 1, k), len = n - m + 1;
for (int i = 1; i <= n + 1 - len; i++) sv[i] = max(op[i], op[i + len - 1]);
int ans = 0;
for (int i = 1; i <= c + 1; i++) {
int p = 0x3f3f3f3f;
for (int j = i; j + len - 1 <= i + n - c - 1 && j <= n + 1 - len; j++) p = min(p, sv[j]);
ans = max(ans, p);
}
printf("%d\n", ans);
}
// PAUSE;
return 0;
}

D. Irreducible Anagrams

        只需要知道:一个串不存在符合题意的irreducible anagram的充要条件是它满足下面性质的一条:

  • 长度为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
#include <bits/stdc++.h>
using namespace std;
char op[200005];
int sum[200005][30], len;
int main()
{
scanf("%s", op + 1), len = strlen(op + 1);
for (int i = 1; i <= len; i++) {
for (int j = 0; j < 26; j++) sum[i][j] = sum[i - 1][j] + (op[i] - 'a' == j);
}
int q, l, r;
scanf("%d", &q);
while (q--) {
scanf("%d%d", &l, &r);
int cnt = 0;
for (int i = 0; i < 26; i++) {
if (sum[r][i] - sum[l - 1][i] > 0) ++cnt;
}
if (l == r || op[l] != op[r] || cnt >= 3)
printf("Yes\n");
else
printf("No\n");
}
// PAUSE;
return 0;
}

E. Prefix Enlightenment

        这个题出的很好,强烈建议一做。
        任意三个集合交集为空说明任何一个元素最多出现在两个集合中。我们把元素看成边,集合看成点,这样给定的若干集合可以构成一个图。
        对于只出现在一个集合中的元素,我们构造一个假象的集合(成为集合$S_0$),使其包含该元素,进而建图。
        我们给每一个集合一个状态,该状态只能为0和1,表示这个集合选不选。
        容易发现,如果某个元素原本为0,那么必须有恰好一个集合包含它,这样该元素对应边的两个点状态互异。同样地,如果某个元素原本为1,那么该元素对应边的两个点状态相同。如果这个元素没有对应边,那么忽略就好了。
        这样就得到了一些限制条件,问题转化为在给定的连通块状态限制条件下,最小化被选点的数量。这可以用加权并查集优雅地解决。
        定义并查集中的点权为与父节点的关系(1为互异,0为相同),然后上路径压缩更新点权。本题的难点在于并查集合并函数的实现,在合并两个连通块时,要更新连通块大小以及互异的点数,连带着更新答案。
        还有一个坑点:我们构造的$S_0$集合是不可选的,在计算最小答案时,要注意$S_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
#include <bits/stdc++.h>
#define N 300005
using namespace std;
char op[N];
int n, k, fa[N], v[N], num[N], sz[N], ans, gx[N];
vector<int> vec[N];
int ff(int x)
{
if (fa[x] == x) return x;
int f = ff(fa[x]);
v[x] ^= v[fa[x]];
return fa[x] = f;
}
inline void merge(int x, int y, int p)
{
if (ff(x) == ff(y)) return;
int fx = ff(x), fy = ff(y);
if (fx == 0) swap(fx, fy);
v[fx] = p ^ v[x] ^ v[y];
sz[fy] += sz[fx];
num[fy] += v[fx] ? sz[fx] - num[fx] : num[fx];
ans -= gx[fy] + gx[fx];
if (fy == 0)
gx[fy] = num[fy];
else
gx[fy] = min(sz[fy] - num[fy], num[fy]);
ans += gx[fy], fa[fx] = fy;
}
int main()
{
scanf("%d%d%s", &n, &k, op + 1);
for (int i = 0; i <= k; i++) fa[i] = i, sz[i] = 1;
for (int i = 1, c, x; i <= k; i++) {
scanf("%d", &c);
while (c--) scanf("%d", &x), vec[x].push_back(i);
}
for (int i = 1; i <= n; i++) {
if (vec[i].size() == 1) vec[i].push_back(0);
}
for (int i = 1; i <= n; i++) {
if (!vec[i].empty()) merge(vec[i][0], vec[i][1], op[i] == '0');
printf("%d\n", ans);
}
return 0;
}

F. Coffee Varieties

        暂且只说easy版的。
        将$k$减半(如果$k$是1,就不用减了)。这样可以把整个区间划分为$\frac {2n}{k}$块,我们枚举这些块中的每一对,$reset$一次然后遍历,删去那些回答为$Y$的部分。可以证明每一个重复的都会用这种方法被删去。
        一共询问的次数:

        最后数一数哪些没被删即可。

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;
int vis[5000], n, k, p;
char e;
int main()
{
cin >> n >> k;
p = k == 1 ? 1 : k >> 1;
for (int i = 1; i <= n / p; i++) {
for (int j = i + 1; j <= n / p; j++) {
cout << "R" << endl;
for (int z = 1 + (i - 1) * p; z <= i * p; z++) {
cout << "? " << z << endl;
cin >> e;
if (e == 'Y') vis[z] = 1;
}
for (int z = 1 + (j - 1) * p; z <= j * p; z++) {
cout << "? " << z << endl;
cin >> e;
if (e == 'Y') vis[z] = 1;
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (!vis[i]) ++ans;
}
cout << "! " << ans << endl;
// PAUSE;
return 0;
}

0%