Hexo
0%

Posted on

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Posted on

hello

hello

hello

This is my blog, build by hexo.

eiπ+1=0e^{i\pi}+1=0

1
2
3
4
5
#include<iostream>
int main(){
    std::cout<<"hello world!"<<std::endl;
    return 0;
}

Posted on Edited on

斜率优化

P3195 [HNOI2008] 玩具装箱

考虑 dp，令 si=∑k=1icks_i=\sum^{i}_{k=1}c_k，dpidp_i 为 11 到 ii 装箱的最小代价，则转移方程为 dpi=min⁡dpj+(i−j−1+si−sj−L)2(1≤j<i)dp_i=\min dp_j+(i-j-1+s_i-s_j-L)^2(1\le j<i)。

此时，为了方便，我们将所有的 sis_i 加 11，将 LL 也加 11，那么式子简化为 dpj+(si−sj−L)2=dpj+si2−2sisj−2siL+(sj+L)2dp_j+(s_i-s_j-L)^2=dp_j+s_i^2-2s_is_j-2s_iL+(s_j+L)^2。

此时，假设有 j0<j1j_0<j_1 且由 j1j_1 转移更优，则 dpj0+si2−2sisj0−2siL+(sj0+L)2≥dpj1+si2−2sisj1−2siL+(sj1+L)2dp_{j_0}+s_i^2-2s_is_{j_0}-2s_iL+(s_{j_0}+L)^2\ge dp_{j_1}+s_i^2-2s_is_{j_1}-2s_iL+(s_{j_1}+L)^2，即 (sj1−sj0)×2si≥[dpj1+(sj1+L)2]−[dpj0+(sj0+L)2](s_{j_1}-s_{j_0})\times 2s_i\ge [dp_{j_1}+(s_{j_1}+L)^2]-[dp_{j_0}+(s_{j_0}+L)^2]，由于显然 sj1≥sj0s_{j_1}\ge s_{j_0}，令 Yi=dpi+(si+L)2,Xi=siY_i=dp_i+(s_i+L)^2,X_i=s_i，因此 2si≥Yj1−Yj0Xj1−Xj02s_i \ge \frac{Y_{j_1}-Y_{j_0}}{X_{j_1}-X_{j_0}}。

此时，我们发现这个式子很像斜率，考虑当我们多了一个的决策点时，我们会希望这个决策点与上一个点形成的斜率越小越好（毕竟越小根据上面的式子会更优），也就是我们在维护一些，因此我们可以用单调队列来维护决策点。

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
#include<iostream>
using namespace std;
typedef long long ll;
const long double eps=1e-11;
ll c[50010],dp[50010];
int n,L;
ll X(int j){return c[j];}
ll Y(int j){return dp[j]+(c[j]+L)*(c[j]+L);}
long double slope(int i,int j){return 1.0L*(Y(j)-Y(i))/(X(j)-X(i));}
int q[50010];
int main(){
    cin>>n>>L;
    L++;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;++i)c[i]+=c[i-1]+1;
    int l,r;l=r=0;
    q[r++]=0;
    for(int i=1;i<=n;i++){
        while(l<r-1&&slope(q[l],q[l+1])-2.0L*c[i]<eps)l++;//不最优的就弹出
        dp[i]=dp[q[l]]+(c[i]-c[q[l]]-L)*(c[i]-c[q[l]]-L);
        while(l<r-1&&slope(q[r-2],q[r-1])-slope(q[r-2],i)>eps)r--;//使斜率尽量小
        q[r++]=i;
    }
    cout<<dp[n]<<endl;
    return 0;
}

决策单调性分治

决策单调性指决策非严格递增，这样的 dp 转移时的代价通常可写为 cost(i,j)cost(i,j) 的形式，且当 a<b<c<da<b<c<d 时，cost(a,d)+cost(b,c)cost(a,d)+cost(b,c) 劣于 cost(a,c)+cost(b,d)cost(a,c)+cost(b,d)（即四边形不等式，可记忆为包含劣于交叉）。

在对于形如 dpi,jdp_{i,j} 且第一维为转移层数且只能从上一层往下一层转移并具有决策单调性时，可使用决策单调性分治。决策单调性分治一般使用递归实现，对于状态 [l,r][l,r] 以及其决策区间 [vl,vr][vl,vr]，我们取中点 mid=l+r2mid=\displaystyle\frac{l+r}{2}，并暴力计算出其决策点 mm，那么状态 [l,mid)[l,mid) 的决策区间为 [vl,m][vl,m]，状态 (mid,r](mid,r] 的决策区间为 [m,vr][m,vr]，递归解决即可。递归层数显然为 O(log⁡n)O(\log{n}) 级别，每一层复杂度为 O(n)O(n) 因此进行动态规划 kk 层的总复杂度为 O(knlog⁡n)O(kn\log{n})。

