比赛链接 / 官方题解链接
A. Matrix Game
Solution
Key：每填一个空，可用的行和列同时减一。
有了上述观察，就容易知道判断可用的行与列的最小值的奇偶性即可。
Code
>folded1
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;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
int T, n, m;
int main(){
for(read(T); T; T--){
read(n, m);
set<int> row, col;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
int a; read(a);
if(a) row.insert(i), col.insert(j);
}
}
n = n - row.size(), m = m - col.size();
puts(min(n, m) & 1 ? "Ashish" : "Vivek");
}
return 0;
}
|
B. Trouble Sort
Solution
如果已经有序，输出 Yes；否则，只要存在不同类型的数，就一定可以排好序。
证明：只要存在不同类型的数，那么我们可以借助第三个数对任意两个数进行交换——类似交换两个整数那样。于是可排序。
Code
>folded1
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;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 505;
int T, n, a[N], b[N];
int main(){
for(read(T); T; T--){
read(n);
bool sorted = true;
for(int i = 1; i <= n; i++){
read(a[i]);
if(i > 1 && a[i] < a[i-1])
sorted = false;
}
bool ok = false;
for(int i = 1; i <= n; i++){
read(b[i]);
if(i > 1 && b[i] != b[1]) ok = true;
}
if(sorted) puts("Yes");
else puts(ok ? "Yes" : "No");
}
return 0;
}
|
C. Rotation Matching
Solution
把 $b$ 数组扩倍，用 $a$ 数组去匹配。只需要找到 $a$ 数组中每一个数要匹配到 $b$ 数组的同一个数时需要移动的步数，统计“属于”每种步数的元素个数，取最大即是答案。
Code
>folded1
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;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 200005;
int n, a[N], b[N], pos[N], cnt[N], ans;
int main(){
read(n);
for(int i = 1; i <= n; i++){
read(a[i]);
pos[a[i]] = i;
}
for(int i = 1; i <= n; i++){
read(b[i]);
cnt[(pos[b[i]] - i + n) % n]++;
ans = max(ans, cnt[(pos[b[i]] - i + n) % n]);
}
printf("%d\n", ans);
return 0;
}
|
D. Solve The Maze
Solution
要把 $B$ 困住，就干脆把 $B$ 周围的方块全部置为墙（如果某个方块是 $G$ 就显然是 No），这之后如果从 $(n,m)$ 还能到达所有的 $G$，就可行。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 55;
int n, m, T;
char g[N][N];
bool reach[N][N];
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
void dfs(int x, int y){
reach[x][y] = true;
for(int i = 0; i < 4; i++){
int tx = x + dx[i], ty = y + dy[i];
if(1 <= tx && tx <= n && 1 <= ty && ty <= m &&
g[tx][ty] != '#' && !reach[tx][ty]){
dfs(tx, ty);
}
}
}
int main(){
for(read(T); T; T--){
bool ok = true;
read(n, m);
for(int i = 1; i <= n; i++) scanf("%s", g[i] + 1);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(g[i][j] == 'B'){
if(i > 1 && g[i-1][j] == 'G'){ ok = false; break; }
if(i > 1 && g[i-1][j] == '.') g[i-1][j] = '#';
if(j > 1 && g[i][j-1] == 'G'){ ok = false; break; }
if(j > 1 && g[i][j-1] == '.') g[i][j-1] = '#';
if(i < n && g[i+1][j] == 'G'){ ok = false; break; }
if(i < n && g[i+1][j] == '.') g[i+1][j] = '#';
if(j < m && g[i][j+1] == 'G'){ ok = false; break; }
if(j < m && g[i][j+1] == '.') g[i][j+1] = '#';
}
}
if(!ok) break;
}
if(!ok){ puts("No"); continue; }
memset(reach, 0, sizeof reach);
if(g[n][m] != '#') dfs(n, m);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(g[i][j] == 'G' && !reach[i][j]){
ok = false;
break;
}
}
}
if(!ok) puts("No");
else puts("Yes");
}
return 0;
}
|
E. Maximum Subsequence Value
Solution
对于大小小于 $3$ 的集合，它的值显然是所有数的或；对于大小大于等于 $3$ 的集合，任选出 $3$ 个数，它们的或一定大于等于这个集合的答案。因为假设这个集合的值的第 $i$ 位是 $1$，那么第 $i$ 位最多有 $2$ 个 $0$，于是任选 $3$ 个数，它们的值第 $i$ 位一定是 $1$。
所以 $O(n^3)$ 地枚举即可。
Code
>folded1
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;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 505;
int n;
LL a[N];
int main(){
read(n);
for(int i = 1; i <= n; i++) read(a[i]);
if(n == 1) return printf("%lld\n", a[1]), 0;
if(n == 2) return printf("%lld\n", a[1] | a[2]), 0;
LL ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j < i; j++)
for(int k = 1; k < j; k++)
ans = max(ans, a[i] | a[j] | a[k]);
printf("%lld\n", ans);
return 0;
}
|
F. Swaps Again
Solution
手玩一些数据后可以猜想，只要 $a,b$ 中对称的无序数对相同，那就可行。
Code
>folded1
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
| #include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}
typedef long long LL;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define mp(x, y) make_pair(x, y)
#define pb(x) emplace_back(x)
const int N = 505;
int T, n, a[N], b[N];
int main(){
for(read(T); T; T--){
read(n);
for(int i = 1; i <= n; i++) read(a[i]);
for(int i = 1; i <= n; i++) read(b[i]);
if((n & 1) && a[n/2+1] != b[n/2+1]){ puts("No"); continue; }
multiset<pii> A, B;
for(int i = 1; i <= n / 2; i++){
if(a[i] <= a[n-i+1]) A.insert(mp(a[i], a[n-i+1]));
else A.insert(mp(a[n-i+1], a[i]));
if(b[i] <= b[n-i+1]) B.insert(mp(b[i], b[n-i+1]));
else B.insert(mp(b[n-i+1], b[i]));
}
puts(A == B ? "Yes" : "No");
}
return 0;
}
|
G. Secure Password
留坑……