Codeforces Round #649 (Div. 2)。

A. XXXXX

        求出模$x$的前缀和，然后对于一个下标$i$，找出满足$j < i$并且两个前缀和不同的$j$，从中找出最大长度。

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
#include <bits/stdc++.h>
using namespace std;
int n, x, op[100005], sum[100005], fk[100005];
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &x);
        for (int i = 1; i <= n; i++) {
            scanf("%d", op + i);
            sum[i] = (sum[i - 1] + op[i]) % x;
        }
        for (int i = 0; i < x; i++) fk[i] = -1;
        int ans = 0;
        for (int i = 0; i <= n; i++) {
            if (fk[sum[i]] == i - 1) fk[sum[i]] = i;
        }
        for (int i = 1; i <= n; i++) {
            ans = max(ans, i - (fk[sum[i]] + 1));
        }
        if (ans == 0) {
            printf("-1\n");
        } else {
            printf("%d\n", ans);
        }
    }
    return 0;
}

B. Most socially-distanced subsequence

        显然可以发现只有数拐弯（增减状态改变）时需要加入答案。

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
#include <bits/stdc++.h>
using namespace std;
int n, p[100005], sta[100005], ct = 0;
vector<int> vec;
inline void push(int x)
{
    if (ct <= 1) {
        sta[ct++] = x;
        return;
    }
    if ((x - sta[ct - 1] > 0 && sta[ct - 1] - sta[ct - 2] > 0) || x - sta[ct - 1] < 0 && sta[ct - 1] - sta[ct - 2] < 0) {
        sta[ct++] = x;
    } else {
        if (vec.empty() || vec.back() != sta[0]) vec.push_back(sta[0]);
        if (vec.empty() || vec.back() != sta[ct - 1]) vec.push_back(sta[ct - 1]);
        sta[0] = sta[ct - 1];
        sta[1] = x;
        ct = 2;
    }
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n), ct = 0, vec.clear();
        for (int i = 1; i <= n; i++) scanf("%d", p + i);
        for (int i = 1; i <= n; i++) {
            push(p[i]);
        }
        if (vec.empty() || vec.back() != sta[0]) vec.push_back(sta[0]);
        if (vec.empty() || vec.back() != sta[ct - 1]) vec.push_back(sta[ct - 1]);
        printf("%d\n", vec.size());
        for (int i : vec) printf("%d ", i);
        printf("\n");
    }
    return 0;
}

C. Ehab and Prefix MEXs

        可怕的构造题。
        可以发现$a_{i-1} < a_{i}$时，$b_i$只能是$a_{i-1}$，其余情况下$b_{i}$是$a_i$到$a_n$中最小的没有出现过的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int a[100005], n, b[100005], vis[100005];
int main()
{
    scanf("%d", &n), memset(b, -1, sizeof(b));
    for (int i = 1; i <= n; i++) scanf("%d", a + i), vis[a[i]] = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] != a[i - 1]) b[i] = a[i - 1];
    }
    int num = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i] != -1) continue;
        while (num < a[i] || vis[num]) ++num;
        b[i] = num++;
    }
    for (int i = 1; i <= n; i++) printf("%d ", b[i]);
    return 0;
}

