「联赛模拟测试35」题解

T1:组合

很容易发现，这题需要建个图

建图方法是把每个串的首尾相连，能反过来就建双向边

由于每个串都要用上，所以第一问就是判断是否存在欧拉路，第二问就是欧拉路径

考场前80打了个 (O(n^2)) 带回溯的暴搜，后20口胡了一个 (O(nlogm)) 的最长路路径记录

然后本地得了45分，联考oj得了25，原因：

1.

2.

其实一遍DFS就能找出欧拉路径（没写过。。）

判是否存在欧拉路的以前考过两次，不写了，贴个欧拉路的

void DFS1(int u,int id){
//	for(int x=now[u];x;x=e[x].next){
	while (now[u]) {
		int x = now[u]; now[u] = e[x].next;
		int v=e[x].to;
		if(black[x])continue;
		black[x]=1;
		if(opt==1)black[x^1]=1;
		DFS1(v,e[x].id);
		//sta[++top]=e[x].id;
	}
	if(id)sta[++top]=id;
}

T2：小W的魔术

沙雕题，十几分钟就推出来了

先往大致方向蒙个柿子

用计算器验证验证

然后就出来了

不会的建议练习打表

ans=((qpow(26,n)-qpow(26,n-m)-qpow(26,n-m-1)*25%mol*m%mol)%mol+mol)%mol;

这个部分分干扰性极大

T3：小Y的图

智障题，然而考试时没冲，脑子里只有T1

把货车运输改成建最小生成树就行

T4：小L的数

不会，割了