Codeforces Round #578 (Div. 2) 题解

这次我只过了三道，D题因为最后统计答案时越界而 Wrong answer on pretest 12 ，结束后把两个 n 改成 n-k+1 就过了，我真是傻逼。

代码都是考场代码，所以很丑，凑合看吧。

A. Hotelier

题意

有 $10$ 个房间，客人可能从左边或右边进来，进来后给客人安排最近的房间。可能有人离开。给出 $N$ 个操作，要求输出操作后每个房间是否有人。

$N\le 10^5$

题解

膜你水题。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

bool vis[10];
char s[100005];
int n,left,right;

signed main()
{
    n=read();
    scanf("%s",s+1);
    for (int i=1;i<=n;i++)
    {
        if (s[i]=='L')
        {
            for (int j=0;j<=9;j++) if (!vis[j]) { vis[j]=1; break; }
        }
        else if (s[i]=='R')
        {
            for (int j=9;~j;j--) if (!vis[j]) { vis[j]=1; break; }
        }
        else vis[s[i]-'0']=0;
    }
    for (int i=0;i<=9;i++) cout<<vis[i];
    return 0;
}

B. Block Adventure

题意

有 $N$ 堆方块，每堆的高度为 $H_i$ 。一个人要从 $1$ 走到 $N$ ，他有一个无限大的袋子，最开始装有 $M$ 个方块。当他站在某个堆上时，可以把当前堆取出或放上一些方块。能从 $i\rightarrow i+1$ 要求 $|H_i-H_{i+1}|\le k$ ，问他能否到达 $N$ 。

$N\le 100$ 。多组数据，组数 $T\le 1000$ 。

题解

贪心。拿就尽量多拿，放就尽量少放。

注意当前堆只能取到 $0$ ，即最多取 $H_i$ 个。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int t,n,m,k,h[105];

signed main()
{
    t=read();
    while (t--)
    {
        n=read(); m=read(); k=read();
        for (int i=1;i<=n;i++) h[i]=read();
        bool flag=1;
        for (int i=1;i<n;i++)
        {
            m+=min(h[i],h[i]-h[i+1]+k);
            if (m<0) { puts("NO"); flag=0; break; }
        }
        if (flag) puts("YES");
    }
    return 0;
}

C. Round Corridor

题意

有内外两层圆环，内环和外环分别被等分为 $N$ 个和 $M$ 个。同一层的分隔区域有墙，内外两层之间没有墙。询问 $Q$ 次，给出起点和终点，问能否到达。

$N,M\le 10^{18} \ , \ Q\le 10^4$ 。

题解

令 $G=\gcd(N,M)$ ，可以发现整个图形被分成了 $G$ 块，每一块内可达。

那么只需要判断询问是否在同一块即可。当 $S_x=1$ 时，显然起点所属块为 $\lfloor \dfrac{S_y-1}{\dfrac{N}{G}} \rfloor +1$ ，另一种情况和终点同理。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,m,q,sx,sy,ex,ey;

ll gcd(ll x,ll y) { return y ? gcd(y,x%y) : x; }

signed main()
{
    n=read(); m=read(); q=read();
    ll g=gcd(n,m);
    n/=g; m/=g;
    for (ll i=1;i<=q;i++)
    {
        sx=read(); sy=read(); ex=read(); ey=read();
        ll sid,eid;
        if (sx==1) sid=(sy-1)/n+1;
        else sid=(sy-1)/m+1;
        if (ex==1) eid=(ey-1)/n+1;
        else eid=(ey-1)/m+1;
        puts(sid==eid ? "YES" : "NO");
    }
    return 0;
}

D. White Lines

题意

有一个 $N\times N$ 的矩阵，格点有黑白两种颜色。现在可以把 $K\times K$ 的矩形染白，求最多有多少行和列全为白色。

$K\le N\le 2000$ 。

题解

先只考虑行的情况。

用 $s[i][j]$ 存下图的情况，黑色为 $1$ ，白色为 $0$ ，然后对行作前缀和为 $x[i][j]$ 。

这样就可以预处理出在第 $i$ 行，如果选择 $j$ 为左上角，能否把当前行染白。具体方法是判断 $[j,j+k-1]$ 这段区间是否包含了这一行所有的黑色格点，即 $x[i][j+k-1]-x[i][j-1]=x[i][n]$ 。将结果记录在 $vx[i][j]$ 。

然后将 $vx[i][j]$ 作列上的前缀和，记录为 $vxs[i][j]$ 。

可以纵向统计出如果以 $(i,j)$ 为左上角，可以染白的行有多少个。具体的方法为将 $[i,i+k-1]$ 区间上所有的 $vx[i][j]$ 加起来，即 $vxs[i+k-1][j]-vxs[i-1][j]$ ，把这个值重新赋给 $vx[i][j]$ 。

列的情况同理，最后记录在 $vy[i][j]$ 。

答案即为 $\max (vx[i][j]+vy[i][j])$ 。注意最后统计的时候上界一定是 $n-k+1$ ，我就因为这个导致 Wrong answer on pretest 12 ，然后结束了才过的。

还有如果某行或列最开始就是白色，那就把它统计进 $cnt$ ，然后在统计 $vx$ 时就跳过。最后把 $cnt$ 加进答案。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

char ch[2005];
int n,k,s[2005][2005],x[2005][2005],y[2005][2005],vx[2005][2005],vy[2005][2005],vxs[2005][2005],vys[2005][2005];

signed main()
{
    n=read(); k=read();
    for (int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for (int j=1;j<=n;j++)
        {
            s[i][j]=ch[j]=='B';
            x[i][j]=x[i][j-1]+s[i][j];
        }
    }
    for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) y[i][j]=y[i-1][j]+s[i][j];
    int cnt=0; //最开始就为白线的个数
    for (int i=1;i<=n;i++)
    {
        if (x[i][n]==0) { cnt++; continue; } //最开始就为白线，跳过
        for (int j=1;j<=n;j++)
        {
            if (x[i][j+k-1]-x[i][j-1]==x[i][n]) vx[i][j]++;
        }
    }
    for (int j=1;j<=n;j++)
    {
        if (y[n][j]==0) { cnt++; continue; }
        for (int i=1;i<=n;i++)
        {
            if (y[i+k-1][j]-y[i-1][j]==y[n][j]) vy[i][j]++;
        }
    }
    for (int j=1;j<=n;j++)
    {
        for (int i=1;i<=n;i++)
        {
            vxs[i][j]=vxs[i-1][j]+vx[i][j]; //vxs是vx的前缀和
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            vys[i][j]=vys[i][j-1]+vy[i][j];
        }
    }
    for (int j=1;j<=n;j++)
    {
        for (int i=1;i<=n-k+1;i++)
        {
            vx[i][j]=vxs[i+k-1][j]-vxs[i-1][j]; //把连续k个的和赋回来
        }
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n-k+1;j++)
        {
            vy[i][j]=vys[i][j+k-1]-vys[i][j-1];
        }
    }
    int ans=0;
    for (int i=1;i<=n-k+1;i++) for (int j=1;j<=n-k+1;j++) ans=max(ans,vx[i][j]+vy[i][j]); //统计答案
    cout<<ans+cnt<<endl;
    return 0;
}