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)$ 表示擦除了第 行 列开始竖着的 个格子之后这一列是否能为空；

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

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 ( i=;i<=n;i++)
         ( j=;j<=n;j++)
            a[i][j]=();
    
     ( i=;i<=n;i++){
         tl=,tr=;
         ( j=;j<=n;j++)  (a[i][j]) {tl=j;;}
         ( j=n;j>=;j--)  (a[i][j]) {tr=j;;}
         (tl==){
            ben++;
            ;
        }
         (tr-tl > k) ;
         ( j=tl-(k-(tr-tl));j<=tl;j++) fl[i][j]=;
    }
     ( i=;i<=n;i++)
         ( j=;j<=n-k;j++)
            suml[i][j]=suml[i][j]+fl[i][j];

     ( j=;j<=n;j++){
         tl=,tr=;
         ( i=;i<=n;i++)  (a[i][j]) {tl=i;;}
         ( i=n;i>=;i--)  (a[i][j]) {tr=i;;}
         (tl==){
            ben++;
            ;
        }
         (tr-tl > k) ;
         ( i=tl-(k-(tr-tl));i<=tl;i++) fc[i][j]=;
    }
     ( j=;j<=n;j++)
         ( i=;i<=n-k;i++)
            sumc[i][j]=sumc[i][j]+fc[i][j];

     ( i=;i<=n-k;i++)
         ( j=;j<=n-k;j++){
            ans=(ans,ben + suml[i+k][j]-suml[i][j]+sumc[i][j+k]-sumc[i][j]);
        }
    (,ans);
     ;
}

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][]=qsm[][]=;
     ( i=;i<=LEN;i++) qsm[][i]=qsm[][i]*hv[]%tt,qsm[][i]=qsm[][i]*hv[]%tt;

     (n--){
        (,s);  nowlen=(s);
         hash1[],hash2[],now=;
        hash1[]=hash1[]=hash2[]=hash2[]=;
         ( i=;i<=(nowlen,len);i++){
             ( k=;k<;k++){
                hash1[k]=(hash1[k]*hv[k]+s[i])%tt;
                hash2[k]=(hash2[k]+ans[len-i]*qsm[k][i])%tt;
            }
             (hash1[]==hash2[] && hash1[]==hash2[]) now=i;
        }
         ( i=now;i<=nowlen;i++) ans[++len]=s[i];
    }
     ( i=;i<=len;i++) (ans[i]);
    ();
     ;
}

Solution #2

（来自 CF 官方 Tutorial）

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

F - Graph Traveler

Description

*1500

给出一张有向图，可能有重边、自环。每个点有点权 $k_i$，点 $i$ 有 $m_i$ 条出边，连向的点分别记为 $e_i[0],{}_{}$。 你可以开始一个 Graph Traveler 的游戏，规则（步骤）如下：

• 选定一个起点和一个整数 $c$；
• 当访问到 $i$ 点时（包括起点），将 $c$ 加上 $k_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$； 。

Solution

如果直接暴力求解，我们肯定想要的是记录一个状态 $(x,c)$，表示走到 $x$ 点，手中的数字是 $y$，如果走到重复的状态则会陷入循环。但是问题在于这个 $y$ 可以是无限大或者无限小。
考虑对于一个点 $x$，在走到这个点上时持有的数字如果是 $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;
     (vis[lnk[now]]){
         ( i=deep[lnk[now]];i<=deep[now];i++)  (!cnd[onl[i]]) ans[now]++,cnd[onl[i]]=;
         ( i=deep[lnk[now]];i<=deep[now];i++) cnd[onl[i]]=;
    }  ans[now]=(rlnk[now],(y+v[x])%maxs,now);
    vis[now]=;
     ans[now];
}

{
    n=();
     ( i=;i<=n;i++) v[i]=(),v[i]=(v[i]%maxs+maxs)%maxs;
     ( i=;i<=n;i++){
        m[i]=();
         ( j=;j<m[i];j++) k[j]=();
         ( j=;j<maxs;j++){
             nowto=(j+v[i])%maxs;
            lnk[(i)*maxs+j]=(k[nowto%m[i]])*maxs+nowto;
            rlnk[(i)*maxs+j]=k[nowto%m[i]];
            ans[(i)*maxs+j]=;
        }
    }

     ( i=;i<=n;i++)
         ( j=;j<maxs;j++)
             (ans[(i)*maxs+j]==) (i,j,(i)*maxs+j);
    
    q=();
     (q--){
         x=(),c=();
        c=(c%maxs+maxs)%maxs;
        (,ans[(x)*maxs+c]);
    }
     ;
}