P4360 [CEOI 2004] 锯木厂选址

决策单调性分治板子，证明一般打一下表就行了，当然也可以证四边形不等式。代码略。

CF868F Yet Another Minimization Problem

这道题目暴力 dp 易想到状态 fi,jf_{i,j} 表示序列长度为 jj 分 ii 段的最小费用，转移为 dpi,j=min⁡k=i−1j−1dpi−1,k+cost(k+1,j)dp_{i,j}=\displaystyle\min_{k=i-1}^{j-1}dp_{i-1,k}+cost(k+1,j)。可以证明该 dp 有决策单调性，决策单调分治即可，注意这题 costcost 不好算，可采用莫队思想，维护左右指针 ll 和 rr，将左右指针每次挪一格，这题挪一格的复杂度可做到 O(1)O(1)，因此总复杂度为 O(knlog⁡n)O(kn\log{n})。

数据结构优化

单调队列优化

一般用在决策在一段类似滑动窗口的区间内的线性 dp。其代价一般较为固定。

P1725 琪露诺

单调队列优化板子，转移方程为 dpi=max⁡j=i−Ri−Ldpj+Aidp_i=\displaystyle\max_{j=i-R}^{i-L}dp_j+A_i，用单调队列维护最大的 dpjdp_j 即可。

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
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
using namespace std;
int st=0,ed=0,q[200010],dp[200010],a[200010];
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,l,r;
	cin>>n>>l>>r;
	for(int i=0;i<=n;i++){
		cin>>a[i];
	} 
	for(int i=1;i<l;i++){
		dp[i]=-2147483648;
	}
	int ans=-2147483648;
	for(int i=l;i<=n;i++){
		while(ed>st&&dp[i-l]>dp[q[ed-1]]) ed--;
		q[ed++]=i-l;
		if(q[st]<i-r) st++;
		dp[i]=dp[q[st]]+a[i];
		if(i+r>n)ans=max(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

线段树优化

没什么好讲的，比较活。

wqs 二分优化

wqs 二分一般用在形如有 nn 个物品选 mm 个求最大或最小消费的 dp 中。wqs 二分的条件是凸性，即当我们将选的个数作为横坐标，对应的消费作为纵坐标时，相邻点之间的斜率非严格递增（下凸）或递减（上凸），一般来说当要取最大时为上凸，反之为下凸，凸性一般比较难证，但当 O(mn)O(mn) 的斜率优化无法通过时，一般就得用 wqs 二分，当然，打表也是可以的。下图是一个下凸函数的示例：

对于这样的问题，我们考虑用直线 kx+bkx+b 来切凸包，设 f(x)f(x) 为选 xx 个的消费，则切点 ii 满足 f(i)−kif(i)-ki 最小或最大（看凸性，但也可以直接看我们是要最小化还是最大化代价）。因此对于每个斜率 kk，我们可以先抛开个数限制进行 dp，每分一组消费要减 kk，最优的组数便是切点。

由于斜率是单调的，因此我们可以考虑二分斜率，例如当上凸时，如果求得的切点小于 kk 则斜率大了，反之小了。最终的答案为 dpn+kmdp_n+km。

P5308 [COCI 2018/2019 #4] Akvizna

考虑 wqs 二分，可发现该函数为上凸，再加上斜率优化即可。

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
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iomanip>
using namespace std;
const long double eps=1e-18;
const int N=1e5+10;
int n,k;
long double dp[N];int h[N],q[N];
long double X(int j){
    return 1.0L/(long double)(n-j);
}
long double Y(int j){
    return dp[j]-(long double)j/(n-j);
}
bool check(long double mid){
    int l=1,r=0;
    q[++r]=0;
    for(int i=1;i<=n;i++){
        while(l<r&&Y(q[l+1])-Y(q[l])>=-i*(X(q[l+1])-X(q[l])))l++;
        int j=q[l];
        h[i]=h[j]+1;
        dp[i]=dp[j]+(long double)(i-j)/(n-j)-mid;
        while(l<r&&(Y(i)-Y(q[r-1]))*(X(q[r])-X(q[r-1]))>=(Y(q[r])-Y(q[r-1]))*(X(i)-X(q[r-1])))r--;
        q[++r]=i;
    }
    return h[n]<=k;
}
int main(){
    cin>>n>>k;
    long double l=0,r=1,mid;
    while(fabs(r-l)>eps){
        mid=(l+r)/2.0L;
        if(check(mid))r=mid;
        else l=mid;
    }
    cout<<fixed<<setprecision(9)<<dp[n]+mid*k<<'\n';
    return 0;
}

Posted on Edited on

莫队

普通版

前言

莫队是由集训队大佬莫涛提出来的，在此再次膜拜大佬！

思想

普通莫队主要用于离线的区间查询操作，当然，也不是所有的都适用，当一个区间 [l,r][l,r] 的答案可以用 O(1)O(1) 的时间转化成 [l+1,r],[l−1,r],[l,r+1],[l,r−1][l+1,r],[l-1,r],[l,r+1],[l,r-1] 的答案，我们就可以考虑使用莫队。

具体怎么做呢？其实就是将当前区间的答案通过一次一次移动 l,rl,r 变成另一个区间的答案。

然后就没有了？

当然不是，这样很容易就被卡了，怎么卡呢，只需要将一次询问放在最前，下一次有放在最后，如此循环往复，这样我们每次就会移动 nn 次，就足够卡爆这个没加任何优化的方法。

怎么优化呢？我们可以修改每个询问的顺序，尽量让两个询问之间移动次数最少，这里说一种咋看有点玄学的方法，我们把序列分成 n\sqrt{n} 个块，如果两个点的左端点不在同一块，左端点小的放前面，如果左端点所在块相同，那就比较右端点，右端点小的排前面。

复杂度证明

可以证明，最坏复杂度为 O(nn)O(n\sqrt{n})。我有一个绝妙的证明方法，可惜这里的空白太小了（分明是作者不会）。

优化

还能优化？没错，我们修改一下排序规则，如果两个点的左端点不在同一块，左端点小的放前面，如果左端点所在块相同，那就比较右端点，如果当前块编号为奇数，右端点小的放前面，否则右端点大的放前面。还想问为什么？应该不需要我放那句话了吧。

小B的询问

题面

小B 有一个长为 nn 的整数序列 aa，值域为 [1,k][1,k]。
他一共有 mm 个询问，每个询问给定一个区间 [l,r][l,r]，求：

∑i=1kci2\sum\limits_{i=1}^k c_i^2

其中 cic_i 表示数字 ii 在 [l,r][l,r] 中的出现次数。
小B请你帮助他回答询问。

思路

莫队板子题。问题在于该如何修改呢？其实很简单，当我们将某个点加入当前区间时，设这个点所表示的值在当前区间的值为 xx，那么答案会增加 (x+1)2−x2=2x+1(x+1)^2-x^2=2x+1，当我们将某个点从当前区间删除时，设这个点所表示的值在当前区间的值为 xx，那么答案会减少 x2−(x−1)2=2x−1x^2-(x-1)^2=2x-1。

代码

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
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int a[50010];
int b[50010];
int pos[50010];
long long ans[50010];
struct node{
	int l,r;
	int idx;
}c[50010];
long long cnt=0;
bool cmplr(node a,node b){
	if(pos[a.l]!=pos[b.l])return a.l<b.l;
	if(pos[a.l]&1)return a.r<b.r;
	return a.r>b.r;
}
void pplus(int x){
	cnt+=(b[x]*2)+1;
	b[x]++;
	return;
}
void perase(int x){
	cnt-=(b[x]*2)-1;
	b[x]--;
	return;
}
int main(){
    cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m,k;
	cin>>n>>m>>k;
	int block=n/sqrt(m);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pos[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;i++){
		cin>>c[i].l>>c[i].r;
		c[i].idx=i;
	}
	sort(c+1,c+m+1,cmplr);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l>c[i].l){
			l--;
			pplus(a[l]);
		}
		while(r<c[i].r){
			r++;
			pplus(a[r]);
		}
		while(l<c[i].l){
			perase(a[l]);
			l++;
		}
		while(r>c[i].r){
			perase(a[r]);
			r--;
		}
		ans[c[i].idx]=cnt;
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
	cout<<flush;
    return 0;
}

小Z的袜子

题面

作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……

具体来说，小 Z 把这 NN 只袜子从 1 到 NN 编号，然后从编号 LL 到 RR 的袜子中随机选出两只来穿。尽管小 Z 并不在意两只袜子是不是完整的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 (L,R)(L,R) 以方便自己选择。

思路

其实没那么难，设当前区间编号为 ii 的袜子有 xx 双，根据概率论和一点数学，答案是：
∑i=lrci×(ci−1)2(r−l+1)×(r−l)2=∑i=lrci−(r−l+1)(r−1+1)×(r−l)\frac{\sum^{r}_{i=l}\frac{c_i\times (c_i-1)}{2}}{\frac{(r-l+1)\times (r-l)}{2}}=\frac{\sum^{r}_{i=l}c_i-(r-l+1)}{(r-1+1)\times (r-l)}。现在会做了吧，就是上一题加一点东西。

代码

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
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int a[50010];
int b[50010];
int pos[50010];
long long aa[50010],bb[50010];
struct node{
	int l,r;
	int idx;
}c[50010];
long long cnt=0;
bool cmplr(node a,node b){
	if(pos[a.l]!=pos[b.l])return a.l<b.l;
	if(pos[a.l]&1)return a.r<b.r;
	return a.r>b.r;
}
void pplus(int x){
	cnt+=(b[x]*2)+1;
	b[x]++;
	return;
}
void perase(int x){
	cnt-=(b[x]*2)-1;
	b[x]--;
	return;
}
int pgcd(long long a,long b){
	return b?pgcd(b,a%b):a;
}
int main(){
    cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	int block=n/sqrt(m);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		pos[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;i++){
		cin>>c[i].l>>c[i].r;
		c[i].idx=i;
	}
	sort(c+1,c+m+1,cmplr);
	long long l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l>c[i].l){
			l--;
			pplus(a[l]);
		}
		while(r<c[i].r){
			r++;
			pplus(a[r]);
		}
		while(l<c[i].l){
			perase(a[l]);
			l++;
		}
		while(r>c[i].r){
			perase(a[r]);
			r--;
		}
		if(l==r){
			aa[c[i].idx]=0;
			bb[c[i].idx]=1;
		}else{
			aa[c[i].idx]=cnt-(r-l+1);
			bb[c[i].idx]=(r-l+1)*(r-l);
			int t=pgcd(aa[c[i].idx],bb[c[i].idx]);
			aa[c[i].idx]/=t;
			bb[c[i].idx]/=t;
		}
	}
	for(int i=1;i<=m;i++){
		cout<<aa[i]<<"/"<<bb[i]<<"\n";
	}
	cout<<flush;
    return 0;
}

