模拟64 考试总结

2024-01-24 13:59:52

咕咕咕

考试经过

题目基本不会，于是猛冲暴力
T1看见同余不会，狂写部分分；T2看见字符串不会，哈希乱搞；T3看见矩阵不会，暴力走人；T4啥玩意看不懂，果断弃掉
60+70+30+0=160，算是冲满了，rk6

T1.三元组

其实压根不是个数论题。。。
你发现根本想不出任何数论技巧，所以考虑放弃而把它做成数据结构题
暴力枚举\(n^3\),发现左边的一次项是连续的，想怎么用这个性质
枚举中间的\(b\)，由于左边连续，所以会形成若干个\(0-k-1\)的区间，每有这样一个区间，右边所有的\(i^3\)一定能在左边找到对应的值，因为它覆盖了整个区间，直接累加答案就好。剩下不满的区间可以利用在值域上开树状数组维护，也算比较套路了
还是先插满，每次左移，维护，删除，记得取模边界注意一下

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=100050;
int n,k;
struct bit{
   int b[N];
   inline void cl(){memset(b,0,sizeof(b));}
   inline int lowbit(int x){return x&(-x);}
   inline void add(int x,int v){for(int i=x;i<=k;i+=lowbit(i))b[i]+=v;}
   inline int getsum(int p){int s=0;for(int i=p;i;i-=lowbit(i))s+=b[i];return s;}
   inline int get(int l,int r)
   {
   	if(l>r)return 0;
   	if(!l)return getsum(r);
   	return getsum(r)-getsum(l-1);
   }
}tr;
inline int gan(int x)
{
   int ga=x%k;
   if(ga)return ga;
   else return k;
}
signed main()
{
   freopen("exclaim.in","r",stdin);
   freopen("exclaim.out","w",stdout);
   int t;cin>>t;
   for(int T=1;T<=t;T++)
   {
   	scanf("%lld%lld",&n,&k);tr.cl();
   	for(int i=1;i<=n;i++)tr.add(gan(i*i*i),1);
   	int ans=0;
   	for(int i=1;i<=n;i++)
   	{	
   		int s=i/k,p=gan(i),ga=gan(i*i);
   		ans+=(s*(n-i+1));
   		if(p==k){tr.add(gan(i*i*i),-1);continue;}
   		int l=gan(ga+1),r=gan(ga+p);
   		if(l<=r)ans+=tr.get(l,r);
   		else ans+=tr.get(1,r)+tr.get(l,k); 
   		tr.add(gan(i*i*i),-1);
   	}
   	printf("Case %lld: %lld\n",T,ans);
   }
   return 0;
}

T2.简单的字符串

简单是因为可以哈希水过去，优化一下基本卡不掉
正解是用了结论，首先合法串一定可以变成形如\(uvvu\)的形式，循环同构性质
设前面的串是\(A\),后面为\(B\),结论是\(u,v\)必有一个是\(AB\)或\(BA\)的最长\(border\)
证明建议右转，%%%
如果是\(u\)的话可以利用 \(border\)理论，跳两次找到大于一半\(border\)的公差，再直接跳到小于等于一半的位置，复杂度是正确的
否则的话枚举中间点，向两边扩展，中间保持最长匹配，一直哈希就好了
总复杂度\(n^2\)，纯正解

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int N=5050;
ull h[N],ps[N];bool an[N][N];
int a[N],n,nxt[N][N];
ull get(int l,int r){if(l>r)return 0;return h[r]-h[l-1]*ps[r-l+1];}
signed main()
{
	freopen("s.in","r",stdin);
	freopen("s.out","w",stdout);
	cin>>n;int ans=0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	ps[0]=1;for(int i=1;i<=n;i++)ps[i]=ps[i-1]*13331;
	for(int i=1;i<=n;i++)h[i]=h[i-1]*13331+a[i];
	for(int i=1;i<=n;i++)
	{
		int p=i-1;nxt[i][i]=p;
		for(int j=i+1;j<=n;j++)
		{
			while(p>i-1&&a[j]!=a[p+1])p=nxt[i][p];
			if(a[j]==a[p+1])p++;
			nxt[i][j]=p;
		}
	}
	for(int i=1;i<n;i++)
	{
		int lmid=i,rmid=i+1,ll=lmid,rr=rmid;
		int lp=rmid,rp=lmid;
		while(ll>=1&&rr<=n)
		{
			if(get(ll,lmid)==get(rmid,rr))
			{
				lp=ll,rp=rr;
				an[ll][rr]=1;	
			}
			else
			{
				if(get(ll,lp-1)==get(rp+1,rr))
				an[ll][rr]=1;
			}
			ll--,rr++;
		}
	}
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j+=2)
		{
			if(an[i][j])continue;
			int lmid=(i+j)>>1,rmid=lmid+1;
			int nx1=nxt[i][j],nx2=nxt[i][nx1],ma;
			if(nx1<i)continue;
			if(nx1<=lmid)ma=nx1;
			else if(nx2<i)continue;
			else if(nx2<=lmid)ma=nx2;
			else 
			{
				int s=nx1-nx2,pp=nx1-((nx1-rmid+1)/s)*s;
				if(pp<=lmid)ma=pp;else ma=nxt[i][pp];
			}
			if(ma==lmid||get(ma+1,lmid)==get(rmid,j-(ma-i+1)))an[i][j]=1;
		}
	}
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j+=2)
	  if(an[i][j])ans++;
	cout<<ans<<endl;
	return 0;
}

T3.环路

考场时就想到了要做矩阵乘，每次算一遍对角线上答案之和再累加
现在优化显然应该快速幂，想能不能把答案存在某个地方

就这么配，扩大一倍，这样就把答案保存在了右上方1的位置，可以思考矩阵乘的实现过程
实现时可能稍微卡常

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=205;
char c[N][N];
int a[N][N],pp[N][N],p[N][N],n,m,k;
inline void mul()
{
	memset(pp,0,sizeof(pp));
	for(int i=1;i<=2*n;i++)
	 for(int k=1;k<=2*n;k++)
	 {
	  	if(!a[i][k])continue;
	  	for(int j=1;j<=2*n;j++)
	  	 pp[i][j]=(pp[i][j]+a[i][k]*p[k][j]%m)%m;
	 }
	memcpy(a,pp,sizeof(pp));
}
inline void gan()
{
	memset(pp,0,sizeof(pp));
	for(int i=1;i<=2*n;i++)
	 for(int k=1;k<=2*n;k++)
	 {
	 	if(!p[i][k])continue;
	 	for(int j=1;j<=2*n;j++)
	 	 pp[i][j]=(pp[i][j]+p[i][k]*p[k][j]%m)%m;
	 }
	memcpy(p,pp,sizeof(pp));
}
inline void ksm(int x)
{
	for(;x;x>>=1)
	{
		if(x&1)mul();
		gan();		
	}
}
signed main()
{	
	freopen("tour.in","r",stdin);
	freopen("tour.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)scanf("%s",c[i]+1);
	cin>>k>>m;
	for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
     if(c[i][j]=='Y')p[i][j]=1;
   memcpy(a,p,sizeof(p)); 
   for(int i=1;i<=n;i++)p[i][i+n]=p[i+n][i+n]=1;
   ksm(k-2);int ans=0;
   for(int i=1;i<=n;i++)ans=(ans+a[i][i]+a[i][i+n])%m;
	cout<<ans<<endl;
   return 0;
}

T4.过河

没改出来，咕

考试总结

时间还是分配好，总体在预期之内
暴力和正解有时差不了多少，关键是思维能不能上去
要把状态保持住

码农公寓