orangejuice's blog

挂了请务必叫我

Posted on Edited on In

CF1296F - Harry The Potter

题目大意

给定 \(n\) 个数 \(a_i\) （ \(a_i\) 可以 \(<0\) ) 和两种操作

1.对于任意 \(a_i\) 和任意 \(x\) ， \(a_i\rightarrow a_i\pm x\)

2.对于任意 \(a_i,a_j\) 和 \(x\) , \(a_i\rightarrow a_i-x,a_j\rightarrow a_j-x-1\)

用最少操作将 \(a_i\) 都变成0

分析

考虑最基本的策略：

1.选择两个数 \(a_i,a_j\) ，将其中较大 \(a_i\) 的减去 \(a_j\pm 1\) ，同时删掉 \(a_j\)

2.最后剩下的就通过操作1解决

我们希望能能尽量多地通过操作1对于某一组数的子集进行匹配，

使得对于这个子集内的数操作的最后一次能使得 \(a_i,a_j\) 一起消失

那么现在问题分为两步

1. 判定一个子集合法

对于一个集合S,(|S|>1)，考虑对于它进行匹配

模拟每次选择两个进行操作的过程可以发现，实际上只需要操作到最终总和为0

而不断操作的过程中，实际上会修改每个 \(S_i\) 对于总和的贡献系数（最终是 \(\pm 1\) ）

同时，每次操作产生 \(\pm 1\) 的常数，并且最终的常数可以是任意一个能通过 \(|S|-1\) 个 \(\pm 1\) 生成的数

（因为可以通过调整操作使得合法）

那么可以给出判定集合匹配的条件

1.那么将这个集合分裂为两个集合 \(S_1,S_2\) 并且 \(S_1,S_2\ne \empty\) ，使得 \(|Sum_1-Sum_2|\) 能够通过 \(|S|-1\) 个 \(\pm 1\) 合成

即 \(|Sum_1-Sum_2|<|S|\) ，且 \(|Sum_1-Sum_2|\equiv |S|-1 \pmod 2\)

奇偶性对于加减法始终保持不变，可以直接判定

如果暴力枚举判定 \(S_1,S_2\) ，复杂度为 \(O(3^n)\approx 34e8\)

但是实际上有很多剪枝，比如如果有一个子集能完成匹配，自己就不用再匹配

然而也有稳定算法（。。。）

因为实际上要求的是 \(-|S|< Sum_1-Sum2 <|S|\) 的形式，可以 \(\text{Meet in the middle}\) +双指针解决

复杂度为 \(O(\sum \binom{n}{i} 2^{\frac{i}{2}} i)\) ，实际上由于常数不满这里几乎不用时间

稍微算一下复杂度级别，大概是 \(\sum n \binom{n-1}{i-1} \sqrt 2^{i}=\sqrt 2n(\sqrt 2+1)^{n-1}\) （实际上也并不小？）

2. 求解最优匹配

最终我们要将全集分解为若干子集以及散部，最大化子集个数

暴力枚举复杂度依然为 \(O(3^n)\) ，卡卡就能过（还很快

但是想用集卷积试试

设表示合法匹配集的多项式为 \(G(x)\)