Posted on Edited on

tarjan 求 LCA

题面

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

思路

这次我们要使用的知识点是 dfsdfs 和并查集，这个 tarjantarjan 是离线的，我们要先把每个点的每一个要跟它求 LCALCA 的点给记录下来，接下来用 dfsdfs 跑这么个流程：

  1. 遍历这个点的每个子结点并进入子节点
  2. 将子节点与自己合并
  3. 遍历要跟它求 LCALCA 的点，如果这个点被访问了，这个点在并查集中的祖先便是答案

等等，你是不是蒙圈了？我们先放张图：

假设我们要求 LCA(3,6)LCA(3,6) 。

我们在这张图上模拟一下并查集中的过程：

首先，一切还是一盘散沙：

接下来，33 和它的父节点 44 合并起来了，由于与 33 它相关联的 66 还没访问，此时无法更新任何答案：

接着又是 5,45,4 以及 2,52,5，都无法更新答案：

注意了！！！此处敲黑板！！！此时我们访问到 22 的另一个子节点 66，此时我们便发现，33 已被访问，于是答案是 22 ！！！

后面的无用功就不放了。

于是，我们就发现了，其实我们就是把点按 dfndfn 序不断合并，当两个点要合并在一起时，此时的祖先便是答案，就像这样：

xx 和 yy 便是要求 LCALCA 的两个点，它们现在刚好就合并到一起，显然只有到它们的公共祖先它们才会合并在一起，再由于回溯时是从深到低，所以第一次合并在一起时一定是到 LCALCA 了。

