20210922下午

這是考試給出的截圖：

這是原題下面的描述

怎麼回事呢？

T1	T2	T3	T4
預測	100	100	100	100
一測	36	10	100	100

T1：

經典，并查集即可。

T2：

A C AC AC自動機應用基礎，本題從反向思考，用全部可能減去不含任何單詞的語句。那麼和不要62幾乎沒有差別，那麼将AC自動機建出來，将 E n d End End标記下傳，然後直接在 t r i e trie trie樹上跑 d p dp dp就行，考場 f a i l fail fail求錯了還沒下傳，寫 A C AC AC自動機還沒人家寫暴力分高。。。

轉移：

int dp()
{
	f[0][0]=1;int u,v,x=1,y=0,res=0;
	for(int i=1;i<=m;i++)
	{
		x=i&1;y=x^1;
		memset(f[x],0,sizeof(f[x]));
		for(int j=0;j<=tot;j++)
		{
			if(End[j]) continue;
			for(int k=0;k<26;k++)
			{
				v=trie[j][k];
				if(End[v]) continue;
				f[x][v]=(f[x][v]+f[y][j])%mod;
			}
		}
	}
	for(int i=0;i<=tot;i++) res+=f[x][i],res%=mod;
	return res;
}
           

T3：

可以轉換為 R M Q RMQ RMQ問題，占一個時間段就是将區間加一，所求即使區間最大值，線段樹維護即可。

T4：

類似合并果子，顯然從小往大合并是最優的，但由于可能不能每次都能合到 m m m堆，簡單驗證可知先少合一點讓之後每次都合 m m m堆是最優的，算一下應先合幾堆就行。

總結： A C AC AC自動機沒寫對太可惜了。