CF - B. Combinatorics Homework（思维）

https://codeforces.com/contest/1574/problem/B

题意
给定 a 个字符 ‘A’，b 个字符 ‘B’，c 个字符 ‘C’。
问，所有字符能否组成一个字符串，存在且只存在 m 个位置满足 s[i] = s[i+1]。

思路
求出能满足的 s[i] = s[i+1] 的位置个数的最大值和最小值，然后判断 m 是否在这个区间中。

证明：
最小值的情况是：a b a b a c a c a a，如果想让满足的位置个数+1，只需要调换其中某个 a,b 或者 a,c 的顺序，就是只要想让满足位置数+1就可以调换两个位置使其满足，直到加到最大值。
所以最小值到最大值这个区间中的所有数都可以满足。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		int a, b, c;
		cin >> a >> b >> c >> m;
		int maxa = a + b + c - 3;
		int mina = 1e9;
		
		if(a > b + c) mina = a - (b + c) - 1;
		else if(b > a + c) mina = b - (a + c) - 1;
		else if(c > a + b) mina = c - (a + b) - 1;
		else mina = 0;
		
		if(m >= mina && m <= maxa) cout << "YES\n";
		else cout << "NO\n";
	}
	
	return 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

---

今天又碰见一道这样的题目：
https://codeforces.com/contest/1695/problem/C

C. Zero Path

题意
给定 n*m 的矩阵，每个位置有 1 或者 -1 两种数。
每次操作只能向右或者向下走一格，问能否存在一条从 (1, 1) 到 (n, m) 的路径满足走过的格子权值之和为 0？

思路
和上一题一样，判断性问题。

特判 n+m 为偶数的情况，一共走过 n+m-1 个格子，格子数都为奇数，最后的总和肯定不会为偶数 0。
然后和上一题所用的方法是一样的，求出从起点到终点所走路径中权值和的最大值、最小值，判断 0 是否在这个区间内。

为什么这样是正确的呢？
一共 n+m-2 个方向抉择，形成 R D 两种字符组成的字符串。如果对调两个位置，对其他位置没有影响，考虑对总权值的影响。
如果走到的两个位置权值不变则没有影响 +0，而如果原来是 +1 变成了 -1 或者 -1 变成了 +1，这样产生的效果是原来权值之和 -2 或者 +2，发现都是变的偶数。
每变一次都使得最后答案+2或者-2，那么最小值最大值区间中的所有偶数都能得到，那么 0 在这个区间中的话也能得到了。
很神奇。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 1010, mod = 1e9+7;
int T, n, m;
int a[N][N], maxa[N][N], mina[N][N];

signed main(){
	Ios;
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++)
			{
				int x; cin >> x;
//				maxa[i][j] = max(maxa[i-1][j], maxa[i][j-1]) + x; 这样更新不可以
//				mina[i][j] = min(mina[i-1][j], mina[i][j-1]) + x;
				if (i == 1)
	            {
	                maxa[i][j] = x + maxa[i][j - 1];
	                mina[i][j] = x + mina[i][j - 1];
	            }
	            if (j == 1)
	            {
	                maxa[i][j] = x + maxa[i - 1][j];
	                mina[i][j] = x + mina[i - 1][j];
	            }
	            if (i != 1 && j != 1)
	            {
	                maxa[i][j] = x + max(maxa[i][j - 1], maxa[i - 1][j]);
	                mina[i][j] = x + min(mina[i][j - 1], mina[i - 1][j]);
	            }
			}
		}
		if((n + m) % 2 == 0) cout << "NO\n";
		else if(maxa[n][m] >= 0 && mina[n][m] <= 0) cout << "YES\n";
		else cout << "NO\n";
	}
	
	return 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

要额外注意更新到第一行和第一列位置的最大值和最小值的时候，不要越界了！
这个题和之前直接越界的题目不同的地方在于，之前越界可以求方案数：越界的地方方案数初始为0；可以求最大值：保证维护的值为正数了，而越界的地方初始为0…
而这个题就不能越界：因为维护的值可能为正数，这样的话维护最小值，和越界位置的0取最小值就变成 0 了，而越界的地方是不应该去更新的。同样维护的值可能为负数，这样的话维护最大值的时候和越界位置取最大值也变成 0，出现错误！

---

然后这道题也可以用 bitset 过掉，直接 f[i, j] 表示成一个二进制数，第 k 为是否为 1 表示到达 (i, j) 点时，能否满足的权值和为 k。
然后在更新的时候，当前位置直接从上一位置的二进制数 左移 1 位或者右移 1 位来更新，O(1)。
然后 n*m 个 bitset，每个 bitset 长度为 2000，空间复杂度为 O(n*m*2000/32 = 6e7)，刚刚好。（长度为 n 的 bitset 所占空间为 n/32，很优秀！）
注意开的时候不要开太多，用多少开多少。

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 1010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
	Ios;
	cin >> T;
	
	while(T--)
	{
		cin >> n >> m;
		bitset<2010> f[n+1][m+1]; //不要开太多，建立耗时
		f[0][1][1000] = f[1][0][1000] = 1;
		
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				int x; cin >> x;
				if(x == 1) f[i][j] |= f[i-1][j] << 1, f[i][j] |= f[i][j-1] << 1;
				else f[i][j] |= f[i-1][j] >> 1, f[i][j] |= f[i][j-1] >> 1;
			}
		}
		if(f[n][m][1000] == 1) cout << "YES\n";
		else cout << "NO\n";
	}
	return 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