代码

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdio>
#include<string>
#include<iomanip>
using namespace std;
const int N=5e5+10;
int n,m,s;
struct edge{
	int to,nxt;
}g[N<<1];
int head[N],tot1=0;
struct qry{
	int to,nxt,idx;
}q[N<<1];
int qhead[N],tot2=0;
int ans[N];
void add(int x,int y){
	tot1++;
	g[tot1].to=y;
	g[tot1].nxt=head[x];
	head[x]=tot1;
	return;
}
void qadd(int x,int y,int z){
	tot2++;
	q[tot2].to=y;
	q[tot2].nxt=qhead[x];
	q[tot2].idx=z;
	qhead[x]=tot2;
	return;
}
int fa[N],vis[N];
int Find(int x){
	return (fa[x]==x)?x:(fa[x]=Find(fa[x]));
}
void dfs(int u,int f){
	vis[u]=1;
	for(int i=head[u];i;i=g[i].nxt){
		int v=g[i].to;
		if(v!=f){
			dfs(v,u);
			fa[v]=u;
		}
	}
	for(int i=qhead[u];i;i=q[i].nxt){
		int v=q[i].to;
		if(vis[v]){
			ans[q[i].idx]=Find(v);
		}
	}
	return;
}
int main(){
    cin.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m>>s;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		qadd(u,v,i);
		qadd(v,u,i);
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	dfs(s,0);
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
	cout<<flush;
    return 0;
}

