[abc] AtCoder Beginner Contest 244

前言

时间就是金钱 就是生命 ,所以直接从D题开始补了 传送门:

D.Swap Hats

题目很简单,但是有一个 分析状态 的思想值得学习

我们简单分为

• (1)有三个不同
• (2)有两个不同
• (3)都相同

显然 状态(1)(3) 无论如何怎么操作都只能 转换到 状态(2)

但是状态(2) 一次操作 只能转换到 (1)(3)

因此在 1 e 18 1e^{18} 1e18的偶数操作下,只有(1)(3)状态是合法的

Mycode

void solve()
{
	char a,b,c;cin>>a>>b>>c;
	char A,B,C;cin>>A>>B>>C;
	
	int t = (A == a) + (B == b) + (C  == c);
	if(!t || t== 3){
		coutS>>T>>x;
	while(m -- ){	
		int a,b;cin>>a>>b;
		g[a].pb(b);g[b].pb(a);
	}
	
	f[1][S][0] = 1;
	
	//长度是  k+1
	for(int i=2;i