Codeforces Round #578 (Div. 2)

C - Round Corridor

题意：给两个圆环套在一起，将1圆环分成n份，2圆环分成m份，分开的部分为墙，不可通过，q组询问，问两个圆环上任意位置是否可到达。

思路：可以发现影响联通块的只有两个圆环的墙重叠时，也就是大墙。然后可以想到n，m的最大公约数为大墙的个数，那么n/gcd(n,m),m/gcd(n,m)就是每两个大墙之间的划分个数，然后判断两个点是否在一起就是判断这两个点所在的逆时针方向的上一个大墙是否相同就可以了。

#include<bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main()
{
    ll n,m,q;
    scanf("%lld%lld%lld",&n,&m,&q);
    ll gd=__gcd(n,m);
    ll nn=n/gd;
    ll mm=m/gd;
    while(q--)
    {
        ll sx,sy,ex,ey;
        scanf("%lld%lld%lld%lld",&sx,&sy,&ex,&ey);
        ll q1,q2;
        if(sx==1)
        {
            if(sy%nn==0)
                q1=sy/nn-1;
            else
                q1=sy/nn;
        }
        else
        {
            if(sy%mm==0)
                q1=sy/mm-1;
            else
                q1=sy/mm;
        }
        if(ex==1)
        {
            if(ey%nn==0)
                q2=ey/nn-1;
            else
                q2=ey/nn;
        }
        else
        {
            if(ey%mm==0)
                q2=ey/mm-1;
            else
                q2=ey/mm;
        }
        if(q1==q2)
            printf("YES
");
        else
            printf("NO
");
    }
}

View Code

D. White Lines

题意：给n*n的网格，每个网格B,W代表黑色白色，现在要在里面选择一个大小为k*k的网格将其全部变白，问最多行和列产生多少白色条，白色条表示一行或一列全为白。

思路：统计每个点作为矩形的左上角顶点对增加白条的贡献。

#include<bits/stdc++.h>
using namespace std;

char a[2005][2005];
int ans[2005][2005];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        scanf("%s",a[i]+1);
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        int b,e;
        b=e=-1;
        for(int j=1; j<=n; j++)
        {
            if(a[i][j]=='B')
            {
                if(b==-1) b=j;
                e=j;
            }
        }
        if(b==-1)
        {
            cnt++;continue;
        }
        if(e-b+1>k) continue;
        for(int ii=max(1,i-k+1); ii<=i; ii++)
            for(int jj=max(1,e-k+1); jj<=b; jj++)
            {
                ans[ii][jj]++;
            }
    }
    for(int j=1; j<=n; j++)
    {
        int b,e;
        b=e=-1;
        for(int i=1; i<=n; i++)
        {
            if(a[i][j]=='B')
            {
                if(b==-1) b=i;
                e=i;
            }
        }
        if(b==-1)
        {
            cnt++;continue;
        }
        if(e-b+1>k) continue;
        for(int ii=max(1,e-k+1); ii<=b; ii++)
            for(int jj=max(1,j-k+1); jj<=j; jj++)
            {
                ans[ii][jj]++;
            }
    }
    int maxx=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            maxx=max(maxx,ans[i][j]);
    printf("%d
",maxx+cnt);
}

View Code

E. Compress Words

题意：给n个字符串，从左到右，1和2串合并然后结果和3合并，类推..合并规则是左边串后缀和右边串的前缀的最长公共部分要去掉。

思路：Kmp,对于每个右边的字串a预处理nxt[],之后和只需要和主串b下标为lenb-lena+1~lenb的位置比较找出最长公共长度即可。

注意：这题一开始一直超时，以为是不够优化，后来才想到，每次for时如果都要来一次strlen判断主串长度会很费时，所以lenb的长度直接累加就好，不要每次计算。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int nxt[maxn];
int f[maxn];
char a[maxn];
char b[maxn];
int lena,lenb;
void getnxt() // a是子串b是主串
{
    nxt[1]=0;
    for(int i=2,j=0; i<=lena; i++)
    {
        while(j>0&&a[i]!=a[j+1]) j=nxt[j];
        if(a[i]==a[j+1]) j++;
        nxt[i]=j;
    }
}
void kmp()
{
    int i,j;
    for(i=lenb-lena+1,j=0; i<=lenb; i++)
    {
        while(j>0&&(j==lena||b[i]!=a[j+1])) j=nxt[j];
        if(b[i]==a[j+1]) j++;
        if(j==lena) break;
    }
    for(int i=1; i<=lena-j; i++)
        b[lenb+i]=a[j+i];
    lenb+=lena-j;
}
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",b+1);
    lenb=strlen(b+1);
    for(int i=1; i<=n-1; i++)
    {
        scanf("%s",a+1);
        lena=strlen(a+1);
        getnxt();
        kmp();
    }
    printf("%s",b+1);
}

View Code