4.7 模拟赛

祭第二次 AK 这次是首 AKer。

CF126B Password

Description

给定一个字符串 $s$，求 $s$ 的一个最大 $\text{border}$ 使得它除了在收尾，在中间也出现过。

Solution

显然，中间存在过一个 $\text{border}$，也就是对于末尾的 $\text{border}_n$，存在一个中间值 $j$ 使得 $\text{border}_j=\text{border}_n$。而且，注意到所有的 $\text{border}_i\le n$，因此开一个桶 flag 来记录中途出现的 $\text{border}$，最后结尾不断跳 $\text{border}$ 判断之前有没有出现过。

1
2
3
4
int j=border[n-1];
while(j&&!flag[j])  j=border[j-1];
for(int i=0;i<j;++j)    cout<<c[i];
cout<<endl;

P3879 [TJOI2010] 阅读理解

Description

给出一些句子，包含一些单词，一共有 $m$ 次查询，每次查询一个单词 $s$ 在哪些句子中出现过。

Solution

字符串哈希，使用 map 进行维护。对于每一个单词开一个 vector 统计哪些句子出现过。注意去重处理（当然也可以用 set 来省去去重）。

1
2
3
4
5
6
7
8
9
cin>>n;
for(int i=1;i<=n;++i){
    cin>>l;
    for(int j=1;j<=l;++j){
        cin>>s;
        if(!ma[s])  ma[s]=++idx;
        if(!g[ma[s]].size()||g[ma[s]].back()!=i)    g[ma[s]].pb(i);
    }
}

P2922 [USACO08DEC] Secret Message G

Description

给定一些字符串，查询 $m$ 次，每次一个字符串 $s$，求给定的字符串中是它前缀或它是前缀的串的数量。

Solution

把那些字符串扔进 $\text{Trie}$ 中，然后在路径上每次插入 $+1$，并且在最后的地方开另一个数组 $+1$。这样，答案就是路径上结尾的地方的数组和加上末尾子树的第一个数组和。

P5952 [POI2018] 水箱

Description

给定一个 $n\times m$ 的网格，每两个网格之间有一堵墙分隔。墙的高度为 $h_i$，四周的墙无穷高。求最高水位为 $H$ 时整个网格可能的状态数，对 $10^9+7$ 取模。

Solution

首先注意到 $1\le H\le 10^9$，这很不好，但是 $n\times m\le 5\times 10^5$，因此可以离散化。考虑我们从低到高一层层填水，中间断层的就一下子填完，那么一定是一堆小的联通块不断合并的过程。因此，很容易联想到并查集。我们考虑使用并查集维护联通块，并且开两个数组 $\text{ans,comdep}$ 分别表示该联通块在 $\text{comdep}$ 的高度时刚好合并，并且这个高度的答案为 $\text{ans}$。值得注意的是，相同的联通块在不同高度的答案是不一样的。因为可能整个水位同时提高，这样的答案就会 $+1$（例如一个格子，它在 $H=1$ 时 $\text{ans}=2$，但是在 $H=21$ 时 $\text{ans}=22$）。记录这个 $\text{comdep}$ 就是方便下次再合并它的时候统计它的答案。

现在考虑如何合并两个联通块。对于联通块 $x$ 和 $y$，显然在高度小于合并高度的时候，它们互不影响，根据乘法原理，很容易得知在高度小于合并高度时它们的答案是 $(\text{ans}_x+dep-\text{comdep}_x)$ $\times$ $(\text{ans}_y+dep-\text{comdep}_y)$。然后再把 $\text{comdep}$ 设成当前高度，我们就合并完了。

注意，这里的记录方式有很多种。我用的是不记录在刚好合并的高度上的那一个答案，而是只记录它们的乘积。这样可以最大地减小代码复杂度。大家注意一下这里的统计细节。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>

#include<bitset>
#include<set>

#include<deque>
#include<cassert>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<vector>

#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define DBG cerr << __LINE__ << ' ' << __FUNCTION__ << endl

#define DRE default_random_engine
#define UID uniform_int_distribution
#define y0 Y0
#define y1 Y1

#define pi acos(-1)
#define eps (1e-8)

using namespace std;

#define int long long
const int INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int N = 1e6 + 10;
const int M = 5e5 + 10;
const int MOD = 1e9 + 7;

