Codeforces Round #578 (Div. 2) Solution

向右看齐 2021-10-29 09:30 206阅读 0赞

[A. Hotelier][]

题意：有十个位置初始为 $0$，三种操作，找到左边第一个空位，变成 $1$，找到右边第一个空位，变成 $1$，把某个位置变成 $0$

直接模拟..

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[B. Block Adventure][]

题意：有一些位置，每个位置有一些方块，你一开始在最左边的方块上，每次可以把当前位置的一个方块放到背包，从背包里拿一个方块叠到当前位置，背包容量无限

如果右边的下一个位置和当前位置方块数差值小于等于 $K$，你也可以选择移动到右边的下一个位置

多组数据，给定初始状态，问是否能到最右边

直接贪心，每到一个位置都把当前位置的方块拿到刚好能到下一个位置，如果不够才用背包的方块来垫，然后注意不能把一个位置的方块拿成负数就行了

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

[C. Round Corridor][]

题意：给一个圆环，分成内外两层，两层分别被墙均分成 $n,m$ 段，如果某个位置内外层都有墙则不能通过（可以参考题目的图）

多次询问位置问是否联通

首先内层分成 $n$ 段，那么每段角度为 $x=2 \\pi /n$，外层同理每段角度 $y=2 \\pi /m$，如果某个位置内外都有墙则有 $ax=by$

代入得 $a/n=b/m$ 即 $am=bn$ 所以内层每 $n/\\gcd(n,m)$ 段，外层每 $m/\\gcd(n,m)$ 段就出现此位置都有墙

所以根据内外层直接把位置整除 $n$ 或 $m$，如果结果一样则联通

还是不懂就看代码吧....

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    inline ll read()
    {
        ll x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    ll n,m,Q;
    ll gcd(ll a,ll b) { return b ? gcd(b,a%b) : a; }
    int main()
    {
        n=read(),m=read(); Q=read();
        ll a,b,c,d,G=gcd(n,m); n/=G; m/=G;
        while(Q--)
        {
            a=read(),b=read(),c=read(),d=read();
            if(a==1&&c==1)
            {
                if((b-1)/n==(d-1)/n) printf("YES\n");
                else printf("NO\n");
                continue;
            }
            if(a==2&&c==2)
            {
                if((b-1)/m==(d-1)/m) printf("YES\n");
                else printf("NO\n");
                continue;
            }
            if(a==1&&c==2)
            {
                if((b-1)/n==(d-1)/m) printf("YES\n");
                else printf("NO\n");
                continue;
            }
            if(a==2&&c==1)
            {
                if((b-1)/m==(d-1)/n) printf("YES\n");
                else printf("NO\n");
            }
        }
        return 0;
    }

[D. White Lines][]

题意：给一个矩阵每个位置非黑即白，定义白线为整行或整列都是白色的行或列

你可以进行一次操作把一个给定大小为 $K$ 的矩形全部变成白色

求一次操作以后白线的最大数量，矩阵大小 $n<=2000$

考虑每一行如何对答案产生贡献，如果本来就没黑的那就直接加就好了

如果此行最左边和最右边黑色块的位置差大于 $K$ 则此行不能产生贡献

否则我们可以发现只有当小矩形在某些位置的时候操作才能使此行最左边和最右边的黑色块都变白，才能对答案产生贡献

显然这些操作位置同样是的矩形区域

考虑维护 $ans\[i\]\[j\]$ ，表示变白操作的左上角为 $i,j$ 时的答案

对原本每一行，对 $ans$ 的贡献就是一个矩形区域，即当操作位置在这个矩形内时，最终答案 $+1$

对于列的情况也同样考虑即可

这个东西直接二维前缀和维护，先预处理好，最后枚举所有位置看看哪个答案最大即可

看代码也挺容易看懂

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=2007;
    int n,K,D[N][N],S[N][N];
    char s[N][N];
    int main()
    {
        n=read(),K=read();
        for(int i=1;i<=n;i++)
            scanf("%s",s[i]+1);
        int L,R,u,d,l,r;
        for(int i=1;i<=n;i++)//行的贡献
        {
            L=R=0;
            for(int j=1;j<=n;j++)
                if(s[i][j]!='W') (!L) ? L=R=j : R=j;
            if(!L) { D[1][1]++; continue; }
            if(R-L+1<=K)
            {
                u=max(1,i-K+1),d=i,l=max(1,R-K+1),r=L;
                D[u][l]++; D[d+1][l]--; D[u][r+1]--; D[d+1][r+1]++;//容斥一下
            }
        }
        for(int j=1;j<=n;j++)//列的贡献
        {
            L=R=0;
            for(int i=1;i<=n;i++)
                if(s[i][j]!='W') (!L) ? L=R=i : R=i;
            if(!L) { D[1][1]++; continue; }
            if(R-L+1<=K)
            {
                u=max(1,R-K+1),d=L,l=max(1,j-K+1),r=j;
                D[u][l]++; D[d+1][l]--; D[u][r+1]--; D[d+1][r+1]++;
            }
        }
        int ans=0;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
            {
                S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+D[i][j];//二维前缀和
                ans=max(ans,S[i][j]);
            }
        printf("%d\n",ans);
        return 0;
    }

[E. Compress Words][]

真的心累，想先写 $E$ 然后调不出来，结果 $D$ 都没时间写了，直接翻车

这题看样例都知道什么意思了...懒得翻译了

两种做法，$Hash$ 或者 $KMP$

关键思路都一样，对每个串的后缀都暴力枚举长度并和下一个串的前缀比较

如果我们能做到每次都是 $O(1)$ 比较，那么因为每个串只会作为前面和后面各出现一次所以复杂度 $O(strlen)$

$O(1)$ 显然考虑哈希就行，比赛时也是这样写...然后就很不好调，因为 $CF$ 很卡哈希所以建议至少双哈希（当然越多越好，只要不超时）

并且千万不要自然溢出，绝对被卡死...

$KMP$ 做法就是，本来要比较 $x$ 的后缀和 $y$ 的前缀，我们设 $z=y+x$

这样比较 $y$ 的前缀和 $x$ 的后缀，就是比较 $z$ 的前缀和 $z$ 的后缀，直接 $KMP$ 就完事了

注意每次我们每次比较的是 前面一堆串的结果 $x$ 和 下一个串 $y$，注意不能前一个串直接和后一个串比较，原因显然

那么比较的时候前面的串可能很长，所以只要取 $x$ 后面的和 $y$ 长度一样的一段就行了

那么复杂度就是 $O(n)$

代码调不动了，自己加油吧 $qwq$

[F. Graph Traveler][]

还没看......好像是个图论

看完题解了，好像是个模意义下搞搞 $dp$，然后模拟一波

转载于:https://www.cnblogs.com/LLTYYC/p/11343421.html

[A. Hotelier]: http://codeforces.com/contest/1200/problem/A
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/dacf73e62b314f77a67c92c9c7c73fd7.png
[B. Block Adventure]: http://codeforces.com/contest/1200/problem/B
[C. Round Corridor]: http://codeforces.com/contest/1200/problem/C
[D. White Lines]: http://codeforces.com/contest/1200/problem/D
[E. Compress Words]: http://codeforces.com/contest/1200/problem/E
[F. Graph Traveler]: http://codeforces.com/contest/1200/problem/F