Posted on Edited on

AC 自动机

简单版

题目描述

给定 nn 个模式串 sis_i 和一个文本串 tt，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

思路

我们可以将所有模式串存进 trietrie 树中，像这样：

此时如果我们朴素地查找，那显然会超时，因此我们可以使用类似 KMPKMP 算法的思想，对于每个点都创建一个 failfail 指针，表示与当前节点表示的字符串在trietrie 树中出他自己外的后缀最长的那个所在位置，就拿图来举例吧，对于节点 44 他的表示的字符串为 ABCABC，它的除它自己外的后缀有 CC，BCBC，在 trietrie 中它们都存在，于是我们取最长的 BCBC ，它在 77 号节点，所以 fail4=7fail_4=7。

那怎么求 failfail 呢？这个我们可以用广搜来实现，毕竟一个点的 failfail 显然不会比这个点深。那么一个点的 failfail 就是它父亲的 failfail 对应的当前节点的字符，也就是说若设 vv 为当前节点，uu 为它的父节点，ii 为 vv 这个节点存的字符，那么就有 fail[v]=nxt[fail[u]][i]fail[v]=nxt[fail[u]][i]。特别地，如果 vv 还没建立我们可以让 vv 直接等于它的 failfail 值。

有了 failfail 后，一切就好办了，只需要将要匹配的文本串在 trietrie 中查找，每到一个节点就不断跳 failfail 更新答案，毕竟当前节点能匹配上，那它的后缀自然能匹配上嘛。

注意事项

一定不要重复记录一个点的贡献。

代码

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
#include<iostream>
#include<bitset>
#include<string>
#include<cstring>
#include<queue>
using namespace std;
namespace AC{
	int nxt[1000010][26],cnt=0;
	int end[1000010],fail[1000010];
	queue<int>q;
	void insert(string s){
		int len=s.size();
		int u=0;
		for(int i=0;i<len;i++){
			if(!nxt[u][s[i]-'a']){
				nxt[u][s[i]-'a']=++cnt;
			}
			u=nxt[u][s[i]-'a'];
		}
		end[u]++;
		return;
	}
	void build(){
		queue<int>q;
		for(int i=0;i<26;i++){
			if(nxt[0][i]){
				q.push(nxt[0][i]);
			}
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=0;i<26;i++){
				if(nxt[u][i]){
					fail[nxt[u][i]]=nxt[fail[u]][i];
					q.push(nxt[u][i]);
				}else{
					nxt[u][i]=nxt[fail[u]][i];
				}
			}
		}
		return;
	}
	int query(string s){
		int u=0,ans=0;
		int len=s.size();
		for(int i=0;i<len;i++){
			u=nxt[u][s[i]-'a'];
			for(int j=u;j&&end[j]!=-1;j=fail[j]){
				ans+=end[j];
				end[j]=-1;
			}
		}
		return ans;
	}
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		string t;
		cin>>t;
		AC::insert(t);
	}
	AC::build();
	string s;
	cin>>s;
	cout<<AC::query(s)<<endl;
	return 0;
}

加强版

题目描述

给定 nn 个模式串 sis_i 和一个文本串 tt，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

思路

这题跟前一题咋看区别并不大，很容易想到用数组记录答案，每匹配上一次就更新答案，但是这样做由于一个点会被访问不止一次，时间复杂度无法接受，因此需要优化。我们来分析一下，就拿前面那张图举例：

