CodeForces Round #578 Div2 题解

/ 0评 / 3

Codeforces Round #578 (Div. 2)

D - White Lines

Description

*1900

给出一个 n\ast m 的黑白矩阵,你可以将一块 k\ast k 的矩形全部变成白色。
问你执行一次上述染色之后,全空白的行和全空白的列数量总和的最大值。

数据范围:n,m\leq 2000

Solution

Fl(i,j) 表示擦除了第 ij 列开始横着的 k 个格子之后这一行是否能为空;
Fc(i,j) 表示擦除了第 ij 列开始竖着的 k 个格子之后这一列是否能为空;

对这两个做前缀和,然后枚举左上角即可。

Code

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

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

int read_ch(){
    char ch=getchar();
    while (ch!='B' && ch!='W') ch=getchar();
    return ch=='B';
}

const int maxn=2005;
int n,k,ben=0,ans=0;
int a[maxn][maxn];

int fl[maxn][maxn],suml[maxn][maxn];
int fc[maxn][maxn],sumc[maxn][maxn];

signed main(){
    n=read(); k=read();
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            a[i][j]=read_ch();

    for (int i=1;i<=n;i++){
        int tl=-1,tr=-1;
        for (int j=1;j<=n;j++) if (a[i][j]) {tl=j;break;}
        for (int j=n;j>=1;j--) if (a[i][j]) {tr=j;break;}
        if (tl==-1){
            ben++;
            continue;
        }
        if (tr-tl+1 > k) continue;
        for (int j=tl-(k-(tr-tl+1));j<=tl;j++) fl[i][j]=1;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n-k+1;j++)
            suml[i][j]=suml[i-1][j]+fl[i][j];

    for (int j=1;j<=n;j++){
        int tl=-1,tr=-1;
        for (int i=1;i<=n;i++) if (a[i][j]) {tl=i;break;}
        for (int i=n;i>=1;i--) if (a[i][j]) {tr=i;break;}
        if (tl==-1){
            ben++;
            continue;
        }
        if (tr-tl+1 > k) continue;
        for (int i=tl-(k-(tr-tl+1));i<=tl;i++) fc[i][j]=1;
    }
    for (int j=1;j<=n;j++)
        for (int i=1;i<=n-k+1;i++)
            sumc[i][j]=sumc[i][j-1]+fc[i][j];

    for (int i=1;i<=n-k+1;i++)
        for (int j=1;j<=n-k+1;j++){
            ans=max(ans,ben + suml[i+k-1][j]-suml[i-1][j]+sumc[i][j+k-1]-sumc[i][j-1]);
        }
    printf("%d\n",ans);
    return 0;
}

E - Compress Words

Description

*2000

定义合并两个单词为:移除后一个单词的前缀,这个前缀和前一个单词的后缀相同并且最长。例如:sample+please=samplease
给出 n 个单词,从左到右两两进行合并(即先合并第一个和第二个,然后将结果合并第三个……),输出所有操作完成后的结果。1\leq n\leq 10^5,所有单词总长度不超过 10^6

Solution #1

