Codeforces Round #648 (Div. 2)。

A. Matrix Game

        我们把没有$1$的行给数出来，假设为$a$，然后把没有$1$的列数出来，假设为$b$。每一次操作必然会导致$a$和$b$同时减去一，当其中一个减到零时，对方输。于是考察$\min(a,b)$的奇偶性，当为奇数时，先手必胜，否则必输。

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;
int m, c[51], r[51];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d%d", &n, &m);
        memset(c, 0, sizeof(c));
        memset(r, 0, sizeof(r));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int x;
                scanf("%d", &x);
                if (x == 1) c[j] = 1, r[i] = 1;
            }
        }
        int ans = 0x3f3f3f3f, s = 0;
        for (int i = 1; i <= n; i++) s += r[i] == 0;
        ans = min(ans, s);
        s = 0;
        for (int i = 1; i <= m; i++) s += c[i] == 0;
        ans = min(ans, s);
        if (ans & 1) {
            printf("Ashish\n");
        } else {
            printf("Vivek\n");
        }
    }
    return 0;
}

B. Trouble Sort

        当序列中同时存在两个种类的数时，其中的数必然是可以两两交换的。于是如果其中存在两个种类的数，则一定是$yes$，否则需要特判该序列是否已经有序。

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
#include <bits/stdc++.h>
using namespace std;
int a[100005], n;
inline int ok()
{
    for (int i = 2; i <= n; i++) {
        if (a[i] < a[i - 1]) return 0;
    }
    return 1;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int na = 0, nb = 0;
        scanf("%d", &n);
        for (int i = 1, x; i <= n; i++) scanf("%d", a + i);
        for (int i = 1, x; i <= n; i++) {
            scanf("%d", &x);
            if (x == 0)
                ++na;
            else
                ++nb;
        }
        if (na == 0 || nb == 0) {
            if (!ok())
                printf("No\n");
            else
                printf("Yes\n");
        } else {
            printf("Yes\n");
        }
    }
    return 0;
}

C. Rotation Matching

        枚举每一个数字，统计移动到哪些地方时可以使它匹配，然后在所有位置中找一个可以满足最多数字的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int a[200005], b[200005], n, num[200005];
int main()
{
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), a[x] = i;
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), b[x] = i;
    for (int i = 1; i <= n; i++) {
        if (b[i] > a[i])
            ++num[b[i] - a[i] + 1];
        else if (b[i] < a[i])
            ++num[n - (a[i] - b[i]) + 1];
        else
            ++num[1];
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, num[i]);
    printf("%d", ans);
    return 0;
}

D. Solve The Maze

        从$B$开始$BFS$，将其$BFS$第一次遇到的路都给改成墙，这样可以保证$B$一定逃不出去，然后再判断$G$能不能都逃出去。
        这种方法的正确性在于$BFS$能够保证其不会堵住任何不必要的路。如果堵住的路本来就不会阻挡$G$的逃出，则忽略，若阻挡了$G$的逃出，则说明至少一个$B$和至少一个$G$的逃出的必经路有重叠，并且由于$BFS$的特性，这个公共的必经点是离$B$最近的，此时堵住一个更远的一定不会使答案更优，于是此时无解。从而保证了答案的正确性。

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
#include <bits/stdc++.h>
#define ID(x, y) ((x - 1) * m + y)
using namespace std;
int n, m, vis[60][60], fa[3000];
char op[60][60];
queue<pair<int, int>> que;
const int X[] = {0, 1, 0, -1}, Y[] = {1, 0, -1, 0};
int ff(int x)
{
    return fa[x] == x ? x : fa[x] = ff(fa[x]);
}
inline void merge(int x, int y)
{
    if (ff(x) == ff(y)) return;
    int f1 = ff(x), f2 = ff(y);
    fa[f1] = f2;
}
int main()
{
    // DEBUG;
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%s", op[i] + 1);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                vis[i][j] = 0, fa[ID(i, j)] = ID(i, j);
                if (op[i][j] == 'B') que.push(make_pair(i, j)), vis[i][j] = 1;
            }
        }
        while (!que.empty()) {
            pair<int, int> pp = que.front();
            que.pop();
            for (int i = 0; i < 4; i++) {
                int x = pp.first + X[i], y = pp.second + Y[i];
                if (x < 1 || x > n || y < 1 || y > m || op[x][y] == '#' || vis[x][y]) continue;
                if (op[x][y] == '.')
                    op[x][y] = '#';
                else {
                    vis[x][y] = 1;
                    que.push(make_pair(x, y));
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (op[i][j] == '#') continue;
                for (int z = 0; z < 4; z++) {
                    int x = i + X[z], y = j + Y[z];
                    if (x < 1 || x > n || y < 1 || y > m || op[x][y] == '#') continue;
                    merge(ID(x, y), ID(i, j));
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (op[i][j] == 'G') {
                    if (ff(ID(i, j)) != ff(ID(n, m))) {
                        printf("No\n");
                        goto to;
                    }
                }
            }
        }
        printf("Yes\n");
    to:;
    }
    return 0;
}