我们会发现当到达 44 时，我们会接着一连更新 4,7,94,7,9，到 77 时又会更新一遍 7,97,9。很显然，问题就是出在这里，我们每个点不断被一次一次地更新，导致时间复杂度过大。因此，我们需要找到一种方法能够一次性统计一个点的答案。

我们可以把每个 failfail 当作一条边建图，易证这是一个 DAGDAG，我们可以不用不断跳 failfail 只需要标记当前点，再跑一遍拓扑排序，在拓扑排序的同时进行递推，这样每个点只会被更新一次，大大降低了复杂度。

代码

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<iostream>
#include<queue>
#include<string>
#include<cstring>
using namespace std;
namespace AC{
	int nxt[12800][26],tot=0;
	int ind[12800],fail[12800],cnt[160];
	queue<int>q;
    void reset(){
        tot=0;
        memset(nxt,0,sizeof(nxt));
        memset(ind,0,sizeof(ind));
        memset(fail,0,sizeof(fail));
        memset(cnt,0,sizeof(cnt));
        return;
    }
	void insert(string s,int p){
		int len=s.size();
		int u=0;
		for(int i=0;i<len;i++){
			if(!nxt[u][s[i]-'a']){
				nxt[u][s[i]-'a']=++tot;
			}
			u=nxt[u][s[i]-'a'];
		}
		ind[u]=p;
		return;
	}
	void build(){
		queue<int>q;
		for(int i=0;i<26;i++){
			if(nxt[0][i]){
				q.push(nxt[0][i]);
			}
		}
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int i=0;i<26;i++){
				if(nxt[u][i]){
					fail[nxt[u][i]]=nxt[fail[u]][i];
					q.push(nxt[u][i]);
				}else{
					nxt[u][i]=nxt[fail[u]][i];
				}
			}
		}
		return;
	}
	int query(string s){
		int u=0;
		int len=s.size();
		for(int i=0;i<len;i++){
			u=nxt[u][s[i]-'a'];
			for(int j=u;j;j=fail[j]){
				cnt[ind[j]]++;
			}
		}
        int ans=0;
        for(int i=1;i<=tot;i++){
            if(ind[i]){
                ans=max(ans,cnt[ind[i]]);
            }
        }
		return ans;
	}
}
string t[160];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    while(cin>>n&&n){
        AC::reset();
        for(int i=1;i<=n;i++){
            cin>>t[i];
            AC::insert(t[i],i);
        }
        AC::build();
        string s;
        cin>>s;
        int ans=AC::query(s);
        cout<<ans<<"\n";
        for(int i=1;i<=n;i++){
            if(AC::cnt[i]==ans){
                cout<<t[i]<<"\n";
            }
        }
    }
    cout<<flush;
    return 0;
}

Posted on Edited on

割点

基础概念

割点是怎么回事呢？是这样的，如果图中的某一个点被删掉后图的最大连通子图数量变少了，也就是说那个点所在的最大连通子图被分成了多个最大连通子图那么这个点就是图的割点。

算法思想

知道概念后，又该怎么求呢。

首先，我们求出节点的 dfndfn 序，这用 dfsdfs 就可以做到，同时，在 dfsdfs 时，维护 lowlow 表示一个点在不经过在自己在 dfsdfs 树中的父节点能到达的 dfndfn 序最小的节点的 dfndfn，如果节点 uu 存在一个它在 dfsdfs 树中的子节点 vv 使得 lowv≥dfnulow_v\ge dfn_u，那么节点 uu 就是一个割点，为什么呢？其实很简单，毕竟如果 vv 点不经过 uu 点就到不了前面 dfndfn 序更小的 uu 的祖先，那就说明去掉 uu 节点后 vv 就与前面的不连通了。同时，还有一种情况需要讨论，那就是当 uu 是他所在 dfsdfs 树的根时，只要有两个及以上的去掉 uu 就无法互相连通的子节点，拿他也是割点。

接下来讲求 lowlow 的方法，先给方法。若 vv 是 uu 的 dfsdfs 树子节点，那 lowu=min⁡(lowu,lowv)low_u=\min(low_u,low_v)，否则 lowu=min⁡(lowu,dfnv)low_u=\min(low_u,dfn_v)。证明？很可惜我现在还不会。

