LA 3641 Leonardo's Notebook

发表于 | 更新于

Link

Solution

训练指南的模板题，还是记一下吧 对于一个循环CC 假设项数nn为奇数 则C2C^2一定也有奇数个项 否则 C2C^2一定是两个n2\dfrac n2项的循环 根据这个结论判断能否构造合法解 自行举例感受一下

Code

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
//Code by Lucida
#include<bits/stdc++.h>
#define get(x) scanf("%d",&x)
#define put(x) printf("%d",x)
#define gets(x) scanf("%s",x)
bool Work()
{
	static char s[30];
	static bool ud[30];
	static int cnt[30];
	gets(s+1);
	memset(ud,0,sizeof(ud));
	memset(cnt,0,sizeof(cnt));
	for(int i=1;i<=26;++i)
		s[i]-='A'-1;
	for(int i=1;i<=26;++i)
	{
		if(ud[i]) continue;
		int l=0;
		while(!ud[i])
		{
			l++;
			ud[i]=1;
			i=s[i];
		}
		cnt[l]++;
	}
	for(int i=2;i<=26;i+=2)
		if(cnt[i]&1) return 0;
	return 1;
}
int main()
{
	freopen("input","r",stdin);
	int T;get(T);
	while(T--)
		puts(Work()?"Yes":"No");
	return 0;
}
/* AC Record(Bugs)
++->+=2
*/