E. Maximum Subsequence Value

        出的很妙的一道题。
        考虑三个数，答案必然就是它们的按位或。如果加入更多的数，对于原有答案中原本不存在的一个二进制位$i$，即使后来加入的所有数都有该位，但是由于起初的三个数没有，答案也不会计入，这说明加入更多的数不会使答案更优。
        于是正解为枚举三个数，取最大的按位或。

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;
long long op[501];
int main()
{
    scanf("%d", &n);
    long long ans = 0;
    for (int i = 1; i <= n; i++) scanf("%lld", op + i);
    if (n == 1) {
        printf("%lld", op[1]);
    } else if (n == 2) {
        printf("%lld", op[1] | op[2]);
    } else {
        for (int a = 1; a <= n; a++) {
            for (int b = a + 1; b <= n; b++) {
                for (int c = b + 1; c <= n; c++) ans = max(ans, op[a] | op[b] | op[c]);
            }
        }
        printf("%lld", ans);
    }
    return 0;
}

F. Swaps Again

        经过证明，可以发现题目中给定的操作等价于进行若干次操作，每次操作是下面两个操作中的一个：

  • 交换$a_i$和$a_{n-i+1}$，$1\leq i\leq n$
  • 同时交换$a_i,a_j$以及$a_{n-i+1},a_{n-j+1}$，$1\leq i<j\leq \lfloor\frac {n}{2}\rfloor$

        这样说明$(a_i,a_{n-i+1})$是一个整体，它们可以重组。这样我们只需要找出$b$对应的配对，然后用$a$去匹配它，验证匹配的可行性即可。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 505 + 5;
typedef long long ll;
int a[N], b[N], n;
multiset<pair<int, int>> ssp;
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        for (int i = 1; i <= n; i++) scanf("%d", b + i);
        if (n & 1) {
            if (a[(n + 1) >> 1] != b[(n + 1) >> 1]) {
                printf("No\n");
                continue;
            }
        }
        ssp.clear();
        for (int i = 1, j = n; i < j; i++, --j) ssp.insert(make_pair(a[i], a[j]));
        for (int i = 1, j = n; i < j; i++, --j) {
            if (ssp.count(make_pair(b[i], b[j]))) {
                ssp.erase(ssp.find(make_pair(b[i], b[j])));
            } else if (ssp.count(make_pair(b[j], b[i]))) {
                ssp.erase(ssp.find(make_pair(b[j], b[i])));
            } else {
                printf("No\n");
                goto to;
            }
        }
        printf("Yes\n");
    to:;
    }
    return 0;
}

G. Secure Password

        好题，强烈建议一做。
        首先有一个进行$2logn$次查询的做法。
        我们预处理一个数组$val[i][j]$表示二进制表示中，第$i$位为$j$（$j$取$0/1$）的所有下标对应的数的按位或。这样就可以求出$p_i$。注意到下标互不相同，这意味着一个下标$j$必然存在一个位使得$i$与$j$的二进制表示在这一位不同，这样我们统计$i$的每一位与其不同的数，调出相应的$val$，或起来就是答案。
        再考虑如何在$13$次询问中解决该问题。
        仍然是使用下标的思路，我们对下标重新编号，使得它们的二进制表示中满足以下两个条件：

  • $1$的数量相等
  • $1$出现的位置不存在包含关系

        可以证明这样任何两个下标$i,j$，对于$i$，其必存在一位使得$i$编号在这一位为$1$，而$j$为$0$。这样就可以在$logm$的询问中解决该问题，其中$m$是编号的值域。
        注意到从$13$个数中取$6$个数刚好大于$1000$，这说明我们开$13$个二进制的值域即可，然后为每一个下标分配一个包含恰好$6$个$1$的二进制数，它们必然是互不包含的，这样刚好使用$13$次询问。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 10000 + 5;
typedef long long ll;
ll n, os[1005], op[15], ans[1005];
inline ll query(const vector<int>& vec)
{
    if (vec.empty()) return 0;
    printf("? %d", vec.size());
    for (int i : vec) printf(" %d", i);
    printf("\n");
    fflush(stdout);
    ll x;
    scanf("%lld", &x);
    return x;
}
inline int ok(int x)
{
    int s = 0;
    for (int i = 0; i < 15; i++) s += (x & (1 << i)) >> i;
    return s == 6;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1, x = 0; i <= n; i++) {
        while (!ok(x)) ++x;
        os[i] = x++;
    }
    for (int i = 0; i < 13; i++) {
        vector<int> tmp;
        for (int j = 1; j <= n; j++) {
            if ((os[j] & (1 << i)) == 0) tmp.push_back(j);
        }
        op[i] = query(tmp);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 13; j++) {
            if (os[i] & (1 << j)) ans[i] |= op[j];
        }
    }
    printf("!");
    for (int i = 1; i <= n; i++) printf(" %lld", ans[i]);
    fflush(stdout);
    return 0;
}