Codeforces Round #578 (Div. 2)

D - White Lines

Description

*1900

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

数据范围：$n,m\leq 2000$。

Solution

$Fl(i,j)$ 表示擦除了第 $i$ 行 $j$ 列开始横着的 $k$ 个格子之后这一行是否能为空；
$Fc(i,j)$ 表示擦除了第 $i$ 行 $j$ 列开始竖着的 $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$，点 $i$ 有 $m_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$，在走到这个点上时持有的数字如果是 $y$ 和 $y+m_i$，结果是一样的。那么如对于所有点，就都满足 $y$ 和 $y+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;
}