Codeforces Round #578 (Div. 2) 题解

题解 比赛-Codeforces
题目链接 编辑文章

这次我只过了三道,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;
}

新评论

称呼不能为空
邮箱格式不合法
网站格式不合法
内容不能为空

第一次提交的评论将在审核后显示。

    游客
    游客
    2019-08-12 13:10

    E题也好做,哈希...但是没时间写了

      Llf0703
      2019-08-12 14:05

      orz

      duanyll
      2019-08-16 21:16

      CF上写hash不是坐等被叉吗

        Llf0703
        2019-08-16 21:25

        运气好可能不会。比如一room全是我这种最后1min还在写题的辣鸡

    bwt
    2019-08-15 13:31

    Orz