则 \([x^S]G(x)=\left\{\begin{aligned} 1 && \text{S is a match}\\-\infty && \text{otherwise}\end{aligned} \right.\)

定义 \(\max\) 子集卷积 \([x^S]F\times G(x)=\max\{ [x^T]F(x)+[x^{S\Delta T}]G(x)\}\)

实际上我们求的的是 \(F(x)=\text{exp}{(G(x))}\) 的最大项

众所周知一次普通子集卷积/子集 \(\text{exp}\) 是 \(O(n^22^n)\) 的（如果用集合幂+形式幂exp的做法，常数可能会更小）

而取 \(\max\) 操作难以放入多项式做 \(\text{FMT}\) 以及乘法

额外增加 \(dp\) 值的维度会使得复杂度爆炸

但是鉴于 \(dp\) 值很小，可以在值域内压位，将加法转化为乘法

判断压位的每一位是否有出现即可，每次卷完只保留最大的一位

因为实际上匹配最多 \(\frac{n}{2}\) 个，需要压10位

因为多项式实际上很空，每位在卷积过程中出现的次数并不多

所以压位压位长度不需要太长 （虽然我long long 以内压不进去）

还是比较可以实现的，因此这一部分复杂度为 \(O(2^nn^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
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
94
95
96
97
98
typedef __uint128_t ull;
const int N=25,M=1<<20,INF=1e9+10;
const ull D=1000;

int n,m;
ll A[N],S[M];
int c[M],chk[M];
ull F[21][M],G[21][M];
ll X[1<<10],Y[1<<10];
int C;
ll B[N];

ll Fix(ll x,ll y){
	return floor((long double)x/y);
}
int Norm(ull &x){
	ull T=1,c=0;
	while(T*D<=x) T*=D,c++;
	return x=T,c;
}
void FMT(ull *F){
	for(int i=1;i<=m;i<<=1) {
		for(int l=0;l<=m;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				F[j+i]+=F[j];
			}
		}
	}
}
void IFMT(ull *F){
	for(int i=1;i<=m;i<<=1) {
		for(int l=0;l<=m;l+=i*2) {
			for(int j=l;j<l+i;++j) {
				F[j+i]-=F[j];
			}
		}
	}
}

int main() {
	rep(i,1,rd()) {
		ll x=rd<ll>();
		if(x) A[n++]=x;
	}
	if(!n) return puts("0"),0;
	m=(1<<n)-1;
	rep(i,1,m) {
		c[i]=c[i&(i-1)]+1,S[i]=S[i&(i-1)]+A[__lg(i&-i)];
		rep(j,0,n-1) if(i&(1<<j)) chk[i]|=chk[i^(1<<j)];
        // 剪枝，选取的每一个匹配集合都是极小的
		if(chk[i]) { chk[i]=2; continue; }
        // 先判定奇偶性是否合法
		if(c[i]<2 || (S[i]&1)==(c[i]&1)) continue;
        // Meet in the middle
        // 计算Sum1的范围，因为负数取整可能比较奇怪，所以写成这样
		ll l=Fix(S[i]-c[i]+2,2),r=Fix(S[i]+c[i]-1,2);
		C=X[0]=Y[0]=0;
		rep(j,0,n-1) if(i&(1<<j)) B[C++]=A[j];
		int k=C/2;
		int l1=(1<<k)-1,l2=(1<<(C-k))-1;
		rep(j,1,l1) X[j]=X[j&(j-1)]+B[__lg(j&-j)];
		rep(j,1,l2) Y[j]=Y[j&(j-1)]+B[__lg(j&-j)+k];
		
        // 需要特判掉空集和全集的情况，这是非法的
		rep(j,1,l2) if(X[0]+Y[j]>=l && X[0]+Y[j]<=r){ chk[i]=1; break; }
		rep(j,1,l1) if(X[j]+Y[0]>=l && X[j]+Y[0]<=r){ chk[i]=1; break; }
		rep(j,0,l2-1) if(X[l1]+Y[j]>=l && X[l1]+Y[j]<=r){ chk[i]=1; break; } 
		rep(j,0,l1-1) if(X[j]+Y[l2]>=l && X[j]+Y[l2]<=r){ chk[i]=1; break; }

		if(chk[i] || l1<=1 || l2<=1) continue;
		sort(X+1,X+l1),sort(Y+1,Y+l2);
		
		int p=l2-1;
		rep(j,1,l1-1) {
			while(p>0 && X[j]+Y[p]>r) p--;
			if(p>0 && X[j]+Y[p]>=l) { chk[i]=1; break; }
		}
	}
	rep(i,1,m) if(chk[i]==1) G[c[i]][i]=D;
	int ans=0;
	F[0][0]=1;
	rep(i,2,n) FMT(G[i]);
	rep(i,0,n) {
		if(i) IFMT(F[i]);
		rep(j,(1<<i)-1,m-(1<<(n-i))+1) if(F[i][j]) {
			if(c[j]!=i) F[i][j]=0;
			else cmax(ans,Norm(F[i][j]));
		}
		if(i+2<=n) {
			FMT(F[i]);
			rep(S,0,m) if(F[i][S]) rep(j,2,n-i) F[i+j][S]+=F[i][S]*G[j][S];
		}
	}
	printf("%d\n",n-ans);
}



Posted on Edited on In

CF1303G - Sum of Prefix Sums

题目大意

定义一个数列的 \(a_1,a_2,\cdots a_n\) 的权值为 \(\sum (n-i+1)a_i\)

对于一棵带点权的树，求所有路径数列最大的权值


分析

首先对于路径问题可以考虑无脑树分治

假设确定一条路径到达根的 \(b_1,b_2,\cdots b_m\) ，一条从根出发的路径 \(c_1,c_2,\cdots c_k\)

设 \(s_1=\sum (m-i+1)b_i,s_2=\sum b_i\) ， \(s_3=\sum (k-i+1)c_i\)

则易知其贡献为 \(s_1+s2\cdot k+s_3\)

考虑这是一个斜率优化的形式，可以通过凸包维护

但是不同的实现方法有很多，复杂度为基本上都是 \(O(n\log ^2n)\)

比如：

1.点分治+分治合并凸包+分治合并查询

2.点分治+李超树

3.边分治+凸包（需要 \(sort\) ，说不定不用？）

我无脑李超树

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
94
95
96
97
98
99
100
101
102
103
104
const int N=2e5+10,INF=1e9+10;

int n,m,a[N];
vector <int> G[N];
struct Node{
	ll k,b;
	Node(){}
	Node(ll k,ll b):k(k),b(b){}
	ll operator [] (ll x) const { return k*x+b; }
} s[N];
int ls[N],rs[N],cnt;
int New(){
	int u=++cnt;
	ls[u]=rs[u]=0,s[u]=Node(-INF,-INF);
	return u;
}
void Upd(int &p,int l,int r,Node x){
	if(x.k<0) return;
	if(!p) p=New();
	int mid=(l+r)>>1;
	if(s[p][mid]<x[mid]) swap(s[p],x);
	if(l==r) return;
	if(x[l]>s[p][l]) Upd(ls[p],l,mid-1,x);
	if(x[r]>s[p][r]) Upd(rs[p],mid+1,r,x);
}
ll Que(int p,int l,int r,int x){
	if(l==r) return s[p][x];
	int mid=(l+r)>>1;
	return max(s[p][x],x<=mid?Que(ls[p],l,mid,x):Que(rs[p],mid+1,r,x));
}

int vis[N],mi=1e9,rt,sz[N];
void FindRt(int n,int u,int f){
	int ma=0; sz[u]=1;
	for(int v:G[u]) if(v!=f && !vis[v]) {
		FindRt(n,v,u);
		cmax(ma,sz[v]),sz[u]+=sz[v];
	}
	cmax(ma,n-sz[u]);
	if(mi>ma) mi=ma,rt=u;
}

ll s1[N],s2[N],s3[N],s4[N],dep[N];
int L[N],I[N],dfn,R[N];
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	s2[u]=s2[f]+a[u],s1[u]=s1[f]+1ll*a[u]*(dep[u]+1);
	s4[u]=s4[f]+a[u],s3[u]=s3[f]+s4[u];
	I[L[u]=++dfn]=u;
	for(int v:G[u]) if(v!=f && !vis[v]) dfs(v,u);
	R[u]=dfn;
}
ll ans;
void Div(int n,int u){
	mi=1e9,FindRt(n,u,0),vis[u=rt]=1;
	s1[u]=s2[u]=a[u],s3[u]=s4[u]=dep[u]=0;
	
	I[L[u]=dfn=1]=u;
	for(int v:G[u]) if(!vis[v]) dfs(v,u);
	R[u]=dfn;

	cmax(ans,(ll)a[u]),cnt=rt=0;
	Upd(rt,1,dfn,Node(s2[u],s1[u]));
	for(int v:G[u]) if(!vis[v]) {
		rep(j,L[v],R[v]) {
			int i=I[j];
			cmax(ans,Que(rt,1,dfn,dep[i])+s3[i]);
		}
		rep(j,L[v],R[v]) {
			int i=I[j];
			Upd(rt,1,dfn,Node(s2[i],s1[i]));
		}
	}
	cnt=rt=0;
	drep(k,G[u].size()-1,0) {
		int v=G[u][k];
		if(vis[v]) continue;
		rep(j,L[v],R[v]) {
			int i=I[j];
			cmax(ans,Que(rt,1,dfn,dep[i])+s3[i]);
		}
		rep(j,L[v],R[v]) {
			int i=I[j];
			Upd(rt,1,dfn,Node(s2[i],s1[i]));
		}
	}
	cmax(ans,Que(rt,1,dfn,dep[u])+s3[u]);
	for(int v:G[u]) if(!vis[v]) {
		if(sz[v]>sz[u]) sz[v]=n-sz[u];
		Div(sz[v],v);
	}
}

int main(){
	s[0]=Node(-1,-INF);
	n=rd();
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),G[v].pb(u);
	}
	rep(i,1,n) a[i]=rd();
	Div(n,1);
	printf("%lld\n",ans);
}

