Codeforces Round #814 (Div. 2)

比赛地址

A.Chip Game（奇偶性）

思路：

因为每一次只能走奇数步，所以每一轮走的总步数必然是偶数步。因为只能往右或者往上走，所以总步数最多为(n + m - 2)步。故若(n + m - 2)为奇数则最后一步必然是先手走到，若为偶数则必然是后手走到。

代码：

#include 

using namespace std;

int main()
{
	int t;
	cin >> t;
	while(t --)
	{
		long long n, m;
		cin >> n >> m;
		if((n + m - 2) & 1) puts("Burenka");//若最多走的步数是奇数步则先手必赢，否则后手必赢 
		else puts("Tonya");
	}	
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结：

• 此类，走棋盘走到不能走位置的问题，多从奇偶性的角度考虑。

---

B.Mathematical Circus（数学）

思路：

每组测试数据给定一个n和k（保证n为偶数）。所求的就是 将1~n分解为若干个(a,b)数对，且(a+k)*b被4整除。要想4|(a+k)*b，等价于 4|(a+k)或4|b。
结论1：当(a + k) 或者 b为4的倍数时，那么可以随便匹配一个数。
对于(a+k)*b能被4整除，合法的情况有三种（考虑的是a和b的奇偶性）
1.偶偶，如果(a+k)和b都是偶数，则分别提供一个因子2，就变成了4的倍数。
2.奇偶，当b是偶数但不是4的倍数时，b提供了一个因子2，要想成为合法解，因为a是奇数，则需要k%4的结果是奇数，奇数加上奇数才能变为偶数为答案再提供一个因子2，使得答案变成4的倍数。
3.偶奇，当a是偶数但不是4的倍数且b是奇数时，此时因为b的值已经固定，所以当且仅当k%4为偶数时，(a+k)刚好变为4的倍数。
而对于(a + k)来说要想(a+k)是偶数需要考虑一下k%4的分类情况。

• k % 4 = 0 时，那么(a + k) * b = a * b。若想要a * b是4的倍数，则a或b中必定有一个是4的倍数，但是1~n中能被4整除的数的个数一共为$\frac{n}{4}$个，一个4的倍数只能随便带一个数，故这种情况无解。
• k % 4 = 1 或 3 时，此时，有两种情况，若b为偶数但不是4的倍数，则需要将(a+k)凑成偶数，故此时a必须是奇数，才能成为4的倍数。若b为4的倍数，则(a+k)是奇是偶都可以。
• k % 4 = 2 时，有两种情况，若b为奇数 ，则需要将(a + k)凑成4的倍数，此时a必须为偶数才能成为4的倍数， 若b为4的倍数，则(a+k)是奇是偶都。

代码：

#include 

using namespace std;

int main()
{
	int t;
	cin >> t;
	while(t --)
	{
		int n, k;
		cin >> n >> k;
		int r = k % 4;//余数
		if(r == 0) puts("NO");//无解情况
		else if(r == 1 || r == 3)//若r是奇数 
		{
			puts("YES");
			for(int i = 0; i + 4 <= n; i += 4)
			{	//i+1为奇数， i + 2为偶数但不是4的倍数  
				cout << i + 1 << " " << i + 2 << endl;
				//i+4是4的倍数可以随便选个数配对
				cout << i + 3 << " " << i + 4 << endl; 
			}
			//若n不是4的倍数，则必有一对是剩余的。 
			if(n % 4 == 2) cout << n - 1 << " " << n << endl; 
		} 
		else if(r == 2)//如果r是偶数 
		{
			puts("YES");
			for(int i = 0; i + 4 <= n; i += 4)
			{	//将(a+k)凑成4的倍数，所以可以随便带一个 
				cout << i + 2 << " " << i + 1 << endl;
				cout << i + 3 << " " << i + 4 << endl;
			}//将(a+k)凑成4的倍数。 
			if(n % 4 == 2) cout << n << " " << n - 1 << endl;
		} 
	}
	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

总结：

• 对于此类，将1~n匹配分数对需要找规律的问题，可以多从奇偶性考虑。
• 每次考虑对余数进行分类讨论时，可以参照本题的循环方式。
• 每一个偶数都至少提供一个因子2。

---

C. Fighting Tournament（模拟）

思路：

思路参考，代码注释。

代码：

#include 

using namespace std;

const int N = 200010;
int a[N], b[N], c[N], d[N];//a[]存每个人的能力值，b[]存每一轮是谁赢的，c[]存第i个人一共赢了多少轮，d[]存第一次赢是在第几轮。 
int main()
{
	int t;
	cin >> t;
	while(t --)
	{
		//memset(b, 0, sizeof b);
	//	memset(c, 0, sizeof c);
		//memset(d, 0, sizeof d);
		int n, m;
		scanf("%d%d", &n,&m);
		for(int i = 1; i <= n; i ++) 
		{
			scanf("%d", &a[i]);//输入每一个人的能力值
			c[i] = d[i] = 0;
		}
		int now = a[1];//擂主
		for(int i = 2; i <= n; i ++)
		{	//如果当前这个人比擂主厉害  因为每个人的能力值不一样，故用能力值来代表每个人，用下标的话，需要存能力值和下标 
			if(a[i] > now) now = a[i];
			if(d[now] == 0) d[now] = i - 1;//如果是第一次赢
			c[now]++;
			b[i - 1] = now;
		} 
		 while(m --)
		 {
		 	int x, k;
		 	scanf("%d%d",&x, &k);//询问第x个人，前k轮赢了多少次
			//0.根据规则可以发现，若能力最强的人当了擂主，则后面所有人都无法赢。前n-1轮必定会出现最大的擂主。 
			//1.对于前n-1轮有： 
			//1.1 如果知道第k轮是i赢的，那a[i] < a[x] 若他的能力值小于第x个人的。说明还没有碰到过x,故答案为0;
			//1.2 若能力等于第x个人的能力值，若知道第x个人第一次赢是在第j轮，则答案为 k - j + 1;
			//1.3 若能力大于第x个人的能力值，若知道第x一共赢了多少轮，则答案就为多少轮。 
			//2.当k大于n-1时。答案就是 若第x个人不是最大值，则答案为一共赢了多少轮，若是最大值答案则为k-第一次赢的轮数+1
			//因此需要维护的信息有三个：每一轮是谁赢的，一共赢了多少轮，第一次赢是在第几轮。 
			x = a[x];//将下标转成值
			int ans = 0;
			if(k <= n - 1)
			{
				if(b[k] < x) ans = 0;
				else if(b[k] == x) ans = k - d[x] + 1;
				else ans = c[x];
			} 
			else
			{
				ans = c[x] + (x != n ? 0 : k - (n - 1));
			}
			cout << ans << endl;
		 }
	}	
	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
47
48
49
50
51
52
53
54
55
56
57
58

总结：

• 对于需要预处理的模拟题，需要考虑，我们要求得答案需要维护哪些信息。
• for循环赋为0 比 memset快很多。

---

E. Fibonacci Strings（贪心）

思路：

题意就是给定一个字符集，让我们拼凑出一个斐波那契数列，比如给出3个a，1个b，3个c。
我们可以凑成 c b cc aaa 对应斐波那契数列的 1 1 2 3。
对此，可以得出来若字符集所有字符的数量不等于斐波那契数列的某个前缀则必然无解。
所以步骤如下：
1.用map预处理斐波那契数列的各个前缀和 和 斐波那契数列。map前面存值，后面存前几项的前缀和。
2.对于每一组测试数据：
若字符集是数量加起来，不是某一个前缀和则必然无解。
否则，我们从最后一项，依次向前拼凑，如果只有一种字母比当前项大，则必然只能用这种字符，若同时有两项比当前这一项大的话，则需要用最大值拼凑。
证明：
比如1 1 2 3 5 8 13 21 现在有21个a, 23个b
若 拼21的时候用的是 21个a。那么根据结论1，我们之后最大也只能拼出21个b来，还剩下两个b。
但是因为我们拼凑21的时候，是一个隔着一个空拼凑的，所以我们发现剩下的两个b是不能用来拼凑剩下的数的。
若 拼21的时候用的是 21个b，还剩下2个b。那么根据结论1，我们最大能拼出来21个a。并且剩下的两个b还可以拼凑被a所隔出来的空。
得证，在拼凑时，应该用最大值来拼当前项。

代码：

#include 

using namespace std;
typedef long long ll;

const int N = 105;
int fib[N];
int n, a[N];//字符集 
int main()
{
	map<ll, int> mp;//映射 前n项和 
	fib[0] = fib[1] = 1;//第0项和第1项为1
	mp[1] = 0, mp[2] = 1;//前0项和为1 前1项和为2 
	//预处理每一项的前i项和 
	ll s = 2;
	for(int i = 2; i <= 43; i ++)
	{
		s += (fib[i] = fib[i - 1] + fib[i - 2]);
		mp[s] = i;//计算前i项和 
	}
	int t;
	cin >> t;//t组数据 
	while(t --)
	{
		int n;//字符的种类 
		scanf("%d", &n);
		ll s = 0;//记录字符的总和 
		for(int i = 1; i <= n; i ++){
			scanf("%d", &a[i]);
			s += a[i];
		} 
		if(mp.find(s) == mp.end()) puts("NO");
		else
		{
			bool flog = true;
			int last = 0;
			//从最后一项依次凑 
			for(int i = mp[s]; i >= 0 && flog; i --)
			{
				int k = 0;//找最大的那一项 
				for(int j = 1; j <= n; j ++)
				{
					if(j == last) continue;//不能用相同的种类凑 
					if(a[j] > a[k]) k = j;//求最大的种类，要用最大的种类凑 
				}
				if(a[k] >= fib[i]) a[k] -= fib[i], last = k;
				else flog = false;
			}
			if(flog) puts("YES");
			else puts("NO");
		}
	}
	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
47
48
49
50
51
52
53
54

总结：

• 结论1：$斐波那契数列最后一项的值f_n=f_{n-1}+f_{n-3}+f_{n-5}+...加到不能加隔一项加一次$
• 结论2：$拼凑斐波那契数列的时候，若同时有两个数大于等于当前项，用最大的来拼凑，且不可能同时有三个数大于当前项。$