模拟72 考试总结

2024-01-20 08:03:17

考试经过

开场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 最简单辣快来做

前缀和好题
发现贡献是一个多项式的形式，由于他的样子所以直接做不太好拆
貌似可以前缀和，但一般的前缀和只有加减，如果你只做\(h_i \times a^{x_i}\times b^{y_i}\)的话只有存在逆元的50分
思考魔改前缀和，发现每次向右一格就是乘\(a\)，向左即为乘\(b\),所以我们那个广为人知的前缀和可以变成这样：

\[sum_{i,j}=sum{i-1,j}*a+sum_{i,j-1}*b-sum{i-1,j-1}*(a\times b)+v_{i,j} \]

这是60分做法，满分就是离散化，找四个边界的再乘上格子自己的贡献

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2050;
int n,q,w,h,a,b,mod;
struct node{int x,y,h,rk1,rk2;}p[N];
int p1[N],p2[N],lsh1[N],lsh2[N];
int sum1[N][N],sum2[N][N],sum3[N][N],sum4[N][N];
inline int ksm(int x,int y)
{
	int s=1;x%=mod;
	for(;y;y>>=1)
	{
		if(y&1)s=s*x%mod;
		x=x*x%mod;
	}
	return s;
}
int ksma1[50*N],ksma2[50*N],ksmb1[50*N],ksmb2[50*N];
inline int ksma(int x)
{	
	int t=x/(int)1e5,tt=x%(int)1e5;
	return ksma2[t]*ksma1[tt]%mod;
}
inline int ksmb(int x)
{
	int t=x/(int)1e5,tt=x%(int)1e5;
	return ksmb2[t]*ksmb1[tt]%mod;
}
signed main()
{
	freopen("satellite.in","r",stdin);
	freopen("satellite.out","w",stdout);
	cin>>n>>q>>w>>h>>mod>>a>>b;
	for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&p[i].h,&p[i].x,&p[i].y);
	for(int i=0;i<=1e5;i++)ksma1[i]=ksm(a,i),ksmb1[i]=ksm(b,i);
	for(int i=0;i<=1e9;i+=1e5){int pp=i/1e5;ksma2[pp]=ksm(a,i),ksmb2[pp]=ksm(b,i);}
	for(int i=1;i<=n;i++)lsh1[i]=p[i].x,lsh2[i]=p[i].y;
	sort(lsh1+1,lsh1+n+1);sort(lsh2+1,lsh2+1+n);
	int cnt1=unique(lsh1+1,lsh1+n+1)-lsh1-1;
	int cnt2=unique(lsh2+1,lsh2+n+1)-lsh2-1;
	for(int i=1;i<=n;i++)
	{	
		p[i].rk1=lower_bound(lsh1+1,lsh1+cnt1+1,p[i].x)-lsh1;
		p[i].rk2=lower_bound(lsh2+1,lsh2+cnt2+1,p[i].y)-lsh2;
	}
	lsh1[cnt1+1]=lsh1[cnt1];lsh2[cnt2+1]=lsh2[cnt2];
	for(int i=1;i<=n;i++)
	{
		int xx=p[i].rk1,yy=p[i].rk2;
		(sum1[xx][yy]+=p[i].h)%=mod;(sum2[xx][yy]+=p[i].h)%=mod;
		(sum3[xx][yy]+=p[i].h)%=mod;(sum4[xx][yy]+=p[i].h)%=mod;
	}	
	for(int i=1;i<=cnt1;i++)for(int j=1;j<=cnt2;j++)
	sum1[i][j]=(sum1[i-1][j]*ksma(lsh1[i]-lsh1[i-1])%mod+sum1[i][j-1]*ksmb(lsh2[j]-lsh2[j-1])%mod-
	sum1[i-1][j-1]*ksma(lsh1[i]-lsh1[i-1])%mod*ksmb(lsh2[j]-lsh2[j-1])%mod+mod+sum1[i][j])%mod;
	for(int i=cnt1;i>=1;i--)for(int j=1;j<=cnt2;j++)
	sum2[i][j]=(sum2[i+1][j]*ksma(lsh1[i+1]-lsh1[i])%mod+sum2[i][j-1]*ksmb(lsh2[j]-lsh2[j-1])%mod-
	sum2[i+1][j-1]*ksma(lsh1[i+1]-lsh1[i])%mod*ksmb(lsh2[j]-lsh2[j-1])%mod+mod+sum2[i][j])%mod;
	for(int i=1;i<=cnt1;i++)for(int j=cnt2;j>=1;j--)
	sum3[i][j]=(sum3[i-1][j]*ksma(lsh1[i]-lsh1[i-1])%mod+sum3[i][j+1]*ksmb(lsh2[j+1]-lsh2[j])%mod-
	sum3[i-1][j+1]*ksma(lsh1[i]-lsh1[i-1])%mod*ksmb(lsh2[j+1]-lsh2[j])%mod+mod+sum3[i][j])%mod;
	for(int i=cnt1;i>=1;i--)for(int j=cnt2;j>=1;j--)
	sum4[i][j]=(sum4[i+1][j]*ksma(lsh1[i+1]-lsh1[i])%mod+sum4[i][j+1]*ksmb(lsh2[j+1]-lsh2[j])%mod-
	sum4[i+1][j+1]*ksma(lsh1[i+1]-lsh1[i])%mod*ksmb(lsh2[j+1]-lsh2[j])%mod+mod+sum4[i][j])%mod;
	for(int i=1;i<=q;i++)
	{
		int x,y;scanf("%lld%lld",&x,&y);
		int ga1=lower_bound(lsh1+1,lsh1+cnt1+1,x)-lsh1;
		int ga2=lower_bound(lsh2+1,lsh2+cnt2+1,y)-lsh2;
		int ans=0;
		if(x-lsh1[ga1-1]>=0&&y-lsh2[ga2-1]>=0)ans=(ans+sum1[ga1-1][ga2-1]*ksma(x-lsh1[ga1-1])%mod*ksmb(y-lsh2[ga2-1])%mod)%mod;
		if(lsh1[ga1]-x>=0&&y-lsh2[ga2-1]>=0)ans=(ans+sum2[ga1][ga2-1]*ksma(lsh1[ga1]-x)%mod*ksmb(y-lsh2[ga2-1])%mod)%mod;
		if(x-lsh1[ga1-1]>=0&&lsh2[ga2]-y>=0)ans=(ans+sum3[ga1-1][ga2]*ksma(x-lsh1[ga1-1])%mod*ksmb(lsh2[ga2]-y)%mod)%mod;
		if(lsh1[ga1]-x>=0&&lsh2[ga2]-y>=0)ans=(ans+sum4[ga1][ga2]*ksma(lsh1[ga1]-x)%mod*ksmb(lsh2[ga2]-y)%mod)%mod;		
		printf("%lld\n",ans);
	}
	return 0;
}

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 显然也是我整的

咕

考试总结

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

码农公寓