A. Sakurako's Exam

每次给两个数，第一个数表示序列中1的个数，第二个数表示序列中2的个数；在1和2前面加上+或者-，判断是否可以让整个序列的加减结果为0

  1. 只有1或只有2的情况，个数必须为偶数
  2. 有1有2的情况，根据2的奇偶情况进一步讨论1的奇偶
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 <iostream>
using namespace std;
#define int long long
void solve()
{
	int a, b;
	cin >> a >> b;
	if (!b)
	{
		if (a % 2 == 0)	cout << "YES" << '\n';
		else cout << "NO" << '\n';
		return;
	}
	if (!a)
	{
		if (b % 2 == 0)	cout << "YES" << '\n';
		else cout << "NO" << '\n';
		return;
	}

	if (b % 2)//有奇数个2
	{
		if (a % 2 == 0) cout << "YES" << '\n';
		else cout << "NO" << '\n';
		return;
	}
	else//有偶数个2
	{
		if (a % 2 == 0) cout << "YES" << '\n';
		else cout << "NO" << '\n';
		return;
	}
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

B. Square or Not

判断一个字符串转换成的矩形，能否是边界全为1内部全为0的正方形

  1. 判断能否是正方形
  2. 转换成矩阵，遍历即可
  3. 注意边长小于等于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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define int long long
const int N = 1e3;
int g[N][N];
void solve()
{
	int n; cin >> n;
	string s; cin >> s;
	int e = sqrt(n);
	if (e * e != n)//如果不是正方形
	{
		cout << "No" << '\n';
		return;
	}
	if (e <= 2)
	{
		if (s.find('0') == string::npos) //如果没找到0
			cout << "Yes" << '\n';
		else cout << "No" << '\n';
		return;
	}
	else
	{
		for (int i = 0; i < n; i++)
		{
			g[i / e][i % e] = s[i] - '0';//建立矩形
		}
		for (int i = 0; i < e; i++)
		{
			for (int j = 0; j < e; j++)
			{
				if (i == 0 || j == 0 || i == e - 1 || j == e - 1)//边界
				{
					if (g[i][j] != 1)
					{
						cout << "No" << '\n';
						return;
					}
				}
				else
				{
					if (g[i][j] != 0)
					{
						cout << "No" << '\n';
						return;
					}
				}
			}
		}
		cout << "Yes" << '\n';
	}
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

C. Longest Good Array

给定两个数，要求在这两个数间插入最多的数得到一个序列，并且满足该序列单调递增并且元素之间的间隔不断增大，求整个序列的个数

  1. 利用二分，要数尽可能的多，那么间隔要尽可能的小，是从1开始的以1为等差的等差数列，二分间隔的和
  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
#include <cmath>
#include <iostream>
using namespace std;
#define int long long
void solve()
{
	int x, y;
	cin >> x >> y;
	int gap = y - x;
	//二分
	int ans = 0;
	int l = 1, r = sqrt(2 * gap), mid;
	while (l < r && l + 1!= r)
	{
		mid = l + r >> 1;
		if ((mid + 1) * mid / 2 <= gap) l = mid;
		else r = mid - 1;
	}
	if ((l + 1) * l / 2 <= gap) ans = max(ans, l + 1);//实际上讨论的时候是分<和==的情况，然后发现这两个的式子是一样的，于是合并了
	if ((r + 1) * r / 2 <= gap) ans = max(ans, r + 1);
	cout << ans << '\n';
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

D. Sakurako's Hobby

给定一个数组，根据数组的下标和数组的值进行不断递推，每个数都有黑白两种颜色，问\(1\sim n\)每个数可以到达的颜色为黑色的数的个数

  1. 利用并查集，将能到达的放在一个集合
  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
42
43
44
45
46
47
48
49
50
#include <iostream>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int s[N], c[N], p[N],ct[N];
int find(int x)//找根节点
{
	if (x != p[x]) p[x] = find(p[x]);
	return p[x];
}
void merge(int x, int y)//合并两个节点
{
	p[find(x)] = find(y);
}
void solve()
{
	int n;	cin >> n;
	bool st[N] = {};
	for (int i = 1; i <= n; i++) p[i] = i;//初始化
	for (int i = 1; i <= n; i++) cin >> s[i];//排列
	string color; cin >> color;
	for (int i = 1; i <= n; i++) c[i] = color[i - 1] - '0', ct[i] = 1 - c[i];//颜色
	for (int i = 1; i <= n; i++)
	{
		if (!st[i])//如果没有加入过某个集合
		{
			st[i] = true;
			int j = s[i];
			while (j != i)
			{
				merge(j, i);
				st[j] = true;
				ct[find(j)] += 1 - c[j];
				j = s[j];	
			}
		}
	}
	for (int i = 1; i <= n; i++)
		cout << ct[find(i)] << " ";
	cout << '\n';
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

E. Alternating String

对一个序列有两个操作方式：删除一个字母（最多进行一次该操作）；改变一个字母。让序列最终变成偶数个数且奇数位和偶数位上的字母分别相同

  1. 分序列数本来是偶数和奇数进行讨论

  2. 在序列是奇数的情况下要进行第一个操作，而删除一个数会改变后面序列的奇偶，于是\(\color{red}{我们从后往前枚举删除的数}\)，这样在枚举删除前面的字母的时候后面的字母的奇偶已经是改变的了

  3. 本题应用了上篇Codeforces-971-G对数据类似的处理方法

    \(\color{red}{补充：}\)为什么erase要用find？因为如果是删除数，而不是删除位置，那么multiset中的所有等于该数的数都会被删除

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
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <set> 
#include <map>
using namespace std;
#define int long long
void solve()
{
	int n;	cin >> n;
	string s;	cin >> s;
	if (n == 1 || n == 3)
	{
		cout << 1 << '\n';
		return;
	}
	if (n == 2)
	{
		cout << 0 << '\n';
		return;
	}
	//n >= 3 的情况
	multiset<int> e, o;//记录所有字母出现的次数，升序排列
	map<int, int> me, mo;//记录每个字母出现的次数
	for (int i = 0; i < n; i += 2)//偶数位
	{
		if (e.count(me[s[i] - 'a'])) e.erase(e.find(me[s[i] - 'a']));
		me[s[i] - 'a']++;
		e.insert(me[s[i] - 'a']);
	}
	for (int i = 1; i < n; i += 2)//奇数位
	{
		if (o.count(mo[s[i] - 'a'])) o.erase(o.find(mo[s[i] - 'a']));
		mo[s[i] - 'a']++;
		o.insert(mo[s[i] - 'a']);
	}
	if (n % 2)//如果n是奇数，需要进行删除操作，会改变奇偶
	{
		int ans = 0x3f3f3f3f;
		for (int i = n - 1; i >= 0; i--)
		{
			if (i % 2)//如果i是奇数
			{
                //偶数位删除
				o.erase(o.find(mo[s[i] - 'a']));
				mo[s[i] - 'a']--;//表示该点被删掉
				if (mo[s[i] - 'a'] == 0) mo.erase(s[i] - 'a');
				else o.insert(mo[s[i] - 'a']);
				ans = min(ans, n - *o.rbegin() - *e.rbegin());
				//转换到奇数位
				if (me.count(s[i] - 'a')) e.erase(e.find(me[s[i] - 'a']));
				me[s[i] - 'a']++;
				e.insert(me[s[i] - 'a']); 
			}
			else
			{
				e.erase(e.find(me[s[i] - 'a']));
				me[s[i] - 'a']--;//表示该点被删掉
				if (me[s[i] - 'a'] == 0) me.erase(s[i] - 'a');
				else e.insert(me[s[i] - 'a']);
				ans = min(ans, n - *o.rbegin() - *e.rbegin());

				if (mo.count(s[i] - 'a')) o.erase(o.find(mo[s[i] - 'a']));
				mo[s[i] - 'a']++;
				o.insert(mo[s[i] - 'a']);
			}
		}
		cout << ans << '\n';
	}
	else//n是偶数，只进行变换操作
	{
		cout << n - *e.rbegin() - *o.rbegin() << '\n';
	}
}
signed main()
{
	int t;	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}