struct edge{
    PII u,v;
    int h;
}e[N];
int fa[N], a[N], n, m, idx, ans[N], comdep[N], H;

int Hash(int x,int y){ return (x-1)*m+y;}
int find(int x){ return fa[x]==x?fa[x]:fa[x]=find(fa[x]);}

bool cmp(edge x,edge y){
	return x.h<y.h;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
    cin>>n>>m>>H;
    for(int i=1;i<=n;++i)
        for(int j=1;j<m;++j)    ++idx, cin>>e[idx].h, e[idx].u=mk(i,j), e[idx].v=mk(i,j+1), a[idx]=e[idx].h+1;
    for(int i=1;i<n;++i)
        for(int j=1;j<=m;++j)   ++idx, cin>>e[idx].h, e[idx].u=mk(i,j), e[idx].v=mk(i+1,j), a[idx]=e[idx].h+1;
    sort(a+1,a+1+idx);
    int tot=unique(a+1,a+1+idx)-a-1;
    sort(e+1,e+1+idx,cmp);
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            int x=Hash(i,j);
            fa[x]=x, ans[x]=1; comdep[x]=1;
        }
    int j=1;
    for(int i=1;i<=tot;++i){
        if(a[i]>H)  break;
        while(e[j].h<a[i]&&j<=idx){
            int x=Hash(e[j].u.fi,e[j].u.se), y=Hash(e[j].v.fi, e[j].v.se);
            int fx=find(x), fy=find(y);
            if(fx==fy){ ++j; continue;}
            fa[fy]=fx;
            ans[fx]=((ans[fx]+(a[i]-comdep[fx]))%MOD*(ans[fy]+(a[i]-comdep[fy]))%MOD)%MOD;
            comdep[fx]=a[i];
            ++j;
        }
    }
    int sum=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            int x=Hash(i,j);
            if(find(x)==x)  sum=(sum*(ans[x]+H+1-comdep[x])%MOD)%MOD;
        }
    cout<<sum<<endl;
	return 0;
}

P2375 [NOI2014] 动物园

Description

要求求 $\text{num}$ 表示一个字符串前缀后缀相等的、不重叠的子串的数量。

Solution

方法 1

首先考虑没有不重叠的限制的答案是什么。

显然，如果一个地方的 $\text{border}$ 是 $i$，那么 $\text{num}_{i-1}+1$。特别的，如果 $i=0$，则 $\text{num}=0$。

然后，我们再讨论有限制的情况。我们这时候再开一个 $\text{nxt}$ 表示不重叠的最大 $\text{border}$，那么显然它的求法是一直跳 $\text{border}$（注意这里是第一次求的 $\text{border}$）。那么这里的 $\text{num}i=\text{num}{\text{nxt}_{i-1}}+1$，理由同上。

方法 2

考虑可以有 $O(n \log n)$ 做法。

这个题在求解答案的时候，一种很暴力的方法是对于每一个 $i$ 都不断跳 $\text{border}$ 直到没有重叠的。但是，显然，如果字符串为 $aaaaa\cdots aaaaa$，一共 $10^5$ 个 $a$，那么这里不断跳 $\text{border}$ 显然每次 $O(n)$，那么时间复杂度就爆掉了。

但是我们考虑要找到不重叠的最大 $\text{border}$，一定存在唯一的次数 $x$ 使得跳 $x$ 次之后就是我们需要的答案。而这个 $x$ 又可以分解为一连串的二进制表示，因此不难想到可以使用倍增来加快跳 $\text{border}$ 的过程。这样，我们就可以 $O(n\log n)$ 地完成这一道题目了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for(int i=1;i<len;++i){
    int j=nxt[i-1];
    while(c[i]!=c[j]&&j)    j=nxt[j-1];
    j+=(c[i]==c[j]); nxt[i]=j;
    if(j)   all[i]=all[j-1]+1;
    else    all[i]=0;
}
for(int i=1;i<len;++i){
    int j=border[i-1];
    while((c[i]!=c[j]||(j+1)*2>i+1)&&j)    j=nxt[j-1];
    j+=(c[i]==c[j]); border[i]=j;
    if(j)   num[i]=all[j-1]+1;
    else    num[i]=0;
}