Codeforces Round #568 (Div. 2)网卡&垫底记

这场和div3差不多嘛（后来发现就是div3），就是网太卡10min交一发就不错了，简直自闭。

签到。

记录每一段的字母数，满足条件即：段数相同+字母相同+字母数下>=上。

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+;

char a[N],b[N];

int n,m,n1,n2,c1[N],s1[N],c2[N],s2[N];

bool check()

{

    int now=;

    n1=n2=;

    for(int i=;i<=n;i++)if(i==||a[i]!=a[i-])c1[++n1]=a[i],s1[n1]=;

    else s1[n1]++;

    for(int i=;i<=m;i++)if(i==||b[i]!=b[i-])c2[++n2]=b[i],s2[n2]=;

    else s2[n2]++;

    if(n1!=n2)return ;

    for(int i=;i<=n1;i++)if(c1[i]!=c2[i]||s1[i]>s2[i])return ;

    return ;

}

int main()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        scanf("%s",a+),n=strlen(a+);

        scanf("%s",b+),m=strlen(b+);

        if(check())puts("YES");else puts("NO");

    }

}

签到。不知设成C1和C2除了卡网速还有什么意义？根据ti<=100，直接数组维护每种t出现的次数，然后从大到小贪心删。不知为啥这签到题有人用treap？还T了？

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+;

int n,m,a[N],s[N],num[];

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)scanf("%d",&a[i]),s[i]=s[i-]+a[i];

    for(int i=;i<=n;i++)

    if(s[i]<=m)printf("0 "),num[a[i]]++;

    else{

        int rest=s[i]-m,ans=;

        for(int j=;j;j--)if(j*num[j]<rest)rest-=j*num[j],ans+=num[j];

        else{ans+=(rest+j-)/j;break;}

        printf("%d ",ans);

        num[a[i]]++;

    }

}

把数列排个序，讨论删队头和队尾，其余的差分维护下即可。忘讨论还WA了两发。

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+;

struct node{int id,v;}a[N];

int n,d[N],l[N],r[N];

bool cmp(node a,node b){return a.v<b.v;}

bool judge1()

{

    for(int i=;i<n;i++)if(d[i]!=d[])return ;

    return ;

}

bool judge2()

{

    for(int i=;i<n-;i++)if(d[i]!=d[])return ;

    return ;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i].v),a[i].id=i;

    sort(a+,a+n+,cmp);

    for(int i=;i<n;i++)d[i]=a[i+].v-a[i].v;

    if(judge1()){printf("%d",a[].id);return ;}

    if(judge2()){printf("%d",a[n].id);return ;}

    l[]=;for(int i=;i<n;i++)if(d[i]==d[i-])l[i]=;else break;

    r[n-]=;for(int i=n-;i;i--)if(d[i]==d[i+])r[i]=;else break;

    if(r[]&&d[]+d[]==d[]){printf("%d",a[].id);return ;}

    if(l[n-]&&d[n-]+d[n-]==d[n-]){printf("%d",a[n-].id);return ;}

    for(int i=;i<=n-;i++)if(l[i-]&&r[i+]&&d[]==d[n-]&&d[i-]+d[i]==d[])

    {printf("%d",a[i].id);return ;}

    puts("-1");

}

写&交这题时网均卡了至少10min，导致我被Gloid吊打（虽然不卡还是被吊打）。就是每种字母分别枚举一下，然后直接做即可。

#include<bits/stdc++.h>

using namespace std;

const int N=;

int n,m,r1[],c1[],r2[],c2[],hr[N],hc[N];

char mp[N][N];

bool judge(int x)

{

    int sr=,sc=;

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    if(mp[i][j]=='a'+x-)

    {

        if(!hr[i])hr[i]=,sr++;

        if(!hc[j])hc[j]=,sc++;

    }

    if(sr>&&sc>)return ;

    if(!sr&&!sc){r1[x]=r2[x]=r1[x+],c1[x]=c2[x]=c1[x+];return ;}

    if(sr==&&sc==)

    {

        for(int i=;i<=n;i++)if(hr[i])hr[i]=,r1[x]=r2[x]=i;

        for(int i=;i<=m;i++)if(hc[i])hc[i]=,c1[x]=c2[x]=i;

        return ;

    }

    if(sr==)

    {

        for(int i=;i<=n;i++)if(hr[i])r1[x]=r2[x]=i;

        for(int i=;i<=m;i++)if(mp[r1[x]][i]=='a'+x-){c1[x]=i;break;}

        for(int i=m;i;i--)if(mp[r1[x]][i]=='a'+x-){c2[x]=i;break;}

        for(int i=c1[x];i<=c2[x];i++)if(mp[r1[x]][i]<'a'+x-)return ;

    }

    if(sc==)

    {

        for(int i=;i<=m;i++)if(hc[i])c1[x]=c2[x]=i;

        for(int i=;i<=n;i++)if(mp[i][c1[x]]=='a'+x-){r1[x]=i;break;}

        for(int i=n;i;i--)if(mp[i][c1[x]]=='a'+x-){r2[x]=i;break;}

        for(int i=r1[x];i<=r2[x];i++)if(mp[i][c1[x]]<'a'+x-)return ;

    }

    for(int i=r1[x];i<=r2[x];i++)hr[i]=;

    for(int j=c1[x];j<=c2[x];j++)hc[j]=;

    return ;

}

int main()