D. Ehab’s Last Corollary

        当给的图是一个树时，直接黑白染色，找出一些点来即可，从而解决问题一。
        若给的图不是树，那么它必然有环。考察一个合法环的长度，若其大于$k$，则其中的点必然可以隔项取出，解决问题一，否则这个环可以直接解决问题二。这里说一下什么环是合法的，如果一个环内任意两个不相邻的点都没有多余的边连接它们，就是合法的。
        使用一遍$DFS$可以在$O(n)$复杂度内找到一个合法的环。在$DFS$时，我们只保留最小的那一个环，可以证明这个环必然是合法的。

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
#include <bits/stdc++.h>
#define N 100005
using namespace std;
struct Edge
{
    int next, to;
} edge[N << 2];
int head[N], cnt = 1, n, m, k, vis[N], dep[N], fa[N], minn;
vector<int> ans[2];
inline void add(int x, int y)
{
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}
void DFS_tr(int x, int t)
{
    ans[t].push_back(x);
    for (int i = head[x]; i; i = edge[i].next) {
        if (vis[edge[i].to]) continue;
        vis[edge[i].to] = 1, DFS_tr(edge[i].to, t ^ 1);
    }
}
void DFS(int x, int f)
{
    for (int i = head[x]; i; i = edge[i].next) {
        if (edge[i].to == f) continue;
        if (!vis[edge[i].to]) {
            vis[edge[i].to] = 1, dep[edge[i].to] = dep[x] + 1, fa[edge[i].to] = x, DFS(edge[i].to, x);
        } else if (dep[x] - dep[edge[i].to] > 1) {
            int huan = dep[x] - dep[edge[i].to] + 1, t;
            if (huan < minn) {
                minn = huan, ans[0].clear(), t = x;
                while (t != edge[i].to) ans[0].push_back(t), t = fa[t];
                ans[0].push_back(edge[i].to);
            }
        }
    }
}
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, x, y; i <= m; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
    if (m == n - 1) {
        printf("1\n");
        vis[1] = 1, DFS_tr(1, 0);
        if (ans[0].size() * 2 >= k) {
            for (int i = 0; i < (k % 2 == 0 ? k / 2 : k / 2 + 1); i++) printf("%d ", ans[0][i]);
        } else {
            for (int i = 0; i < (k % 2 == 0 ? k / 2 : k / 2 + 1); i++) printf("%d ", ans[1][i]);
        }
        return 0;
    }
    minn = n + 1, dep[1] = 1, vis[1] = 1, DFS(1, 0);
    if (minn <= k) {
        printf("2\n%d\n", ans[0].size());
        for (int i : ans[0]) printf("%d ", i);
    } else {
        printf("1\n");
        for (int i = 0; i < (k % 2 == 0 ? k / 2 : k / 2 + 1); i++) printf("%d ", ans[0][i << 1]);
    }
    return 0;
}

E. X-OR

        如果我们能定位零的位置，这个问题就很好解决。
        考虑两个候选的位置$a$和$b$，查询出两者的按位或$ab$，对于第三个位置$c$，查询$bc$，有以下几种情况：

  • 若$ab>bc$，则$a$必然不是$0$，将$a$换成$c$。
  • 若$ab<bc$，则$c$必然不是$0$。
  • 若$ab=bc$，则$b$必然不是$0$，将$b$换成$c$，但是此时需要多查询$ac$的值。

        对查询的位置顺序进行随机排列，可以发现上面第三种情况的期望次数很小，即额外查询次数很小。通过这种方法就能定位$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
#include <bits/stdc++.h>
using namespace std;
int n, op[1 << 12], ans[1 << 12];
inline int query(int x, int y)
{
    printf("? %d %d\n", x, y);
    fflush(stdout);
    scanf("%d", &x);
    if (x == -1) exit(0);
    return x;
}
int main()
{
    srand(time(0));
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) op[i] = i;
    random_shuffle(op + 1, op + n + 1);
    int a = op[1], b = op[2], ab = query(a, b);
    for (int i = 3; i <= n; i++) {
        int c = op[i];
        int bc = query(b, c);
        if (ab > bc)
            a = c, ab = bc;
        else if (ab == bc)
            b = c, ab = query(a, c);
    }
    int zero;
    for (int i = 1; i <= n; i++) {
        if (op[i] != a && op[i] != b) {
            int aa = query(a, op[i]);
            int bb = query(b, op[i]);
            if (aa != bb) {
                if (aa > bb)
                    zero = b;
                else
                    zero = a;
                break;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (i != zero) ans[i] = query(zero, i);
    }
    printf("! ");
    for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
    fflush(stdout);
    return 0;
}