竞赛讨论区 > 【题解】牛客练习赛1题解

【题解】牛客练习赛1题解

头像
xuxuxuxuxu
编辑于 2019-04-10 15:00:29 APP内打开
赞 10 | 收藏 9 | 回复3 | 浏览73265

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;
}

3条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