(来自:https://www.luogu.org/blog/Soulist/solution-cf1200e)

感觉这题字符串哈希的做法比较简单……
对新加入的字符串直接枚举其前缀和原串的后缀,然后双模哈希判断相同……
(据说 CF 写哈希很容易被 hack?)

Code #1

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

#define int long long

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

const int maxn=10005,maxlen=1e6+5,LEN=1e6;
const int tt=1e9+7;
const int hv[2]={1926,817};

int n;
char s[maxlen],ans[maxlen];
int len=0;

int qsm[2][maxlen];

signed main(){
    n=read();
    qsm[0][0]=qsm[1][0]=1;
    for (int i=1;i<=LEN;i++) qsm[0][i]=qsm[0][i-1]*hv[0]%tt,qsm[1][i]=qsm[1][i-1]*hv[1]%tt;

    while (n--){
        scanf("%s",s+1); int nowlen=strlen(s+1);
        int hash1[2],hash2[2],now=0;
        hash1[0]=hash1[1]=hash2[0]=hash2[1]=0;
        for (int i=1;i<=min(nowlen,len);i++){
            for (int k=0;k<2;k++){
                hash1[k]=(hash1[k]*hv[k]+s[i])%tt;
                hash2[k]=(hash2[k]+ans[len-i+1]*qsm[k][i-1])%tt;
            }
            if (hash1[0]==hash2[0] && hash1[1]==hash2[1]) now=i;
        }
        for (int i=now+1;i<=nowlen;i++) ans[++len]=s[i];
    }
    for (int i=1;i<=len;i++) putchar(ans[i]);
    printf("\n");
    return 0;
}

Solution #2

(来自 CF 官方 Tutorial)

用 KMP 的解法需要对 KMP 的原理等有比较深入的认知(比如我就没想出来(吐血))。
KMP 中 next 表示的就是最长相同前缀和后缀的长度,所以只要把两个串先拼在一起,使要找前缀的在前面、要找后缀的在后面,然后再构造一遍 next 数组不就行了??最后一个字符的 next 就是答案。
需要注意的是,将两个字符串“拼在一起”时要在中间加一个特殊的字符(比如@),以确保前缀和后缀不会越过一个字符串。如果新加入的串长度比已合并的更大,可以把前面截掉,只留后面和已合并的长度一样的后缀。

F - Graph Traveler

Description

*1500

给出一张有向图,可能有重边、自环。每个点有点权 k_i,点 im_i 条出边,连向的点分别记为 e_i[0],e_i[1],\dots,e_i[m_i-1]
你可以开始一个 Graph Traveler 的游戏,规则(步骤)如下:
- 选定一个起点和一个整数 c
- 当访问到 i 点时(包括起点),将 c 加上 k_i
- 设 x 满足 x ≡ c \pmod {m_i}0\leq x\leq m_i-1,则接下来走向点 e_i[x]

显然步骤 2 和 3 会陷入循环。现在给出 q 组询问,每次询问如果从给定的点 x 以给定的数字 y 开始,多少点会被经过无数次。

数据范围:1\leq n\leq 1000, 1\leq m_i\leq 10, -10^9\leq k_i\leq 10^9, 1\leq m_i\leq 10
1\leq q\leq 10^5, -10^9\leq y\leq 10^9

Solution

如果直接暴力求解,我们肯定想要的是记录一个状态 (x,c),表示走到 x 点,手中的数字是 y,如果走到重复的状态则会陷入循环。但是问题在于这个 y 可以是无限大或者无限小。
考虑对于一个点 x,在走到这个点上时持有的数字如果是 yy+m_i,结果是一样的。那么如对于所有点,就都满足 yy+lcm(m_i) 同等。lcm(1,\dots,10) = 2520(记为 maxs),所以我们可以把所有 y 都控制到 [0,2520)
接下来就简单了,可以把每个 (x,y) 状态看成一个点,编号为 (x-1)\ast maxs+y,那么每个点就只有一条出边,直接求环就可以了……

Code

long long 过不了,可能会爆内存,但是显示的是 RE……

#include<bits/stdc++.h>

using namespace std;

// #define int long long

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

const int maxn=2005,maxs=2520;

int n,v[maxn];
int m[maxn],k[15],lnk[maxn*maxs],rlnk[maxn*maxs];
int q;

int ans[maxn*maxs];
int deep[maxn*maxs],onl[maxn*maxs];
bool vis[maxn*maxs],cnd[maxn];

int DFS(int x,int y,int fa){
    int now=(x-1)*maxs+y;
    if (ans[now]!=-1) return ans[now];

    deep[now]=deep[fa]+1; onl[deep[now]]=x;
    vis[now]=true;
    if (vis[lnk[now]]){
        for (int i=deep[lnk[now]];i<=deep[now];i++) if (!cnd[onl[i]]) ans[now]++,cnd[onl[i]]=true;
        for (int i=deep[lnk[now]];i<=deep[now];i++) cnd[onl[i]]=false;
    } else ans[now]=DFS(rlnk[now],(y+v[x])%maxs,now);
    vis[now]=false;
    return ans[now];
}

signed main(){
    n=read();
    for (int i=1;i<=n;i++) v[i]=read(),v[i]=(v[i]%maxs+maxs)%maxs;
    for (int i=1;i<=n;i++){
        m[i]=read();
        for (int j=0;j<m[i];j++) k[j]=read();
        for (int j=0;j<maxs;j++){
            int nowto=(j+v[i])%maxs;
            lnk[(i-1)*maxs+j]=(k[nowto%m[i]]-1)*maxs+nowto;
            rlnk[(i-1)*maxs+j]=k[nowto%m[i]];
            ans[(i-1)*maxs+j]=-1;
        }
    }

    for (int i=1;i<=n;i++)
        for (int j=0;j<maxs;j++)
            if (ans[(i-1)*maxs+j]==-1) DFS(i,j,(i-1)*maxs+j);

    q=read();
    while (q--){
        int x=read(),c=read();
        c=(c%maxs+maxs)%maxs;
        printf("%d\n",ans[(x-1)*maxs+c]+1);
    }
    return 0;
}

知识共享许可协议 本文章采用 知识共享署名-非商业性使用-相同方式共享 4.0 许可协议 进行许可。
欢迎转载,如有错误欢迎指出。
本文链接:https://skywt.cn/posts/cf1200/


发表评论

电子邮件地址不会被公开。 必填项已用*标注