比赛链接：https://atcoder.jp/contests/agc043
A. Range Flip Find Route
题目链接：https://atcoder.jp/contests/agc043/tasks/agc043_a
题目大意：一个 01 矩阵，每次可以选择一个子矩阵翻转，问最少需要多少次操作能够存在一条 $(1,1)$ 到 $(n,m)$ 的全 $1$ 路径。（只能向右向下走）
做法
对于一条固定的路径，可以变成一个序列考虑，发现每次操作最多少一段 $0$ ，因此就是找到一条路径最小化 $0$ 的段数。
时间复杂度：$O(nm)$ 。
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
| #include<bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5;
void get_char_array(char *ss){
static char s[N];
cin >> s;
memcpy(ss + 1, s, sizeof(char) * (strlen(s) + 1));
}
char st[N][N];
int n, m;
int dp[N][N];
bool pd(char x, char y){return x == '#' && y == '.';}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++) get_char_array(st[i]);
dp[1][1] = st[1][1] == '#';
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(i == 1 && j == 1) continue;
int now = 1e9;
if(i > 1) now = min(now, dp[i - 1][j] + pd(st[i][j], st[i - 1][j]));
if(j > 1) now = min(now, dp[i][j - 1] + pd(st[i][j], st[i][j - 1]));
dp[i][j] = now;
}
}
cout << dp[n][m] << "\n";
return 0;
}
|
和官方题解一样。
B. 123 Triangle
题目链接：https://atcoder.jp/contests/agc043/tasks/agc043_b
题目大意：给你一个只包含 $1,2,3$ 的序列，每次操作会将这个序列相邻两个数字相减并取绝对值，得到一个长度 $-1$ 的序列，操作到只剩下一个值，问这个值是多少。
做法
首先答案只能是 $0,1,2$ 。
所以先把初始序列减 $1$ ，这样全局过程中我们都只需要考虑 $0,1,2$ 。
注意到 $\mod 2$ 意义下可以把 $|x-y|$ 变成 $x+y$ ，从而可以直接用组合数算出最终数字的奇偶性。
现在问题是怎么区分 $0/2$ ？
可以归纳证明，只要初始序列中有 $1$ ，最终答案就一定不可能是 $2$ 。
在序列有 $0/2$ 的情况下，显然后面都只有 $0/2$ ，因此在模 $4$ 意义下 $|x-y|=x+y$ ，所以类似上面组合数直接算答案就行了。
当然也可以把所有数字除 $2$ 然后在 $\mod 2$ 的意义下计算，没区别。
时间复杂度：$O(n)$ 。
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
| #include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 5;
void get_char_array(char *ss){
static char s[N];
cin >> s;
memcpy(ss + 1, s, sizeof(char) * (strlen(s) + 1));
}
char st[N];
int n, a[N];
int cnt[N];
int query(int l, int r){return cnt[r] - cnt[l - 1];}
int calc(int x, int y){return (query(1, x) - query(1, y) - query(1, x - y)) ? 0 : 1;}
int main(){
cin >> n;
get_char_array(st);
for(int i = 2; i <= n; i++){
cnt[i] = cnt[i - 1];
int tmp = i;
while(tmp % 2 == 0) tmp /= 2, cnt[i]++;
}
int ans = 0;
int cnt1 = 0;
for(int i = 1; i <= n; i++){
a[i] = st[i] - '1';
ans = (a[i] * calc(n - 1, i - 1) + ans) % 2;
cnt1 += (a[i] == 1);
}
if(ans == 1) cout << 1 << "\n";
else if(cnt1) cout << 0 << "\n";
else{
ans = 0;
for(int i = 1; i <= n; i++){
a[i] = a[i] / 2;
ans = (a[i] * calc(n - 1, i - 1) + ans) % 2;
}
if(ans == 1) cout << 2 << "\n";
else cout << 0 << "\n";
}
return 0;
}
|
和官方题解一样，我麻烦的地方在于判断组合数的奇偶性：
$\binom{n}{m}\equiv [n \& m = m]\mod2$
但比赛时不知道就没办法了，不可能花时间去想这个东西的，直接数 $2$ 的个数花不了什么时间，在比赛中肯定是选择时间更短的方案。
至于这是为什么，我记得组合数取模有一个专门的定理，到时候会专门出一篇博客讲解，这里不再赘述。
C. Giant Graph
单独开了一篇题解。
D. Merge Triplets
题目链接：https://atcoder.jp/contests/agc043/tasks/agc043_d
题目大意：问有多少个 $3N$ 的合法排列，合法排列的定义是：
给 $N$ 个长度为 $3$ 的序列，序列中的数互不相同且都在 $[1,3N]$ 。
$P$ 初始为空，然后每次选择所有序列开头最小的数字，删掉，加入 $P$ 中，最后得到的 $P$ 称为合法排列。
做法
合法的 $P$ 有什么要求呢？
如果出现 $P_{i} > P_{i+1}$ ，说明肯定是某个序列中连续弹出了两个数字，这启示我们可以把排列分成若干段：$[l_1,r_1],[l_2,r_2],…,[l_m,r_m]$ 。
满足：
- $\forall l_i\le j\le r_i:P_{j}\le P_{l_i}$
- $P_{l_i} < P_{l_{i+1}}$
可以注意到对于每个排列 $P$ ，分法是唯一的。
那么可以注意到 $P$ 合法当且仅当每段长度 $\le 3$ ，而且长度 $\ge 2$ 的段数 $\le n$ 。
然后直接 dp 就行了。
时间复杂度：$O(n^2)$ 。
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;
typedef long long LL;
const int N = 2e3 + 5;
LL mod, f[N * 3][N];
int n;
int main(){
cin >> n >> mod;
f[0][0] = 1ll;
for(int i = 0; i <= n * 3; i++){
for(int j = 0; j <= n; j++){
if(i + 1 <= n * 3) f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
if(i + 2 <= n * 3 && j + 1 <= n) f[i + 2][j + 1] = (f[i + 2][j + 1] + f[i][j] * (i + 1)) % mod;
if(i + 3 <= n * 3 && j + 1 <= n) f[i + 3][j + 1] = (f[i + 3][j + 1] + f[i][j] * (i + 1) % mod * (i + 2)) % mod;
}
}
LL ans = 0ll;
for(int i = 0; i <= n; i++) ans = (ans + f[n * 3][i]) % mod;
cout << ans << "\n";
return 0;
}
|
和官方题解基本一致。
学到一个新词汇，上面的划分方法可以用一个更加专业的说法说：按照前缀 $max$ 分段。