{

    int T;scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)hr[i]=;

        for(int j=;j<=m;j++)hc[j]=;

        for(int i=;i<=n;i++)scanf("%s",mp[i]+);

        int mx=;

        for(int i=;i<=n;i++)

        for(int j=;j<=m;j++)

        if(mp[i][j]>='a'&&mp[i][j]<='z')mx=max(mx,mp[i][j]-'a'+);

        if(!mx){puts("YES\n0");continue;}

        for(int i=mx;i;i--)if(!judge(i)){mx=;break;}

        if(!mx){puts("NO");continue;}

        printf("YES\n%d\n",mx);

        for(int i=;i<=mx;i++)printf("%d %d %d %d\n",r1[i],c1[i],r2[i],c2[i]);

    }

}

签到，把每种馅料压缩成一个二进制位，枚举。这根本不能称之为题目。

#include<bits/stdc++.h>

using namespace std;

int n,m,ans,ans1,ans2,a[],mn[],id[];

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

    {

        int x,y,S=;scanf("%d",&x);

        while(x--)scanf("%d",&y),S|=<<y-;

        a[S]++;

    }

    for(int i=;i<;i++)mn[i]=1e9+;

    for(int i=;i<=m;i++)

    {

        int c,x,y,S=;scanf("%d%d",&c,&x);

        while(x--)scanf("%d",&y),S|=<<y-;

        if(mn[S]>c)mn[S]=c,id[S]=i;

    }

    ans=-;

    for(int i=;i<;i++)

    for(int j=i+;j<;j++)

    if(mn[i]<1e9+&&mn[j]<1e9+)

    {

        int sum=;

        for(int k=;k<;k++)if(((i|j)&k)==k)sum+=a[k];

        if(sum>ans)ans=sum,ans1=i,ans2=j;

        else if(sum==ans&&mn[ans1]+mn[ans2]>mn[i]+mn[j])ans1=i,ans2=j;

    }

    if(ans==-)puts("1 2");

    else printf("%d %d",id[ans1],id[ans2]);

}

G1裸状压DP即可，不知这G1给2750分是啥意思？

咕了的G2终于写了。看大佬们各种常数小的暴力跑过，我也来写了一发暴力。注意g[i]<=3，可以考虑把其拆成3个背包，f[0/1/2][i][j]表示第0/1/2类，选了i件物品，体积和为j的方案数，直接暴力DP即可。然后可以枚举前两个背包的i和j，第三个背包的k，然后只需要预处理出s[i][j][k]表示每一类分别是i、j、k个物品的合法排列方案数，复杂度O(T^2*n^3)，准确说是O(T^2*n^3/54)≈O(T^2*n^2)，但是中途搜索排除了一些dp值为0的情况，所以实际复杂度明显比这小。

#include<bits/stdc++.h>

using namespace std;

const int N=,mod=1e9+;

int n,T,ans,f[][N][N*N],g[][N][N][N],s[N][N][N],fac[N];

vector<int>G[];

void add(int&x,int y){x=x+y>=mod?x+y-mod:x+y;}

int main()

{

    scanf("%d%d",&n,&T);

    fac[]=;for(int i=;i<=n;i++)fac[i]=1ll*fac[i-]*i%mod;

    s[][][]=g[][][][]=g[][][][]=g[][][][]=;

    for(int i=;i<n;i++)

    for(int j=;i+j<n;j++)

    for(int k=;i+j+k<n;k++)

    for(int l=;l<;l++)

    if(g[l][i][j][k])

    {

        if(l!=)add(g[][i+][j][k],g[l][i][j][k]);

        if(l!=)add(g[][i][j+][k],g[l][i][j][k]);

        if(l!=)add(g[][i][j][k+],g[l][i][j][k]);

    }

    for(int i=;i<=n;i++)

    for(int j=;i+j<=n;j++)

    for(int k=;i+j+k<=n;k++)

    if(i||j||k)

    s[i][j][k]=(1ll*g[][i][j][k]+g[][i][j][k]+g[][i][j][k])%mod*fac[i]%mod*fac[j]%mod*fac[k]%mod;

    for(int i=,x,y;i<=n;i++)scanf("%d%d",&x,&y),G[y-].push_back(x);

    for(int i=;i<;i++)

    {

        f[i][][]=;

        for(int p=;p<G[i].size();p++)

        {

            int t=G[i][p];

            for(int j=G[i].size()-;~j;j--)

            for(int k=;k<=T-t;k++)add(f[i][j+][k+t],f[i][j][k]);

        }

    }

    for(int i=;i<=G[].size();i++)

    for(int t0=;t0<=T;t0++)

    if(f[][i][t0])

    for(int j=;j<=G[].size();j++)

    for(int t1=;t0+t1<=T;t1++)

    if(f[][j][t1])

    for(int k=;k<=G[].size();k++)

    if(f[][k][T-t0-t1])

    add(ans,1ll*f[][i][t0]*f[][j][t1]%mod*f[][k][T-t0-t1]%mod*s[i][j][k]%mod);

    printf("%d",ans);

}

强烈谴责出题人，这题目难度排列顺序十分不合理。其实本场CF要是作为div2，应该删了C1、F和G1才正常，不过毕竟本来是作为div3的嘛，怪自己打完才发现。

result：rank37，以为上不了橙结果rating=2106，压线上橙，好啊好啊。不过rank1的Gloid（即poorinenglish）不知道为啥被ban了？

感觉这场就是比网速+开题顺序的。先开F/G1的人赢了。幸好这是小号吧（不过大号都unrated也无所谓了）。

巴特西

Codeforces Round #568 (Div. 2)网卡&垫底记

最新文章

热门文章