代码

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
#include<iostream>
using namespace std;
int ans[20010];
struct edge{
    int to;
    int nxt;
}g[200010];
int head[20010],tot=0;
int dfn[20010],low[20010],cnt=0;
int res=0;
void addedge(int x,int y){
    tot++;
    g[tot].to=y;
    g[tot].nxt=head[x];
    head[x]=tot;
    return;
}
void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    int t=0;
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(!dfn[v]){
            t++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(fa&&!ans[u]&&low[v]>=dfn[u]){
                res++;
                ans[u]=1;
            }
        }else if(v!=fa){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(!fa&&t>1&&!ans[u]){
        res++;
        ans[u]=1;
    }
    return;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        addedge(x,y);
        addedge(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i,0);
        }
    }
    cout<<res<<endl;
    for(int i=1;i<=n;i++){
        if(ans[i]){
            cout<<i<<" ";
        }
    }
    cout<<flush;
    return 0;
}

割边

基础概念

割边和割点差不多，不过点变成了边。

算法思想

总体区别与割点并不多，首先便是判断时变成了 lowv>dfnulow_v> dfn_u，为什么呢？因为 uu 到 vv 的边是唯一的，所以从 vv 出发不经过 uu 结点就相当于不走 (u,v)(u,v) 这条边，所以如果去掉该边 vv 连 uu 都连不上，那就不行了。其次便是不用考虑是否是根。

代码

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
#include<iostream>
#include<algorithm>
using namespace std;
struct edge{
    int to;
    int nxt;
}g[200010];
int head[20010],tot=0;
int dfn[20010],low[20010],cnt=0,fa;
int res=0;
struct node{
    int x,y;
}ans[200010];
bool operator<(node a,node b){
    if(a.x!=b.x)return a.x<b.x;
    else return a.y<b.y;
}
void addedge(int x,int y){
    tot++;
    g[tot].to=y;
    g[tot].nxt=head[x];
    head[x]=tot;
    return;
}
void tarjan(int u,int fa){
    dfn[u]=low[u]=++cnt;
    int t=0;
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(!dfn[v]){
            t++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u]){
                res++;
                ans[res].x=u;
                ans[res].y=v;
            }
        }else if(v!=fa){
            low[u]=min(low[u],dfn[v]);
        }
    }
    return;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    while(m--){
        int x,y;
        cin>>x>>y;
        addedge(x,y);
        addedge(y,x);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            tarjan(i,0);
        }
    }
    sort(ans+1,ans+res+1);
    for(int i=1;i<=res;i++){
        cout<<ans[i].x<<" "<<ans[i].y<<"\n";
    }
    cout<<flush;
    return 0;
}

Posted on Edited on

思路一

十分朴素的做法，设 fi,j,kf_{i,j,k} 表示第 ii 天学习第 jj 种算法 kk 天的方案数。那么对于 fi,j,1f_{i,j,1}，自然就可得：

fi,j,1=∑x=1(x≠j)m∑y=1axfi−1,x,yf_{i,j,1}=\sum_{x=1(x\ne j)}^{m}\sum_{y=1}^{a_x}f_{i-1,x,y}

对于 fi,j,kf_{i,j,k}（k>1k>1），可得：

fi,j,k=fi−1,j,k−1f_{i,j,k}=f_{i-1,j,k-1}

显然，ii 那一维可以省去，再加上前缀和优化，时间复杂度 O(n2m)O(n^{2}m)，空间复杂度 O(n2)O(n^{2})。

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
#include<iostream>
#include<vector>
using namespace std;
int a[7005];
int n,m;
int pre[7005];
const int mod=1000000007;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin>>n>>m;
    int maxn=0;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        maxn=max(maxn,a[i]);
    }
    vector<vector<int> > dp(m+5,vector<int>(maxn+5));
    for(int i=1;i<=m;i++){
        dp[i][1]=1;pre[i]=1;
    }
    int cnt=m;
    for(int i=2;i<=n;i++){
        int tmp=0;
        for(int j=1;j<=m;j++){
            int temp=0;
            for(int k=a[j];k>=1;k--){
                if(k==1){
                    dp[j][k]=(cnt-pre[j]+mod)%mod;
                }else{
                    dp[j][k]=(dp[j][k-1])%mod;
                }
                temp=(temp+dp[j][k])%mod;
                tmp=(tmp+dp[j][k])%mod;
            }
            pre[j]=temp;
        }
        cnt=tmp;
    }
    int ans=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=a[i];j++){
            ans=(ans+dp[i][j])%mod;
        }
    }
    cout<<ans<<endl;
    return 0;
}

得分：50pts。

思路二

