A.矩阵
hash好题啊,一眼看是二维hash,但我不会。怎么办?
我只好用洛谷子矩阵的思路,先求出每行的hash值, 再每列把行的hash值hash一下。
对于边长,我们采用二分,显然有单调性。矩阵越小越容易判匹配,越大越不容易匹配
时间复杂度n^2log(n)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1005;
const int base=31;
const int base2=127;
int n,m,cnt,l,r,mid,hs3[N],has[N*N],p[N],p2[N],a[N][N],hs[N][N],hs2[N][N];
bool pd(int x)
{
for(int i=1;i<=n;i++)
for(int j=x;j<=m;j++)hs2[i][j]=hs[i][j]-hs[i][j-x]*p[x];
cnt=0;
for(int j=x;j<=m;j++)
{
for(int i=1;i<=n;i++)hs3[i]=hs3[i-1]*base2+hs2[i][j];
for(int i=x;i<=n;i++)has[++cnt]=hs3[i]-hs3[i-x]*p2[x];
}
sort(has+1,has+cnt+1);
for(int i=2;i<=cnt;i++)
if(has[i]==has[i-1])return true;
return false;
}
signed main()
{
scanf("%lld%lld",&n,&m);
char c[N][N];
for(int i=1;i<=n;i++)
{
scanf("%s",c[i]+1);
for(int j=1;j<=m;j++)a[i][j]=c[i][j]-'a';
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)hs[i][j]=hs[i][j-1]*base+a[i][j];
p[0]=1;p2[0]=1;
for(int i=1;i<=max(n,m);i++)p[i]=p[i-1]*base;
for(int i=1;i<=max(n,m);i++)p2[i]=p2[i-1]*base2;
l=0;r=min(n,m);
while(l<r)
{
mid=(l+r+1)/2;
if(pd(mid))l=mid;
else r=mid-1;
}
cout<<l;
return 0;
}
B.树
一眼我还以为是树形dp题,后来发现就是简单的一个dp。
我们发现对于一个点u,它的颜色不仅取决于他的父亲,还取决于他的兄弟。
我们把树上的点编号,发现第i个点的颜色取决于第i-1个点的颜色。
表示前i个点,用j种颜色的方案数。
时间复杂度nm
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int p=1e9+7;
int n,m,ans,f[305][305];
signed main()
{
scanf("%lld%lld",&n,&m);
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)f[i][j]=(f[i-1][j]+f[i-1][j-1]*(m-j+1)%p)%p;
for(int i=1;i<=m;i++)ans=(ans+f[n][i])%p;
cout<<ans;
}
C.圈圈
没有看错,不要怀疑,这又是到hash题
我们发现一旦有数加1模m后等于0,那么以这个数开头的队列就是最小的之一
(因为不止有一个数加1模m后等于0)
那判大小怎么解决呢?hash+二分,二分找到lcp,就可以判断大小了。(常规操作)
当然,如果有大佬想用后缀数组或后缀自动机也完全可以
时间复杂度(mlog(n))
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
const int base=1e9+7;
int n,m,k,l,r,ans,mid,a[N],ha[N],p[N];
vector<int>v[N];
int bj(int x,int y,int add)
{
l=0;r=n;
while(l<r)
{
mid=(l+r+1)/2;
if(ha[x+mid-1]-ha[x-1]*p[mid]==ha[y+mid-1]-ha[y-1]*p[mid])l=mid;
else r=mid-1;
}
if(l==n)return x;
if((a[x+l]+add)%m<=(a[y+l]+add)%m)return x;
return y;
}
signed main()
{
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
v[m-a[i]].push_back(i);
a[i+n]=a[i];
}
for(int i=1;i<=n+n;i++)ha[i]=ha[i-1]*base+a[i];
p[0]=1;
for(int i=1;i<=n+n;i++)p[i]=p[i-1]*base;
ans=1;
for(int i=2;i<=n;i++)ans=bj(ans,i,0);
printf("%lld\n",a[ans+k-1]);
for(int i=1;i<m;i++)
{
if(v[i].size())
{
ans=v[i][0];
for(int j=1;j<v[i].size();j++)ans=bj(ans,v[i][j],i);
}
printf("%lld\n",(a[ans+k-1]+i)%m);
}
return 0;
}
全部评论
(2) 回帖