Codeforces Round #578 (Div. 2) Solution-蒲公英云

A. Hotelier

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

直接模拟..

#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=2e5+7;
int n,a[17];
char s[N];
int main()
{
    n=read(); scanf("%s",s+1);
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='L')
        {
            for(int j=1;j<=10;j++) if(!a[j]) { a[j]=1; break; }
            continue;
        }
        if(s[i]=='R')
        {
            for(int j=10;j;j--) if(!a[j]) { a[j]=1; break; }
            continue;
        }
        a[s[i]-'0'+1]=0;
    }
    for(int i=1;i<=10;i++) printf("%d",a[i]);
    printf("\n");
    return 0;
}

B. Block Adventure

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

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

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

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

#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=107;
int T,n,m,K,a[N];
int main()
{
    T=read();
    while(T--)
    {
        n=read(),m=read(),K=read();
        for(int i=1;i<=n;i++) a[i]=read();
        int pos=1,flag=1;
        while(pos<n)
        {
            int t=max(a[pos+1]-K,0); m+=a[pos]-t;
            if(m<0) { flag=0; break; }
            pos++;
        }
        if(flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

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$，如果结果一样则联通

还是不懂就看代码吧….

#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$

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

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

看代码也挺容易看懂

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