AC 代码，设 fi,jf_{i,j} 表示第 ii 天学习第 jj 种算法的方案数，接着，枚举学习的天数，得：

fi,j=∑x=i−aji−1∑y=1(y≠j)mfx,yf_{i,j}=\sum_{x=i-a_j}^{i-1}\sum_{y=1(y\ne j)}^{m}f_{x,y}

接着，我们进行优化，用 preipre_{i} 表示 ∑x=1i∑y=1mfx,y\sum_{x=1}^{i}\sum_{y=1}^{m}f_{x,y}，用 cntj,icnt_{j,i} 表示 ∑x=1ifx,j\sum_{x=1}^{i}f_{x,j}，边 dp 边计算这两个，于是可得 fi,j=(prei−1−prei−aj−1)−(cntj,i−1−cntj,i−aj−1)f_{i,j}=(pre_{i-1}-pre_{i-a_j-1})-(cnt_{j,i-1}-cnt_{j,i-a_j-1})。最后，我们可以把 ii 这一维压掉，注意，取模时减法要加上模数再取模。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=7005;
int a[N];
int dp[N];
int pre[N];
int cnt[N][N];
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i];
		dp[i]=1;
		cnt[i][1]=1;
	}
	pre[1]=m;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(i>=a[j]+1){
				dp[j]=((pre[i-1]-pre[i-a[j]-1]+mod)%mod-(cnt[j][i-1]-cnt[j][i-a[j]-1]+mod)%mod+mod)%mod;
			}else{
				dp[j]=((pre[i-1])%mod-(cnt[j][i-1])%mod+mod+1)%mod;
			}
			cnt[j][i]=(cnt[j][i-1]+dp[j])%mod;
			pre[i]=(pre[i]+dp[j])%mod;
		}
		pre[i]=(pre[i]+pre[i-1])%mod;
	}
	int ans=0;
	for(int i=1;i<=m;i++){
		ans=(ans+dp[i])%mod;
	}
	cout<<ans<<endl;
	return 0;
}

Posted on Edited on

看到这道题，原以为是暴力枚举，一看题目难度和数据范围就明白了，这是道数学题（其实我是看标签知道的）。

好了，言归正传。

solution

  • 首先，区间长度等于 11 是不可能的，具体可以看这篇题解。
  • 当区间长度为 22 时，由于相邻的两个数互质，所以左端点 xx 满足 x(x+1)=mx(x+1)=m 此时化简方程得 x2+x−m=0x^{2}+x-m=0 用二次方程求根公式取较大的 −b+b2−4ac2a\frac{-b+\sqrt{b^{2}-4ac}}{2a} 得 x=−1+1+4m2x=\frac{-1+\sqrt{1+4m}}{2} 此时判断是否为整数即可。
  • 当区间长度大于 22 时，我可以暴力枚举左端点和右端点预处理存在 map 中。

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
#include<iostream>
#include<map>
#include<cmath>
using namespace std;
typedef unsigned long long ll;
map<ll,pair<ll,ll> > s;
const ll INF=1e18;
ll pgcd(ll x,ll y){//gcd
    if(!y){
        return x;
    }
    return pgcd(y,x%y);
}
inline void pdy(ll m){
    ll x=sqrt(1+4*m);
    if(x*x==1+4*m){//判断
        x--;
        if(!(x&1)){//判断
            s[m]=make_pair(x/2,x/2+1);
        }
    }
    return;
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll z;
    cin>>z;
    for(ll i=1;i<=2000000;i++){//预处理 i为左端点
        ll ans=i*(i+1);//求出前两个数的lcm
        for(ll j=i+2;;j++){
            ans/=pgcd(ans,j);//为了避免溢出，先除
            if(ans>INF/j){//是否超出最大值，等价于ans*j>INF,但是避免了溢出
                break;
            }
            ans*=j;
            if(!s.count(ans)){//如果先前没记录
                s[ans]=make_pair(i,j);
            }
        }
    }
    while(z--){
        ll m;
        cin>>m;
        //由于区间长的肯定左端点小，所以先看有没有区间较长的解
        if(s.count(m)){
            cout<<s[m].first<<" "<<s[m].second<<"\n";
        }else{
            //没有考虑长度为2时的解
            pdy(m);
            if(s.count(m)){
                cout<<s[m].first<<" "<<s[m].second<<"\n";
            }else{//如果还没有输出NIE
                cout<<"NIE\n";
            }
        }
    }
    cout<<flush;
    return 0;
}