题解 Codeforces Round #814 (Div. 1/2)

题解 Codeforces Round #814 (Div. 1/2)

div2.

比赛链接

挥手。

div2A. Chip Game

div2A 放这种题？

设先手一步、后手一步为一轮。那么每一轮，$x$ 坐标的增加值和 $y$ 坐标的增加值都是偶数（奇数 $+$ 奇数 $=$ 偶数）。而起点的坐标为 $(1,1)$，二数相加也是偶数。所以每一轮结束后的坐标 $x+y$ 必定为偶数。所以若 $n,m$ 奇偶不同，显然先手必胜。

否则后手有必胜策略，即使接下来的棋盘为正方形，然后仿照先手的走法换个方向走。

#define multiple_test_cases
 
int n, m;
 
void solve(){
   
	n = rdi;
	m = rdi;
	if((n - m) & 1){
   
		puts("Burenka");
	} else {
   
		puts("Tonya");
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

div2B. Mathematical Circus

考虑对 $k\mathrm{mod}4$ 的值分类讨论：

• 若 $k\mathrm{mod}4=0$，那么即 $4|ab$，此时所有的奇数都要和 $4$ 的倍数分类，而显然 $[1,n]$ 的正整数中奇数要比 $4$ 的倍数多，所以无解。
• 若 $k\mathrm{mod}4=1$，代码里写的是(3,1),(2,4)，但实际上和 mod 3 一样就行。
• 若 $k\mathrm{mod}4=2$，每四个数为一组，类似 $(2,1),(3,4)$ 构造。
• 若 $k\mathrm{mod}4=3$，每两个数为一组，类似 $(1,2)$ 构造。

#define multiple_test_cases
 
const int N = 2e5 + 10;
int n, k;
 
void solve(){
   
	n = rdi;
	k = rdi;
	k %= 4;
	if(k == 0){
   
		puts("NO");
	} else if(k == 1){
   
		puts("YES");
		if(n % 4 == 0){
   
			for(int i = 1; i <= n; i += 4){
   
				printf("%d %d\n%d %d\n", i+2, i, i+1, i+3);
			}
		} else {
   
			n -= 2;
			for(int i = 1; i <= n; i += 4){
   
				printf("%d %d\n%d %d\n", i+2, i, i+1, i+3);
			}
			printf("%d %d\n", n+1, n+2);
		}
	} else if(k == 2){
   
		puts("YES");
		for(int i = 1; i <= n; i += 2){
   
			if(((i-1)/2) & 1){
   
				printf("%d %d\n", i, i+1);
			} else {
   
				printf("%d %d\n", i+1, i);
			}
		}
	} else {
   
		puts("YES");
		for(int i = 1; i <= n; i += 2){
   
			printf("%d %d\n", i, i+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
43
44
45
46
47
48
49
50
51
52
53

div2C. Fighting Tournament

下文中的“它”指 a i a_i a