https://atcoder.jp/contests/agc043

A - Range Flip Find Route

题意：给定一个黑白矩阵，要求从左上角走到左下角，只能向右或者向下走，且只能走白格，每次操作可以选一个矩形区域反转所有颜色，问最小操作数。

dp

每一格可能从上或者从左转移来，如果转移过来的那个格子是白色，那么当前格就要再翻转，否则可以和前一格一起翻转。虽然可能会翻转其他不需要的格子，但是由于限制了只能向右或下走，所以不会有影响。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const int INF = 0x3f3f3f3f;
int n, m;
char mp[110][110];
int dp[110][110];
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)scanf("%s", mp[i]);
	memset(dp, 0x3d, sizeof(dp));
	dp[0][0] = (mp[0][0] == '.' ? 0 : 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!i && !j)continue;
			if (mp[i][j] == '.') {
				if (i > 0)dp[i][j] = min(dp[i][j], dp[i - 1][j]);
				if (j > 0)dp[i][j] = min(dp[i][j], dp[i][j - 1]);
			}
			else {
				if (i > 0) {
					if (mp[i - 1][j] == '#')dp[i][j] = min(dp[i][j], dp[i - 1][j]);
					else dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
				}
				if (j > 0) {
					if (mp[i][j - 1] == '#')dp[i][j] = min(dp[i][j], dp[i][j - 1]);
					else dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
				}
			}
		}
	}
	printf("%d\n", dp[n - 1][m - 1]);
	return 0;
}

 

B - 123 Triangle

 

题意：给定数列 a1a2…aNa_1a_2\ldots a_N，每个数只会是1，2，3，xi,jx_{i,j} 表示：

  • x1,j:=ajx_{1,j} := a_j ，1≤j≤N1 \leq j \leq N
  • xi,j:=∣xi−1,j−xi−1,j+1∣x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} |，2≤i≤N2 \leq i \leq N 且 1≤j≤N+1−i1 \leq j \leq N+1-i

求 xN,1x_{N,1}

 

意思就是一个类似倒着的杨辉三角的东西，每个数等于它上方和右上方的数的差的绝对值，求最后一层的那个数。特殊的一点是第一层的每个数只会是1或2或3.

答案只可能是0或1或2，那么先考虑答案的奇偶性来确定是不是1.

最终结果一定是1，2，3的和差，考虑每个数的贡献，每个数的出现次数为 Cn−1i−1C_{n-1}^{i-1} ，就是二项式的系数，想到杨辉三角的时候就应该能猜出来，也是第一层的数到最后一层的路径数。那么当a本身为奇数，且 Cn−1i−1C_{n-1}^{i-1} 也为奇数时，贡献为奇数，当所有数的贡献都为奇数时，结果也是奇数，就是1。这里有个细节是把所有数都-1，对结果没有影响，但是之前要算1和3，现在只要算1了。

还有一点要看出来的是如果答案为2，那么数列里不能有2（都-1后不能有1），这一点还是比较容易想到，可以试着画几层。

如果发现答案为偶数，且可能为2，那么数列里只会有1或3（-1后为0或2），把数列里所有数都除2，结果同样没有影响，所以除2之后再判断答案的奇偶性。由于答案只剩下0或1，所以一定能出结果。

至于判断 CnkC_n^k 的奇偶性，可以判断它包含的2的个数，而 Cnk=n!k!⋅(n−k)!C_n^k=\frac{n!}{k!\cdot (n-k)!}，所以可以预处理出每个阶乘包含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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N], tw = 1, fac[N], cnt[3];
void init(int n) {
	for (int i = 1; i <= n; i++) {
		int t = i;
		fac[i] = fac[i - 1];
		while (t && (t & 1 ^ 1)) {
			fac[i] ++;
			t >>= 1;
		}
	}
}
int fc(int n, int k) {
	return fac[n] - fac[k] - fac[n - k];
}
int main() {
	scanf("%d", &n);
	init(n);
	for (int i = 1; i <= n; i++) {
		char c;
		scanf(" %c", &c);
		a[i] = c - '1';
		if (a[i] == 1)tw = 0;
		int tmp = fc(n - 1, i - 1);
		if (tmp <= 0)cnt[a[i]] ^= 1;
	}
	if (cnt[1])puts("1");
	else {
		if (!tw)puts("0");
		else {
			if (cnt[2])puts("2");
			else puts("0");
		}
	}
	return 0;
}

 

还可以用Lucus定理，把 Cnk%2C_{n}^{k}\%2 变为 n,kn,k 在二进制下每一位的 CC 的乘积，由于二进制下只有0，1，所以仅当 C01C_0^1 时答案不为1，也就是需要存在 kk 中为1，而 nn 中为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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
int n;
int a[N], tw = 1;
int cal() {
	int res = 0;
	for (int i = 0; i < n; i++) {
		if (((n - 1)&i) == i)
			res ^= a[i];
	}
	return (res & 1);
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		char c;
		scanf(" %c", &c);
		a[i] = c - '1';
		if (a[i] == 1)tw = 0;
	}
	if (cal())puts("1");
	else {
		if (!tw)puts("0");
		else {
			for (int i = 0; i < n; i++)a[i] /= 2;
			if (cal())puts("2");
			else puts("0");
		}
	}
	return 0;
}