UOJ 670

题目
先考虑字符串总长度为偶数的情况，由于每个名字从前往后和从后往前都一样，那么我们相当于要找出除中间两个字符之外，两段完全一样的串。

那么这个可以看成从一个字符开始，交替扩展两个段 ，那么我们如果将一个字符的与 \(0\) 连无向边，二个字符的连两个字符间的边，这就相当于求一条从 \(0\) 出发的欧拉回路，可以发现我们在回路上交替选边最终一定能生成合法方案。而对于不与 \(0\) 联通的边，可以发现一种边要么出现次数全部为偶数，要么存在一个自环为奇数 (放在字符串中间)且剩下的都为偶数。

字符串为奇数长度的也类似，就是把 \(0\) 联通块外的边两两放在字符串两侧，从 \(0\) 开始跑一边欧拉回路并将其放在字符串中间位置。

这道题保证有解就很良心，无解的情况感觉太多了。

\(\text{Warning:}\) 跑欧拉回路的时候不能忘了当前弧优化，要不然会被卡 T 。

const int N=1e6+5;
int n,m,s[N],b[N][3],f[N],summ;
struct node{
	int next,to,id,flag,rev;
}a[N*2];int head[N],cnt=1,d[N];
int vis[N*2],top,tota,totb,tg[N];
mapma;
pii st[N*2],x[N],y[N];
struct Qu{
	int x,y,id,rev;
}t[N];int tou;
int cmp(Qu x,Qu y){
	if(x.x!=y.x)return x.x=1;i--){
		print(y[i].fi);
	}
	Flush();
	cout<<'\n';
	for(int i=1;i<=tota;i++){
		print(x[i].se);
	}
	for(int i=totb;i>=1;i--){
		print(y[i].se^1);
	}
	Flush();
	return 0;
}