Posted on Edited on In

CF1305G - Kuroni and Antihype

题目大意

有 \(n\) 个人，每个人有一个权值 \(a_i\)

每个人可以自己选择放入集合，不获得分数

或者一个已经在集合中的人 \(i\) 可以把一个 \(a_i \ \text{and}\ a_j=0\) 的 \(j\) 放入集合，并且获得 \(a_i\) 的分数

求最大得分总和


模型分析

按照原题的模型分析，视 \(a_i\rightarrow a_j\) 为一条权值为 \(a_i\) 边，则实际上求的是 最大外向森林

考虑加入 \(a_0=0\) ，且 \(a_0\) 初始在集合中，一个人自己放入集合视作被 \(0\) 放入集合

那么问题简化为求以0为根的 最大外向树

进一步观察会发现：

在外向树上每个点贡献次数就是 \(a_i\cdot (deg_i-1)\)

那么最大化 \(a_i\cdot (deg_i-1)\) 等价于最大化 \(\sum a_i\cdot deg_i\)

那么我们将一条边的权值 \(a_i\rightarrow a_j\) 改为 \(a_i+a_j\) ，此时边双向权值相同

问题就变成了求最大生成树


计算生成树

只有暴力解法

倒着枚举 \(a_i+a_j=S\) ，枚举 \(S\) 的子集 \(T\) 就能确定两个点

并查集处理加边即可，复杂度为 \(O(\cfrac{3^{18}}{2}\cdot \alpha(n))\)

\(\text{CodeForces}\) 真的有点快！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const int N=1<<18,INF=1e9+10;

int n,a[N],F[N];
ll ans;
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }

