Codeforces刷题记录（tag: chinese remainder theorem 873 ~ 1073）

单词记录：

1. training regime 训练制度 train 训练 grandmaster n.大师  divisible adj.可除尽的  a permutation 一个排列
rearrang 重排列 digit n.数字，数位  generat 产生 denoted 表示 valid solution 有效的解决方案
1
2

1.题目名称：A. Competitive Programmer 1266A

2.思路：

给定n个字符串，对于每一个字符串，经过重排列之后结果是不是60的倍数。
我们发现，是60的倍数，就必须是3和20的倍数。
不管怎么重排列，数字总和都是不变的。
判断一个数是不是3的倍数 等价于 每一位求和判断是不是3的倍数。
如果要是20的倍数，则排列之后的答案最后两位必须是00,20,40,60,80之中是任意一种。倒数第二位必须是偶数。
因此，现在要做的就是，对于每一个字符串：
1.求总和判断是不是3的倍数。
2.判断是否至少有一个0。
3.判断是否有第二个偶数（包括0）。

3.代码：

#include 

using namespace std;

int n;
int main()
{
	cin >> n;
	while(n --)
	{
		string a;
		cin >> a;
		bool ok1 = false, ok2 = false;//ok1判断是否至少有一个0 ok2是找一个偶数。 
		int cnt = 0;//判断总和是不是3的倍数 
		for(auto t : a)
		{
			int x = t - '0';
			if(x == 0 && !ok1) ok1 = true;
			else if(x % 2 == 0) ok2 = true;
			cnt += x;
		}
		if(ok1 && ok2 && cnt % 3 == 0) puts("red");
		else puts("cyan"); 
	}
	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

4.总结：

• $结论：一个数是3的倍数当且仅当这个数各位上的数字加起来是3的倍数。$
• 要想是一个数的倍数，可以分解，比如本题。
• 0是一个偶数。