考试经过

开场T1发现状压dp，写了2h和暴力拍上了，觉得比较稳
T2直接模拟的，T3开始以为二分后来假了，于是暴力匹配+玄学记忆化+剪枝，不知道有多少分
T4很不可做的样子，于是暴力+测试点分治走人了
然而T1挂了，20+47+100+20=187，直接转移给最大值是不对的，样例太水了。。

T1 出了个大阴间题

分析一下假如这一位上可以取1，2，3，4，5，然而下一位一定会转移到1e5，这种情况下1，2，3，4，5都可以有贡献，然而你只记了答案为5的方案数，显然没有算够，所以只转移给最大值是错误的
正确做法是多开一维记录最大值，发现最大值只有\(2n\)种，所以可以map记忆化，\(f\)数组代表当前最大值的方案数，\(g\)代表当前最大值的价值和，有了这个就有正确性了，转移复杂度\(2^n\times n^2\)
对于\(b\)由于都是一堆和一个合并，所以取值也很有限，固定的已合并数的\(b\)是相同的

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int f[1<<19][40],g[1<<19][40],a[20],n,k;
vector <int> sta[20];
inline int getsum(int x)
{
	int s=0;
	while(x)
	{
		if(x&1)s++;
		x>>=1;
	}
	return s;
}
unordered_map <int,int> mp;
int tot,rk[40];
inline void ins(int x)
{	
	if(mp.find(x)==mp.end())mp[x]=++tot,rk[tot]=x;
}
int v[25]={0,0,1,3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287};
signed main()
{
	freopen("repair.in","r", stdin);
	freopen("repair.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++)ins(a[i]),ins(a[i]+1);
	for(int i=1;i<(1<<n);i++)sta[getsum(i)].push_back(i);
	for(int i=1;i<=n;i++)f[1<<(i-1)][mp[a[i]]]=1;
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<sta[i].size();j++)
		{
			int s=sta[i][j];
			for(int p=1;p<=tot;p++)
			{
				int w=rk[p];if(!f[s][p])continue;
				for(int l=1;l<=n;l++)
				{
					if((s>>(l-1))&1)continue;
					int ww=a[l],ga=mp[a[l]];
					if(w<ww)
					{
						f[s|(1<<(l-1))][ga]=(f[s|(1<<(l-1))][ga]+f[s][p])%mod;
						g[s|(1<<(l-1))][ga]=(g[s|(1<<(l-1))][ga]+g[s][p]+f[s][p]*(k*ww%mod+v[i])%mod)%mod;
					}
					if(w==ww)
					{
						int tt=mp[w+1];
						f[s|(1<<(l-1))][tt]=(f[s|(1<<(l-1))][tt]+f[s][p])%mod;
						g[s|(1<<(l-1))][tt]=(g[s|(1<<(l-1))][tt]+g[s][p]+f[s][p]*(k*(ww+1)%mod+v[i])%mod)%mod;
					}
					if(w>ww)
					{
						f[s|(1<<(l-1))][p]=(f[s|(1<<(l-1))][p]+f[s][p])%mod;
						g[s|(1<<(l-1))][p]=(g[s|(1<<(l-1))][p]+g[s][p]+f[s][p]*(k*w%mod+v[i])%mod)%mod
					}
				}	
			}
		}		
	}
	for(int i=tot;i>=1;i--)
	{
		if(f[(1<<n)-1][i])
		{	
			cout<<rk[i]<<" "<<g[(1<<n)-1][i]<<endl;
			return 0;
		}
	}
	return 0;
}

T2 最简单辣快来做

咕

T3 是我的你不要抢

所以这个题解实际证明了暴力复杂度是对的？
记忆化一下，貌似不需要什么特殊处理
正解似乎是AC自动机上的数据结构，但复杂度差不多

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
const int N=600060;
char a[N];vector <ull> ha[N];
ull p[N];int n,q,l[N];
inline ull get(int i,int l,int r)
{
	return ha[i][r]-ha[i][l-1]*p[r-l+1];
}
unordered_map <ull,int> mp;
inline ull ganhash(int x,int y)
{
	return (ull)x*5e6+y;
}
signed main()
{
	freopen("string.in","r",stdin);
	freopen("string.out","w",stdout);
	cin>>n>>q;
	p[0]=1;for(int i=1;i<=6e5;i++)p[i]=p[i-1]*131;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",a+1);l[i]=strlen(a+1);
		ull h=0;ha[i].push_back(h);
		for(int j=1;j<=l[i];j++)
		{
			h=h*131+(a[j]-'a'+1);
			ha[i].push_back(h);	
		}
	}
	for(int i=1;i<=q;i++)
	{
		int x=read(),y=read();ull hh=ganhash(x,y);
		if(mp.find(hh)!=mp.end())
		{printf("%d\n",mp[hh]);continue;}
		int ma=0,lim=min(l[x],l[y]);
		for(int j=lim;j>=1;j--)
		{
			if(get(x,l[x]-j+1,l[x])==get(y,1,j))
			 {ma=j;break;}
		}
		mp.insert(make_pair(hh,ma));
		printf("%d\n",ma);
	}
	return 0;
}

T4 显然也是我整的

咕

考试总结

知道的就是对拍数据一定要强一点
还有速度应该上去一些