int main(){
	n=rd();
	rep(i,1,n) {
		int x=rd();
		a[x]++,ans-=x;
	}
	a[0]++;
	rep(i,0,N-1) F[i]=i;
	drep(i,N-1,1) {
		for(int S=i,T;(S^i)<=S;S=(S-1)&i) if(a[S] && a[T=S^i] && Find(S)!=Find(T)) {
			ans+=1ll*(a[S]+a[T]-1)*i;
			a[S]=a[T]=1,F[Find(S)]=Find(T);
		}
	}
	printf("%lld\n",ans);
}

Posted on Edited on In

CF1366G - Construct the String

题目大意

给定一个初始串 \(S\) 和目标串 \(T\)

其中 \(S\) 除了包含字母外还包含删除标记'.'

具体的 \(S\) 表示的字符串 \(f(S)\) ，就是依次加入每个字母，或者在删除标记处删除上一个字符（不存在这个字符则非法）

求删除 \(S\) 中最少的字符，使得 \(f(S')=T\)


吐槽

\(O(n^2)\) 出 \(n\leq 10^4\) ???



朴素dp分析

这种题目容易想到记录在 \(T\) 中匹配位置的 \(dp\) ，通过枚举 \(S\) 的每一个字符

1.匹配

2.手动删除

3.被'.'删除

然而被'.'删除的情况实际难以处理，因为无法额外记录待定的'.'个数


基于括号树的思路

考虑对于不完全的括号序列的包含关系建立树，注意到

1.一个已经和'.'匹配的字符，不需要考虑它被手动删除的情况

2.一个字符能够保留，当且仅当所有跨过其的右括号被删除

跨过其的右括号即祖先中的右括号

所以此时dp决策可以简单地归纳为

1.保留一整个匹配括号的子树，进入后面的匹配

2.否则，删除右括号，并且决定自己这个字符是否匹配，然后递归进入子树

代码没写


更简洁的表述

实际上与上面类似，但是更加简化了模型，转移可以简单归纳为

1.匹配当前字符

2.删除当前字符

3.找到当前字符匹配右括号，跳过这一段

原理：

实际上朴素dp缺陷就在于：

如果当前这个字符被后面的某一个'.'删除，却又无法匹配时，无法被加入状态

此时手动补充直接跳到删除这个字符的位置

充分性理解：在新串中匹配该字符的右括号 和 当前后缀中匹配该字符的括号相同

如果要让这个字符被'.'删除，那么到当前后缀中匹配该字符的括号为止，中间的部分不可能保留

手动删除只会让匹配该字符的括号右移，这不会更优

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N=10010,P=1e9+7;

int n,m;
char s[N],t[N];
int dp[N][N];

int main(){
	scanf("%s%s",s,t),n=strlen(s),m=strlen(t);
	rep(i,0,n) memset(dp[i],63,(min(m,i)+2)<<2);
	rep(i,*dp[0]=0,n-1) {
		if(s[i]!='.') {
			int j=i,c=0;
			do c+=s[j++]=='.'?-1:1;
			while(c && j<n);
			if(!c) rep(k,0,min(m,i)) cmin(dp[j][k],dp[i][k]);
		}
		rep(j,0,min(m,i)) {
			cmin(dp[i+1][j],dp[i][j]+1);
			if(s[i]==t[j]) cmin(dp[i+1][j+1],dp[i][j]);
		}
	}
	printf("%d\n",dp[n][m]);
}

Posted on Edited on In

CF1379E - Inverse Genealogy

题目大意

给定 \(n,k\) ，要求构造一棵二叉树满足

1.除了叶子以外的节点有两个儿子

2.称一个节点是特殊的：两个儿子中，一个儿子 \(size\) 至少是另一个的两倍

要求特殊的节点恰好有 \(k\) 个


分析

首先考虑一些简单的情况

  1. \(2|n\) 时不存在合法二叉树

  2. \(n\) 个节点的树，能够包含 \(0\) 个特殊节点当且仅当 \(\exists 2^i-1=n\)

也就是能够构成一棵完美二叉树

3.除了 \(2\) 情况外的树，顺次放置每个节点得到的二叉树恰好包含1一个特殊点

那么当 \(k\leq 1\) 时的情况均可以被解决

否则，考虑通过加上一条极长的链来构造

即构造一个一边儿子大小为1，另一边顺次相接的链，这样能够做到最大利用点数

最多能得到 \(\frac{n-3}{2}\) 个特殊点

然而我们必须处理剩余点的分配，下面给出的构造能够解决 \(k\in [2,\frac{n-3}{2}]\) 的情况

通用构造

经过不断尝试得到的构造方法，好像很强

假设得到一条长度为 \(m\) 且右偏的上述链，将剩下的点分配到两个地方

1.根的左儿子

2.链底的右儿子

分配方式就是顺次放置每个节点得到的二叉树

设剩下节点个数+根的左儿+链底的右儿子 \(=c\)

设 \(f(n)=1-[\exists 2^i-1=n]\) ，特别的，当 \(2|n\) 时， \(f(n)=\infty\)

假设根的左儿子分配大小为 \(x\) ，则新的树特殊点数目就是

\(m-2+f(x)+f(c-x)+[c-x\ge 3]+[x\ge 2(n-1-x) \text{ or } (n-1-x)\ge 2x]\)

枚举每一个 \(x\in[1,c-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
const int N=1e5+10;

#define NO puts("NO"),exit(0)

int n,m;
int fa[N];

int chk(int a,int b) {
	if(a>b) swap(a,b);
	return a*2<=b;
}

void Out(){
	puts("YES");
	rep(i,1,n) printf("%d ",fa[i]);
	exit(0);
}

int Get(int l,int r) {
	rep(i,l+1,r) fa[i]=l-1+(i-l+1)/2;
	return l;
}

int Mincost(int x){
	if(~x&1) return 1e9;
	rep(i,0,17) if(x+1==(1<<i)) return 0;
	return 1;
}


int main(){
	n=rd(),m=rd();
	if(Mincost(n)==m) Get(1,n),Out();
	if(m==0) NO;
	if(~n&1) NO;
	if((m+1)*2>=n) NO;
	int r=(m+1)*2+1;
	if(r==n) {
		rep(i,1,m+1) fa[i*2]=i*2-1,fa[i*2+1]=i*2-1;
		Out();
	}

	r-=2;
	int c=n-r+2;
	if(m>1) rep(x,1,c-1) if(Mincost(x)+Mincost(c-x)-!chk(c-x,n-1-(c-x))+(x>=3)==1) {
		rep(i,1,m) fa[i*2]=i*2-1,fa[i*2+1]=i*2-1;
		int t=max(0,r-2);
		fa[Get(r-1,r+x-2)]=t;
		fa[2]=t;
		fa[Get(r+x-1,n)]=1;
		Out();
	}
	NO;
}

Posted on Edited on In

CF1368G - Shifting Dominoes

题目大意

给定一个被 \(1\times 2\) 的骨牌（横向或者竖向）铺满的方格图

现在可以拿走一个骨牌，之后任意一个骨牌可以沿着其放置方向左右移动至多一步

求最终两个空位所在不同位置的方案数


分析

观察一个空位的移动

如果上/下/左/右边是一条骨牌，则可以移动到该骨牌所在的上/下/左/右边方格

将这个移动方式构成一个有向图（当然忽略反复横跳的情况）

大胆猜测此时你会发现它是 两片外向树森林，下面说明三个充分条件

1.跳跃的过程为 \((x,y)\rightarrow (x\pm 2,y\pm 2)\) ，显然 \(x+y\) 的奇偶性不变，故可以黑白染色分为两部分

2.一个点至多有一条入边：一个点的入边只能来自其所在骨牌的另一边

3.图中不存在环：

假设构成了一个环，此时这些边对应的骨牌围成一个不规则的环

从环的某一个角出发，向四周走，发现其余所有点总能完成一一匹配

也就是说，环内部包含的点个数为奇数，显然不存在这样的覆盖方案


答案计算

考虑移除一张骨牌生成两个点 \((x,y)\) ，两个点分属于两片森林，并且可以向下走

不妨求出森林的 \(\text{dfs}\) 序，此时问题变成了一个二维空间矩形覆盖问题

可以扫描线+线段树解决

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
94
const int N=2e5+10;

int n,m,d;
string s[N];
int I(int x,int y){ return (x-1)*m+y; }
ll ans;

vector <int> G[N];
int col(int u){ return ((u-1)%m+(u-1)/m)&1; }

void Link(int u,int v){ G[u].pb(v),ind[v]++; }
int ind[N],L[N],R[N],dfn;
void dfs(int u,int f){
	L[u]=++dfn;
	for(int v:G[u]) if(v!=f) dfs(v,u);
	R[u]=dfn;
}

// 线段树维护扫描过程中第二维未被覆盖的点个数
struct Node{
	int mi,x;
	Node operator + (const Node _) const {
		Node res;
		res.mi=min(mi,_.mi),res.x=0;
		if(mi==res.mi) res.x+=x;
		if(_.mi==res.mi) res.x+=_.x;
		return res;
	}
} tr[N<<2];
int t[N<<2];
void Down(int p){
	if(!t[p]) return;
	rep(i,p<<1,i+1) t[i]+=t[p],tr[i].mi+=t[p];
	t[p]=0;
}
void Upd(int p,int l,int r,int ql,int qr,int x){
	if(ql<=l && r<=qr) {
		t[p]+=x,tr[p].mi+=x;
		return;
	}
	Down(p);
	int mid=(l+r)>>1;
	if(ql<=mid) Upd(p<<1,l,mid,ql,qr,x);
	if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
	tr[p]=tr[p<<1]+tr[p<<1|1];
}

struct Update{
	int p,l,r,x;
	bool operator < (const Update __) const { return p<__.p; }
} U[N*2];
int C;

void Add(int x,int y){
	if(col(x)) swap(x,y);
	U[++C]=(Update){L[x],L[y],R[y],1};
	U[++C]=(Update){R[x]+1,L[y],R[y],-1};
}
void Build(int p,int l,int r){
	tr[p]=(Node){0,r-l+1};
	if(l==r) return;
	int mid=(l+r)>>1;
	Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
}

int main(){
	n=rd(),m=rd();
	rep(i,1,n) {
		cin>>s[i];
		rep(j,1,m) {
			if(s[i][j-1]=='U') if(i>1) Link(I(i-1,j),I(i+1,j));
			if(s[i][j-1]=='D') if(i<n) Link(I(i+1,j),I(i-1,j));
			if(s[i][j-1]=='L') if(j>1) Link(I(i,j-1),I(i,j+1));
			if(s[i][j-1]=='R') if(j<m) Link(I(i,j+1),I(i,j-1));
		}
	}
    // 获得dfs序
	rep(i,1,n*m) if(!ind[i]) dfs(i,0);
	rep(i,1,n) {
		rep(j,1,m) {
			if(s[i][j-1]=='U') Add(I(i,j),I(i+1,j));
			if(s[i][j-1]=='L') Add(I(i,j),I(i,j+1));
		}
	}
	Build(1,1,dfn);
	sort(U+1,U+C+1);
	int p=1;
	rep(i,1,dfn) {
		while(p<=C && U[p].p<=i) Upd(1,1,dfn,U[p].l,U[p].r,U[p].x),p++;
		int c=dfn-(tr[1].mi==0?tr[1].x:0);
		ans+=c;
	}
	printf("%lld\n",ans);
}

Posted on Edited on In

CF1392H - ZS Shuffles Cards

题目大意

给定 \(n\) 张卡和 \(m\) 个终止符，初始时随机打乱成排列，每次操作选出最前面的卡 \(x\) 拿走

1.如果 \(x\) 不是终止符，将 \(x\) 放入集合

2.如果 \(x\) 是终止符，那么重新打乱 \(n+m\) 张卡

求期望多少步 \(S\) 变成全集


分析

令 \(dp_i\) 表示当前手上有 \(i\) 张不同卡时期望多少步结束

按轮考虑，一轮期望操作次数固定，即

\(\displaystyle \frac{\displaystyle \sum _{i=0}^n \binom{n+m-i-1}{m-1}(i+1)}{\displaystyle \binom{n+m}{m}}\)

现在考虑从 \(dp_{i+j}\) 转移过来，当前的牌可以分为三类

1.手里有的

2.手里没有的

3.终止牌

我们计算 \(dp_{i+j}\) 向 \(dp_i\) 转移时的概率，并不需要管1类卡，只需要考虑2,3类卡的相对顺序

不妨直接忽略手里的 \(i\) 张卡，得到转移系数

\(dp_{i+j}\rightarrow dp_i: \cfrac{\displaystyle \binom{n-i-j-1}{m-1}}{\displaystyle \binom{n-i+m}{m}}\)

容易发现可以将 \(\displaystyle dp_{i+j}\binom{n-i-j-1}{m-1}\) 累和完成

注意 \(dp_i\) 有向 \(dp_{i}\) 自己的转移，需要解一次方程，因此需要求逆元

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
const int N=4e6+10,P=998244353;

int n,m;
int I[N],J[N];
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int F[N];
ll C(int n,int m){ return 1ll*J[n]*I[m]%P*I[n-m]%P; }
ll IC(int n,int m){ return 1ll*I[n]*J[m]%P*J[n-m]%P; }

int main(){
	rep(i,*J=1,N-1) J[i]=1ll*J[i-1]*i%P;
	I[N-1]=qpow(J[N-1]);
	drep(i,N-1,1) I[i-1]=1ll*I[i]*i%P; 
	n=rd(),m=rd();
	ll s=0,inv=IC(n+m,m),coef=0;
	rep(i,0,n) coef=(coef+C(n+m-i-1,m-1)*(i+1))%P;
	coef=coef*inv%P;

	drep(i,n-1,0) {
		ll p=C(n+m-i-1,m-1),t=IC(n-i+m,m);
		F[i]=(s*t%P+coef)%P*qpow(P+1-p*t%P)%P;
		s=(s+1ll*p*F[i])%P;
	}
	printf("%d\n",F[0]);
}

Posted on Edited on In

CF1392I - Kevin and Grid

题目大意

给定一张网格图，每个点上 \((i,j)\) 写着 \(a_i+b_j\)

对于一个给定阈值 \(x\) ，将图分为 \(a_i+b_j<x\) 和 \(a_i+b_j\ge x\) 两组连通块

定义一个能够连通到网格图边界的连通块的价值为1，否则为2

有 \(q\) 次查询，每次给定 \(x\) ，求两种连通块价值之差


分析

是网格图上的连通块计数，并且看起来无法真的搜索连通块，于是想到平面图的欧拉定理

欧拉定理连通块计数式子 \(C=|V|-|E|+|F|-1\)

考虑和题目给定的奇妙的价值有什么关系

显然价值是连通块个数加上被包含的连通块个数

答案应该是 \(S_1-S_2=|V_1|-|V_2|-|E_1|+|E_2|+|F_1|-|F_2|+1类被包含个数-2类被包含个数\)

容易观察发现，当一个1类连通块被包含时， \(F_2\) 就增加1

也就是说 \(1类被包含个数-|F_2|\) 最终只剩下 ：外层无限区域 以及 四相邻连通块

设四个相邻连通块的个数为 \(D_1,D_2\)

那么 \(S_1-S_2=|V_1|-|V_2|-|E_1|+|E_2|+D_1-D_2\)

关于如何统计 \(a_i+b_j\leq x\) 的个数，还多组查询，你猜猜要干嘛....

比较不用过脑子的，做7次FFT乘法即可，也可以共用一些FFT结果

\(\downarrow \downarrow \downarrow\) 我没有脑子！！！ (/ha/ha/ha/ha/ha)

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
const int N=1<<18;
const db PI=acos(-1);

struct Cp{
	db a,b;
	Cp(){}
	Cp(db a,db b):a(a),b(b){}
	Cp operator + (const Cp _) const{ return Cp(a+_.a,b+_.b);  }
	Cp operator - (const Cp _) const{ return Cp(a-_.a,b-_.b);  }
	Cp operator * (const Cp _) const{ return Cp(a*_.a-b*_.b,a*_.b+b*_.a);  }
} R[N];
int rev[N];
void FFT(Cp *a,int f){
	rep(i,0,N-1) if(i<rev[i]) swap(a[i],a[rev[i]]);
	static Cp e[N>>1];
	e[0]=Cp(1,0);
	for(int i=1;i<N;i<<=1) {
		Cp t(cos(PI/i),f*sin(PI/i));
		for(int j=i-2;j>=0;j-=2) e[j+1]=(e[j]=e[j>>1])*t;
		for(int l=0;l<N;l+=i*2){
			for(int j=l;j<l+i;++j) {
				Cp t=a[j+i]*e[j-l];
				a[j+i]=a[j]-t;
				a[j]=a[j]+t;
			}
		}
	}
	if(f==-1) rep(i,0,N-1) a[i].a/=N;
}

// 这个变量名求轻喷
int n,m,q;
int a[N],b[N];
ll A[N],B[N],C[N],D1[N],D2[N];
// A为<x块个数
// B为<x边数
// C为>=x边数
// D1,D2同上述

Cp D[N],E[N],F[N],G[N],H[N],I[N];

void Add(ll *a,Cp *b,Cp *c) {
	rep(i,0,N-1) R[i]=b[i]*c[i];
	FFT(R,-1);
	rep(i,0,N-1) a[i]+=round(R[i].a);
}

int main(){
	rep(i,0,N-1) rev[i]=(rev[i>>1]>>1)|((i&1)*(N/2));
	n=rd(),m=rd(),q=rd();
	rep(i,1,n) {
		D[a[i]=rd()].a++;
		if(i>1) F[max(a[i-1],a[i])].a++, G[min(a[i-1],a[i])].a++;
	}
	rep(i,1,m) {
		E[b[i]=rd()].a++;
		if(i>1) H[max(b[i-1],b[i])].a++, I[min(b[i-1],b[i])].a++;
	}
	FFT(D,1),FFT(E,1); FFT(F,1),FFT(G,1); FFT(H,1),FFT(I,1);
	Add(A,D,E);
	Add(B,D,H),Add(B,F,E);
	Add(C,D,I),Add(C,G,E);
	Add(D1,F,H),Add(D2,G,I);
	rep(i,1,N-1) A[i]+=A[i-1],B[i]+=B[i-1],D1[i]+=D1[i-1];
	drep(i,N-2,0) C[i]+=C[i+1],D2[i]+=D2[i+1];
	while(q--) {
		int x=rd();
		ll ans=1ll*n*m-2*A[x-1]-C[x]+B[x-1]+D2[x]-D1[x-1];
		printf("%lld\n",ans);
	}
}

Posted on Edited on In

CF1393E2 - Twilight and Ancient Scroll (harder version)

题目大意

给定 \(n\) 个串 \(S_i\) ，求在每个串中至多删除一个字符（可以删到空）

最终 \(S'_i\) 字典序单调不减的方案数



dp

显然是记录上一个串删除的位置 \(j\) ，得到 \(dp_j\) ，依次考虑每个串

设 \(S\) 为当前串， \(T\) 为上一个串

每次我们枚举当前串删除的位置 \(i\) ，不妨设得到的新串为 \(S'\) ，考虑对于 \(S'\) 找到所有合法转移

设 \(L=LCP(S,T)\) ，在 \(T\) 中删除位置为 \(t\)

  1. \(t>L+1\)

则可以根据 \(T_{L+1}\) 和 \(S'_{L+1}\) 的关系确定 \(T'\) 与 \(S'\) 的关系，只需要处理一个后缀和 \(suf_i\)


2.设 \(p\) 为 \(T_{L+1}\) 向前延伸且字符相同的最长位置， \(t\in[p,L+1]\)

此时，删除 \(T_t\) 可能会使得 \(L'>L\) ，所以提出来特殊处理

显然 \(t\in[p,L+1]\Leftrightarrow t=L+1\) ，那么对于得到的新串可以再求 \(LCP(S',T')\) 来判断大小

只需要一个区间和


  1. \(t<p\) ，此时 \(L'=LCP(S',T')<L\)

由于 \(L'<L\) ,比较 \(S',T'\) 相当于比较 \(T_{t:},T_{t+1:}\)

其中 \(T_{t:}\) 表示 \(T\) 在 \(t\) 开始的后缀，那么预处理找到所有合法的 \(t\) ，累前缀和即可得到 \(pre_{p-1}\)


关于实现

写 \(\text{SA,SAM}\) 就完蛋了

由于删除一个字符之后，求 \(LCP\) 的两个串就是在原串基础上进行 \(\pm 1\) 的偏移

线性预处理三个 \(LCP\) 数组即可，当然真正求的时候需要分类讨论一下(真的，就一下/md)


判断 \(T_{t:},T_{t+1:}\) 容易倒着线性预处理出来，在代码里是 \(chk_i\)


所有操作均可以线性处理，时间复杂度为 \(O(L)\) ，77ms

Tips:

比较过程中容易出现奇妙的越界，我写得很丑

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
const int N=1e6+10,P=1e9+7;

int n,m;
char A[2][N],*S=A[0],*T=A[1];
int X[N],Y[N],Z[N];
int dp[N],F[N],suf[N],pre[N],chk[N],L[N];

int main(){
	rep(_,1,rd()) {
		swap(S,T),swap(n,m);
		scanf("%s",S+1),n=strlen(S+1);
		rep(i,n+1,m+2) S[i]=1;
		rep(i,m+1,n+2) T[i]=-1;
		if(!m) {
			rep(i,1,n+1) dp[i]=1;
			continue;
		}
		rep(i,max(n,m)+1,i+2) X[i]=Y[i]=Z[i]=0;
		drep(i,max(n,m),1) {
			X[i]=S[i]==T[i]?X[i+1]+1:0;
			Y[i]=S[i]==T[i+1]?Y[i+1]+1:0;
			Z[i]=S[i+1]==T[i]?Z[i+1]+1:0;
		}

		// initiate
		suf[m+2]=0;
		drep(i,m+1,1) suf[i]=suf[i+1]+dp[i],Mod1(suf[i]);
		drep(i,m,1) chk[i]=T[i]!=T[i+1]?T[i]>T[i+1]:chk[i+1];
		rep(i,1,m+1) L[i]=T[i]==T[i-1]?L[i-1]:i;
		rep(i,1,m) pre[i]=pre[i-1]+chk[i]*dp[i],Mod1(pre[i]);


		rep(i,1,n+1) {
			int l=min(X[1],i-1);
			if(l==i-1) l+=Z[i];
			F[i]=0;

			auto I=[&](int x){ return (x>=i)+x; };

			// type1 , deleted pos > l+1
			if(T[l+1]<=S[I(l+1)]) F[i]+=suf[l+2],Mod1(F[i]);
			int p=L[l+1];
			
			// type2 ,delete T between [p..l+1]  ,the same as we delete T[l+1]
			int r=0; // r= LCP(S'[l+2],T[l+2]) ,check if delete T[l+1], T'<=S'
			if(l+1<i) r+=min(i-l-1,Y[l+1]);
			if(r==max(0,i-l-1)) r+=X[l+2+r];
			if(T[l+2+r]<=S[I(l+1+r)]) F[i]=(F[i]+0ll+suf[p]-suf[l+2]+P)%P;
			
			// type3 , delete T at [1,p-1], so LCP'<l , and we determine T'<=S' by chk[i]
			F[i]=(F[i]+pre[p-1])%P;
		}
		rep(i,1,n+1) dp[i]=F[i];
	}
	int ans=0;
	rep(i,1,n+1) ans+=dp[i],Mod1(ans);
	printf("%d\n",ans);
}

Posted on Edited on In

CF1404D - Game of Pairs

题目大意

两个人Van游戏，

第一个人对于 \(1,2,\cdots,2n\) 分成 \(n\) 组

第二个人尝试从每组中选一个数，使得选出数的和是 \(2n\) 的倍数

你选一个人Van，然后赢了交互器


分析

考虑从一个 \(\mathbb{Naive}\) 的构造开始：

分成 \(n\) 组，每组都是 \((i,n+i)\)

为什么这么构造？因为每组两个数 \(\mod n\) 都相同

那么最终选出的和 \(Sum\mod n=\frac{n(n+1)}{2}\)

观察到，在 \(n\) 为偶数时， \(Sum \mod n=\frac{n}{2}\ne 0\) ，此时必然无解

然后我没过脑子随机化艹出了n为奇数的方案，但是没事下面有确定解法

而 \(n\) 为奇数时，我们只需要类似找到一组 \(\mod n=0,1,2,\cdots ,n-1\) 的方案

此时必然满足 \(Sum\mod n=0\)

这只需要对于给出的每组 \((a_i,b_i)\) ，对于 \(a_i\mod n,b_i\mod n\) 连一条边

然后在最终的置换环上进行决策即可


然而我们需要 \(Sum\mod 2n=0\)

又 \(\frac{(2n+1)2n}{2}=n(2n+1)\mod 2n=n\) ，故如果找到的 \(Sum\mod 2n=n\) ，取当前方案的补集即可

0%