orangejuice's blog

挂了请务必叫我

Posted on Edited on In

CF1483F - Exam

题目大意

给定 \(n\) 个不同串 \(s_i\) ，令 \(s_i\sub s_j\) 表示 \(s_i\) 是 \(s_j\) 的子串

求所有二元组 \((i,j)(i\ne j)\) 满足

\(s_i\sub s_j,\nexists k\ne i,k\ne j,s_i\sub s_k\sub s_j\)


分析

首先可以说明答案是 \(O(\sum |s_i|)\) 级别的

对于每个 \(s_j\) 考虑其枚举 \(r\) 作为 \(s_i\) 的右端点，则 \(s_i\) 只有最长的一个会贡献答案

故每个右端点最多对应一个 \(s_i\)

一般情况下，判断子串相同的问题我们需要 \(\text{SAM}\)

但是鉴于这道题实际上需要判别的子串只有 \(n\) 个，而维护匹配只需要 \(\text{AC}\) 自动机，所以不需要 \(\text{SAM}\)

那么可以在 \(\text{AC}\) 自动机上预处理每个匹配节点在 \(\text{fail}\) 树上最近的有效祖先

即对于每个右端点找到了最长的 \(s_i\)

可以对于找到的 \(s_i\) 简单去重，但是仍然存在以下多余计算

  1. \(s_i\) 所对应的 \([l,r]\) 被某一个 \(s_i'\) 对应的 \([l',r']\) 包含的情况，可以 \(O(n)\) 判断区间包含干掉

2.一个 \(s_i\) 在这个位置被计算，但是实际上在其他位置被包含

实际上，这只需要判断 \(s_i\) 每一次被出现是否都是有效的即可

可以用树状数组+ \(\text{dfs}\) 序维护 \(s_i\) 出现的次数

时间复杂度为 \(O((\sum |s_i|)\log (\sum |s_i|))\) ，空间复杂度为 \(O((\sum |s_i|)|\Sigma|)\)

似乎是Codeforces上最快的Submission?

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

int n;
int fail[N],lst[N],trie[N][26],End[N],dep[N],fa[N],L[N],R[N],I[N],dfn,cnt;
struct Edge{
	int to,nxt;
} e[N<<1];
int head[N],ecnt;
void AddEdge(int u,int v) {
	e[++ecnt]=(Edge){v,head[u]};
	head[u]=ecnt;
}

void dfs(int u) {
	I[L[u]=++dfn]=u;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(!lst[v]) lst[v]=lst[u];
		dfs(v);
	}
	R[u]=dfn;
}

void Build() {
	static queue <int> que;
	rep(i,0,25) if(trie[0][i]) que.push(trie[0][i]);
	while(!que.empty()) {
		int u=que.front(); que.pop();
		AddEdge(fail[u],u);
		rep(i,0,25) {
			int &v=trie[u][i];
			if(!v) v=trie[fail[u]][i];
			else fail[v]=trie[fail[u]][i],que.push(v);
		}
	}
	dfs(0);
}

struct BIT{
	int s[N];
	void Add(int p,int x){ while(p<=dfn) s[p]+=x,p+=p&-p; }
	int Que(int p){
		int res=0;
		while(p) res+=s[p],p-=p&-p;
		return res;
	}
	int Que(int l,int r){ return Que(r)-Que(l-1); }
} T;

char s[N];
int A[N],B[N],C;

int main(){
	n=rd();
	rep(i,1,n) {
		scanf("%s",s+1);
		int u=0;
		for(int j=1;s[j];++j) {
			int &v=trie[u][s[j]-'a'];
			if(!v) v=++cnt,fa[v]=u,dep[v]=dep[u]+1;
			u=v;
		}
		lst[End[i]=u]=u;
	}
	Build();
	int ans=0;
	rep(i,1,n) {
		C=0;
		for(int u=End[i],mi=1e9;u;u=fa[u]) {
			T.Add(L[u],1);
			int p=lst[u==End[i]?fail[u]:u];
			int l=dep[u]-dep[p]+1;
			if(!p || mi<=l) continue; // none or being included
			mi=l;
			if(!B[p]) A[++C]=p;
			B[p]++;
		}
		rep(j,1,C) {
			ans+=T.Que(L[A[j]],R[A[j]])==B[A[j]];
			B[A[j]]=0;
		}
		for(int u=End[i];u;u=fa[u]) T.Add(L[u],-1);
	}
	printf("%d\n",ans);
}

Posted on Edited on In

CF1383C - String Transformation 2

题目大意

给定串 \(A,B\) ，字符集为前20个小写字母

每次操作取 \(A\) 中同种字符 \(x\) 的一个子集，全部改成另一个字符 \(y\)

求最少操作次数，使得 \(A\) 变成 \(B\)


分析

图论模型

容易发现，每个 \(A_i\rightarrow B_i\) 可以看做一条有向边，操作也是如此

那么问题实际上就是：

求一个最少条边的有向图，每条边有一个编号 \(i\)

使得对于每一对 \(A_i\rightarrow B_i\) ，均存在一个编号递增的有向路径


暴力求解

先对于 \(A_i\rightarrow B_i\) 建立有向图

考虑对于每一个弱连通块，最后形成的图中这些点也必然构成弱连通块

那么一定可以在最终的弱连通块中提取一棵生成树（忽略边的方向）

又可以对于生成树按照边的拓扑序排列，构成一条长链，这样的构造一定不劣

那么分析可行的方案：

1.对于每个弱连通块，先定一条链

2.对于链上的反边所构成的连通块，只需要考虑对于每个新的连通块生成一条链即可

由于范围极小，只有20个点，可以直接状压这条链

对于剩余的连通块，在计算答案时可以考虑对于每个连通块中编号最小的点不算入答案

由于反图的边都是逆着当前的拓扑序的，所以编号最小的点就是没有边连向前面的点

也就是 \(dp\) 最少的，有反边连入的点的个数，复杂度为 \(O(2^{20}\cdot 20)\)

不知道有没有可能写多项式复杂度的

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
const int N=30,M=1e5+10,INF=1e9+10;

int n;
char s[M],t[M];
int dp[1<<20];
int G[N][N],E[N],I[N];

int vis[N],C;
void dfs(int u){
	if(vis[u]) return;
	vis[u]=1,I[C++]=u;
	rep(i,0,19) if(G[u][i] || G[i][u]) dfs(i);
}

int Solve(){
	int A=(1<<n)-1; 
	rep(i,0,A) dp[i]=INF;
	dp[0]=0;
	rep(S,0,A) rep(i,0,n-1) if(~S&(1<<i)) 
			cmin(dp[S|(1<<i)],dp[S]+!!(E[i]&S));
	return dp[A]+n-1;
}

int main(){
	rep(_,1,rd()) {
		rd(),n=0;
		scanf("%s%s",s+1,t+1);
		memset(G,0,sizeof G),memset(vis,0,sizeof vis);
		for(int i=1;s[i];++i) {
			int x=s[i]-'a',y=t[i]-'a';
			if(x==y) continue;
			G[x][y]=1;
		}
		int ans=0;
		rep(u,0,19) if(!vis[u]) {
			C=0,dfs(u);
			rep(i,0,C-1) {
				E[i]=0;
				rep(j,0,C-1) E[i]|=G[I[i]][I[j]]<<j;
			}
			n=C,ans+=Solve();
		}
		printf("%d\n",ans);
	}
}

Posted on Edited on In

CF1503E - 2-Coloring

题目大意

给定一个 \(n\times m\) 网格图，给每个格子黑白染色，使得最终

每行恰好只有一条黑色线段，每列恰好只有一条白色线段

求方案数


分析

这种东西当然是分析好情况就ok了

大概分几种情况

1.QQ截图20210512171601.png

2.QQ截图20210512171647.png

3.QQ截图20210512175626.png

为什么要把第三种拿出来说呢，实际上第三种是1和2的交（黑白都是梯形，确信）

那么枚举中间的分界线，根据中间相距最近的两个点的位置就能用组合数确定答案

（虽然代码里不是组合数）

前缀和优化即可 \(O(nm)\) ，注意两个梯形可以对称，所以最后答案*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

const int N=2030,INF=1e9+10,P=998244353;

int n,m;
int dp[N][N],ans;
// dp[i][j]是i个，每个>=0且递增，最后一个<=j的方案数
ll F(int n,int m){
	if(m<0) return 0;
	return m==0?1:(dp[n][m]-dp[n][m-1]+P)%P;
}
int S[N],T[N];

void Calc(){
	rep(i,1,n-1) {
		int s=0;
		rep(j,1,m-1) {
			s=(s+1ll*F(j,i)*dp[m-j][i-1])%P;
			ans=(ans+1ll*s*F(m-j,n-i)%P*dp[j][n-i-1])%P;
		}
	}
}

int main(){
	dp[0][0]=1;
	rep(i,1,N-1){
		rep(j,0,N-1) {
			if(j) dp[i-1][j]+=dp[i-1][j-1],Mod1(dp[i-1][j]);
			dp[i][j]=dp[i-1][j];
		}
	}
	n=rd(),m=rd();
	Calc(),swap(n,m),Calc();
	rep(i,1,n-1) {
		int s=0;
		rep(j,1,m-1) {
			s=1ll*F(j,i)*dp[m-j][i-1]%P;
			ans=(ans-1ll*s*F(m-j,n-i)%P*dp[j][n-i-1])%P;
		}
	}
	Mod2(ans);
	printf("%d\n",ans*2%P);
}

Posted on Edited on In

CF1499G - Graph Coloring

题目大意

有一个二分图， \(m\) 条边，每条边可以选择为+1或者-1，表示两端的点权值 \(a_u,a_v\pm 1\)

最终的权值总和是 \(\sum |a_u|\)

现在要维护一个动态加边操作

每次加边之后动态维护一个最优的方案最小化权值和，输出其 \(\text{Hash}\) 和


分析

容易发现在最优中方案 \(|a_u|\leq 1\)

且一个点 \(a_u=\pm 1\) 当且仅当 \(deg_u \mod 2=1\)

在依次加入每条边的过程中，一旦出现环，显然环上的边经交错染色之后贡献可以忽略

且奇点总是成对地出现，两个成对的奇点能够确定一条路径

我们只需要在动态加边的过程中，维护对于这样奇点的路径以及环的交替染色即可

注意：

一个点可以被多条路径经过，但是在奇点成对地过程中

我们只认为其中一条的端点是它


那么我们在路径两端记录这条路径，每次加入一条边之后，可能产生多条路径的合并

而在实际实现的过程中，并没有必要把环从路径上删除

假设当前得到路径 \(x\rightarrow y\) ，加入一条边 \(y,z\) 且 \(z\) 在 \(x\rightarrow y\) 上

此时，我们直接认为新的路径端点就是 \((x,z)\) 即可

环的部分依然可以保留在路径上，跟随路径进行交替染色而不影响答案

此时操作被简化为了合并两段交替路径（实际上就是在合并欧拉路径）

可以用带权并查集维护

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

int n1,n2,m,w=1;
int S[N][2],F[N],K[N],D[N];
int Find(int x){
	if(F[x]==x) return F[x];
	int f=F[x]; F[x]=Find(F[x]);
	D[x]^=D[f];
	return F[x];
}

int ans;
void Uni(int x,int y){
	int fx=Find(x),fy=Find(y),d=D[x]^D[y]^1;
	if(fx==fy) return;
	if(d) {
		ans-=S[fx][1],Mod2(ans);
		swap(S[fx][0],S[fx][1]);
		ans+=S[fx][1],Mod1(ans);
		D[fx]=1;
	}
	F[fx]=fy; 
	rep(i,0,1) S[fy][i]+=S[fx][i],Mod1(S[fy][i]);
}
void Add(){
	int x=rd(),y=rd()+n1;
	w*=2,Mod1(w),S[++m][0]=w,F[m]=m;
	if(K[x]<K[y]) swap(x,y);
	if(!K[x]&&!K[y]) K[x]=K[y]=m;
	else if(!K[y]) Uni(K[x],m),K[x]=0,K[y]=m;
	else Uni(K[x],m),Uni(K[y],m),K[x]=K[y]=0;
}

int A[N],C;

int main(){
	n1=rd(),n2=rd();
	rep(_,1,rd()) Add();
	rep(_,1,rd()) {
		if(rd()==1) Add(),printf("%d\n",ans),fflush(stdout);
		else {
			C=0;
			rep(i,1,m) if(Find(i),D[i]==1) A[++C]=i;
			printf("%d\n",C);
			rep(i,1,C) printf("%d ",A[i]);
			puts(""),fflush(stdout);
		}
	}
}

Posted on Edited on In

Codeforces1508D - Tree Calendar

题目大意：

有一棵已知的有根树和一个未知的 \(\text{dfs}\) 序，且做了若干次操作，每次操作是

对于所有的 \((u,fa_u)\and label_{fa_u}<label_{u}\) ，找到最小的二元组 \((label_{fa_u},lable_u)\) ，交换二元组的 \(label\)

给定最终的序列，求复原一个 \(\text{dfs}\) 序并且给出操作次数，或者确定不存在这样的 \(\text{dfs}\) 序

\[ \ \]

模拟这样的过程，容易发现：

1号节点沿着最小 \(\text{dfs}\) 序路径走下去，直到叶子，同时将路径上的点推上来，一共推了 \(dep_{leaf}\) 次

2号节点沿着最小 \(\text{dfs}\) 序路径走下去，直到叶子，同时将路径上的点推上来，一共推了 \(dep_{leaf'}\) 次

....

考虑每个节点都已经推到最底下的情况，则最终所有的节点有两种情况

1.是推下来的节点，则其 \(label\) 恰好为原树上出栈序列的标号

2.剩下的点构成一个新的连通块，按照新的 \(\text{dfs}\) 序的顺序标号

那么考虑找到当前最小的二元组 \((label_{fa_u},label_u)\) ，就知道当前正在推的是哪个元素

考虑先复原这个元素被推下来的过程，复原的过程中注意判定是否当前的元组合法

然后容易通过当前的 \(label\) 确定一开始的 \(\text{dfs}\) 序

具体的，设 \(s_u\) 为 \(u\) 子树中最小的 \(label\) ，按照 \(s_u\) 递增的顺序遍历每个儿子得到的 \(\text{dfs}\) 才可能是合法的 \(\text{dfs}\) 序

原理比较显然，已经被推的叶子按照 \(\text{stack}\) 序遍历，剩下的按照原先的 \(\text{dfs}\) 序遍历，最终取 \(\text{min}\) 然后遍历即合法

然后按照上面的过程，对于得到的 \(\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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=3e5+10;

int n;
int A[N],F[N];
vector <int> G[N];
ll ans;
int X[N],Y[N],Z[N],C1,C2,C3,D[N];
// X 原树 dfs 序
// y 原树 stack 序
// z 删去已经推完的点之后，剩下的点的 dfs 序

int I[N],J[N];
void dfs1(int u){
	I[u]=A[u];
	for(int v:G[u]) D[v]=D[u]+1,dfs1(v),cmin(I[u],I[v]);
}
void dfs2(int u){
	J[X[u]=++C1]=u;
	sort(G[u].begin(),G[u].end(),[&](int x,int y){ return I[x]<I[y]; });
	for(int v:G[u]) dfs2(v);
	Y[u]=++C2;
}
int vis[N];
void dfs3(int u){
	if(vis[u]) return;
	Z[u]=++C3;
	for(int v:G[u]) dfs3(v);
}

int main(){
	n=rd();
	rep(i,1,n) A[i]=rd();
	int p=n+1; A[n+1]=n+1;
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),F[v]=u;
		if(A[u]<A[v] && A[p]>A[u]) p=u;
	}
	int f=1;
	if(p<=n) while(F[p]) {
		int f=F[p];
		// illgal swap
		if(A[f]<A[p]) return puts("NO"),0;
		swap(A[p],A[F[p]]);
		
		// not optimal swap
		if(F[f] && A[F[f]]<A[f]) return puts("NO"),0;
		for(int v:G[f]) if(A[v]>A[f] && A[v]<A[p]) return puts("NO"),0;
		p=F[p],ans++;
	}
	dfs1(1),dfs2(1);
	rep(i,1,n) if(A[i]<A[p]) f&=A[i]==Y[i],vis[i]=1,ans+=D[i];
	dfs3(1);
	rep(i,1,n) if(A[i]>=A[p]) f&=Z[i]+A[p]-1==A[i];
	if(!f) puts("NO");
	else {
		puts("YES");
		printf("%lld\n",ans);
		rep(i,1,n) printf("%d ",X[i]);
		puts("");
	}
}

Posted on Edited on In

Codeforces1508D - Swap Pass

题目大意：

给定 \(n\) 个不共线的点 \(p_i\) ，和一个排列 \(a_i\)

每次交换 \(a_i,a_j\) 的同时，在 \(p_i,p_j\) 之间连一条线段

求一个方案使得最后 \(a_i=i\) ，且连的线之间不交叉

\[ \ \]

问题解决分为两步：

1.环的交换

对于 \(a_i\) 的处理，显然可以将所有点分为若干由 \((i,a_i)\) 边构成的环

每个环上可以随意选择一个点作为初始，设其为 \(o\)

每次交换 \(o,a_o\) 上的数，这样的过程就变成了 \(a_o\) 在环上走一圈

最后连出的边就是 \(o\) 向环上每一个点连接的一圈 "射线"

2.环的合并

考虑Simple的情况，交换两个环上的某一对元素可以将两个环合并在一起

我们希望通过在最终的射线里找"缝隙"连线来合并所有的环

取某一个非孤立的点为原点 \(o\) ，考虑先将所有点放到同一个环里

具体的，将所有的点按原点极角排序，除了最多一个跨过 \(>\pi\) 的位置不能连

剩下的点总可以和极角相邻的点交换，所连的线总在最终射线之间构成三角形

通过若干这样的交换就可以合并到一起

最后再对于钦定的原点进行一次环交换即可

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=3e5+10;

int n,m,O;
int A[N],I[N];
struct Node{
	int x,y;
	Node(){}
	Node(int x,int y):x(x),y(y){}
	Node operator + (const Node _) const { return Node(x+_.x,y+_.y); }
	Node operator - (const Node _) const { return Node(x-_.x,y-_.y); }
	ll operator * (const Node _) const { return 1ll*x*_.x+1ll*y*_.y; }
	db angle() const { return atan2(y,x); }
} P[N];

int C,X[N],Y[N],F[N];
void Swap(int x,int y){ swap(A[x],A[y]),X[++C]=x,Y[C]=y; }
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]); }
void Union(int x,int y){ F[Find(y)]=Find(x); }

int main(){
	n=rd();
	rep(i,1,n) P[i].x=rd(),P[i].y=rd(),A[i]=rd();
	rep(i,1,n) if(A[i]!=i) O=i;
	if(!O) return puts("0"),0;
	rep(i,1,n) if(i!=O) P[i]=P[i]-P[O],I[++m]=i;
	rep(i,1,n) F[i]=i;
	rep(i,1,n) if(F[i]==i) for(int j=A[i];j!=i;j=A[j]) Union(i,j);
	sort(I+1,I+m+1,[&](int x,int y){ return P[x].angle()<P[y].angle(); });
	rep(i,1,m) if(P[I[i]]*P[I[i%m+1]]>=0 && Find(I[i])!=Find(I[i%m+1])) Union(I[i],I[i%m+1]),Swap(I[i],I[i%m+1]);
	while(A[O]!=O) Swap(A[O],O);
	printf("%d\n",C);
	rep(i,1,C) printf("%d %d\n",X[i],Y[i]);
}

Posted on Edited on In

CF1510H - Hard Optimization

题目大意

给定 \(n\) 个区间 \(L_i,R_i\) ，满足其两两之间要么包含要么不交，且所有 \(L_i,R_i\) 互不相同

求为每个区间选定 \(L_i\leq l_i<r_i\leq R_i\) ， \([l_i,r_i]\) 仅在端点相交

使得 \(\sum r_i-l_i\) ，并且输出方案

分析

乍一看， \(L_i,R_i\) 的关系构成森林

哇树形 \(dp\)

哇输出方案！

树形 \(dp\) 还可以输出方案！！！！！！！！！

QQ图片20210506190213.gif

考虑从子树合并 \(dp\) 信息，令 \(dp_{u,i,S}\) 表示

已经确定 \(u\) 的子树内的答案，且向祖先接了 \(i\) 个区间

\(S\) 表示 左边以及右边 是否有 待定未匹配 的区间端点

按照 \(L_i\) 依次合并每个儿子，两个儿子之间可以将未匹配的端点匹配，加入待选集合

待选集合即指向祖先借的个数

每个点在合并结束之后可以匹配同时新建未匹配的左右端点（实际上就是为了给自己定一个方案区间）

关于输出方案

QQ图片20210506185834.jpg

存储每个转移的前驱指针，包括合并以及每个点最后的决策

暴力回溯每个状态，其中待选集合可以用一个栈处理

分类讨论gogogo！！！！

Snipaste_2021-05-06_18-52-05.png
Snipaste_2021-05-06_18-51-49.png

没错三个都是我

QQ图片20210506185755.gif

可能少讨论了一些，但是没有关系！！！！！！！！

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
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
int cmax(int &a,int b){ return a<b?a=b,1:0; }

const int N=2010,P=998244353;

int n;
int L[N],R[N];
int dp[N][N][4],sz[N],len[N],fa[N];
vector <int> E[N];

int X[N],Y[N];
int F[N][4],G[N][4];
int p1[N][N][4],p2[N][N][4];
// p1 存储合并子树的前驱
// p2 存储每个点最后决策时的变化
void dfs(int u) {
	sort(E[u].begin(),E[u].end(),[&](int x,int y){ return L[x]<L[y]; });
    // 叶子暴力赋初值
	if(!E[u].size()) {
		sz[u]=0;
		dp[u][0][0]=R[u]-L[u];
		dp[u][0][1]=R[u];
		dp[u][0][2]=-L[u];
		dp[u][0][3]=0;
		return;
	}
	sz[u]=0;
	for(int v:E[u]) dfs(v);
	memset(F,-63,sizeof F);
	for(int v:E[u]) {
		if(v==E[u][0]) {
			rep(i,0,sz[v]) rep(j,0,3) F[i][j]=dp[v][i][j],p1[v][i][j]=i*16+j;
			sz[u]+=sz[v];
			continue;
		}
		rep(i,0,sz[u]) rep(j,0,3) G[i][j]=F[i][j],F[i][j]=-1e9;
		rep(i,sz[u]+1,sz[u]+sz[v]) rep(j,0,3) F[i][j]=-1e9;
		rep(i,0,sz[u]) rep(a,0,3) rep(j,0,sz[v]) rep(b,0,3) if((a>>1)==(b&1)) {
			if(cmax(F[i+j+(b&1)][(a&1)|(b&2)],G[i][a]+dp[v][j][b])) {
				p1[v][i+j+(b&1)][(a&1)|(b&2)]=j*16+a*4+b;
			}
		}
		sz[u]+=sz[v]+1;
	}
	rep(i,0,sz[u]) rep(j,0,3) {
		if(i && cmax(dp[u][i-1][j],F[i][j])) p2[u][i-1][j]=1;
		if(j&1 && cmax(dp[u][i][j-1],F[i][j]-L[u])) p2[u][i][j-1]=2;
		if(j&2 && cmax(dp[u][i][j-2],F[i][j]+R[u])) p2[u][i][j-2]=3;
		if(j&1 && cmax(dp[u][i][j],F[i][j])) p2[u][i][j]=4;
		if(j&2 && cmax(dp[u][i][j],F[i][j])) p2[u][i][j]=5;
	}
}

stack <Pii> stk;
Pii dfs2(int u,int a,int b) {
	if(!E[u].size()) {
		X[u]=L[u],Y[u]=R[u];
		return mp(L[u],R[u]);
	}
	int typ=p2[u][a][b];
	switch(typ) {
		case 0: { break; }
		case 1: { a+=1; break; }
		case 2: { b+=1; break; }
		case 3: { b+=2; break; }
		case 4: { break; }
		case 5: { break; }
	}
	reverse(E[u].begin(),E[u].end());
	int r=0,lst=-1;
	for(int v:E[u]) {
		int t=p1[v][a][b];
		Pii p=dfs2(v,t>>4,t&3);
		if(t&2) {
			if(lst==-1) r=p.second;
			else stk.push(mp(p.second,lst)),lst=-1;
		}
		if(t&1) lst=p.first;
		a-=(t>>4)+(t&1),b=(t>>2)&3;
	}
	switch(typ) {
		case 0:{ break; }
		case 1:{ X[u]=stk.top().first,Y[u]=stk.top().second,stk.pop(); break; }
		case 2:{ X[u]=L[u],Y[u]=lst; break; }
		case 3:{ X[u]=r,Y[u]=R[u]; break; }
		case 4:{ X[u]=L[u],Y[u]=lst,lst=L[u]; break; }
		case 5:{ X[u]=r,Y[u]=R[u],r=R[u]; break; }
	}
	return mp(lst,r);
}

int main(){
	memset(dp,-63,sizeof dp),scanf("%d",&n);
	rep(i,1,n) scanf("%d%d",L+i,R+i),len[i]=R[i]-L[i];
	rep(i,1,n) {
		rep(j,1,n) if(L[j]<L[i] && R[i]<R[j] && (!fa[i] || len[j]<len[fa[i]])) fa[i]=j;
		if(fa[i]) E[fa[i]].pb(i);
	}
	int ans=0;
	rep(i,1,n) if(!fa[i]) {
		dfs(i);
		ans+=dp[i][0][0],dfs2(i,0,0);
	}
	printf("%d\n",ans);
	rep(i,1,n) printf("%d %d\n",X[i],Y[i]);
}

Posted on Edited on In

CF1514E - Baby Ehab's Hyper Apartment

题目大意

交互题，给定 \(n\) 元竞赛图，方向未知，通过两种操作

1.查询 \((a,b)\) 方向 ，上限 \(9n\) 次

2.查询 \(a\) 到达一个集合 \(S\) 是否存在正向边，上限 \(2n\) 次

判定所有点之间能否互相到达



分析

能否互相到达是一个强连通问题，因此需要求出分量以及分量之间的拓扑关系

由于是竞赛图，最终的每个分量一定可以排成一排，只能由前面向后面连边

由于 \(9\approx \log n\) ，我们需要一个带 \(\log\) 的算法

考虑将分量内部相对顺序随意，其他关系按照拓扑序确定

通过一个 伪排序 得到一个初始序列

然后只需要合并得到强连通分量的区间

具体的，按照序列顺序，顺次向图上加入每个点 \(i\)

对于每个点 \(i\) 和当前的其所在分量 \(A\) ，左边的分量 \(B\) ，以及左边所有点的集合 \(S\)

判断 \(A,B\) 是否合并，即判断 \(i\) 是否有到达 \(S\) 的边

最多有 \(n-1\) 次合并，以及 \(n-1\) 次合并失败

tips: 由于标准库实现的原因，伪排序不能用std::sort，但是可以用std::stable_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

const int N=2e5+10;

int n;

int Que(int a,int b){
	printf("1 %d %d\n",a,b),fflush(stdout);
	return rd();
}
int P[N];
int L[N],F[N];

int main(){
	rep(_,1,rd()) {
		n=rd();
		rep(i,0,n-1) F[i]=P[i]=i;
		stable_sort(P,P+n,Que);
		rep(i,0,n-1) {
			L[i]=i;
			while(L[i]) {
				printf("2 %d %d ",P[i],L[i]);
				rep(j,0,L[i]-1) printf("%d ",P[j]);
				puts(""),fflush(stdout);
				if(rd()) L[i]=L[L[i]-1];
				else break;
			}
			rep(j,L[i],i) F[P[j]]=i;
		}
		puts("3");
		rep(i,0,n-1) {
			rep(j,0,n-1) putchar((F[i]<=F[j])+'0');
			puts("");
		}
		fflush(stdout);
		if(rd()==-1) break;
	}
}

Posted on Edited on In

CF1515G - Phoenix and Odometers

题目大意

给定一张带权有向图，每次查询 \(v,s,t\) 表示从 \(v\) 出发并且回到 \(v\) ，可以经过重边

判断是否存在经过路径总长 \(l\) 满足 \(l+s\equiv 0 \pmod t\)

\[ \ \]

分析

显然 \(v\) 只能在其自己的强连通分量里走，并且分量内部的任意一个环都是可达的

由于是模意义下，所以环的贡献可以抵消，环之间可以无限叠加

根据裴蜀定理，能够生成的数就是是 \(\gcd(len_i)\) 的倍数

只需预处理强连通分量内部的环，判断 \(\gcd(len_i,t)|\gcd(s,t)\) 即可

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

const int N=2e5+10;

int n,m;
struct Edge{
	int to,nxt,w;
}e[N];
int head[N],ecnt;
void AddEdge(int u,int v,int w){
	e[++ecnt]=(Edge){v,head[u],w};
	head[u]=ecnt;
}

ll G[N],S[N];
ll gcd(ll a,ll b){ return b==0?a:gcd(b,a%b); }
int t[N],low[N],dfn,stk[N],ins[N],top,id[N],scc;
ll dis[N];

void dfs(int u){
	ins[stk[++top]=u]=1,low[u]=t[u]=++dfn;
	for(int i=head[u];i;i=e[i].nxt) {
		int v=e[i].to;
		if(!t[v]) {
			dis[v]=dis[u]+e[i].w;
			dfs(v),cmin(low[u],low[v]);
		} else if(ins[v]) {	
            // 不管是横边还是返祖边，长度都是dis[u]-dis[v]!!!
			cmin(low[u],t[v]);
			G[u]=gcd(G[u],dis[u]-dis[v]+e[i].w);
		}
	}
	if(low[u]==t[u]) {
		++scc;
		for(int v=-1;v!=u;) {
			ins[v=stk[top--]]=0;
			id[v]=scc,S[scc]=gcd(S[scc],G[v]);
		}
	}
}

int main(){
	n=rd(),m=rd();
	rep(i,1,m) {
		int u=rd(),v=rd(),w=rd();
		AddEdge(u,v,w);
	}
	rep(i,1,n) if(!t[i]) dfs(i);
	rep(_,1,rd()) {
		int u=rd(),s=rd(),t=rd();
		s=gcd(s,t),t=gcd(t,S[id[u]]);
		puts(s%t==0?"YES":"NO");
	}
}

Posted on Edited on In

CF1517F - Reunion

题目大意

对于一棵树，树上每个节点颜色在在黑白之间均等随机

定义r: 从某一个点 \(u\) 开始， \(r\) 为使得距离 \(u\) 在 \(r\) 以内的点均为均为黑点的最大距离

求 \(r\) 的期望，全黑和全白的情况 \(r\) 特殊处理

模型转化

当然是期望转概率，枚举 \(d\) ，计算 \(\max\{r\}\ge d\) 的概率

然而 \(\exists r\ge d\) 并不好算，于是算 \(\nexists r\ge d\) 的概率

看成是用白点去覆盖整棵树，每个白点可以覆盖距离 \(d\) 以内的所有点

dp

令 \(dp_{u,i}\) 表示当前 \(u\) 的子树内，

\(i\ge 0\) ，能够向上额外延伸 \(i\) 的距离

\(i<0\) ，还需要一个距离为 \(-1-i\) 的白点伸进去覆盖它

合并可能存在的问题？

如果 \(u\) 子树内即有点伸出去又有点没有被覆盖？

那么记录没有被覆盖的点

因为在最优情况里，这个点一定要被另一个节点覆盖

而那个去覆盖它的点，显然比当前节点延伸出去部分覆盖的范围更大

因此 \(u\) 延伸出去的部分没有用

\[\ \]

第二维出现的个数为 \(O(dep)\) ，借用树形背包的复杂度分析，因此单次复杂度上限为 \(O(n^2)\) ，实际完全不满

总复杂度为 \(O(n^3)\)

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=310,P=998244353;
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 n,d,m;
vector <int> G[N];
int dp[N][N*2],g[N*2],D[N];
vector <int> tmp;
void dfs(int u,int f) {
	// n+1 为基准偏移
	rep(i,0,m) dp[u][i]=0;
	dp[u][n+d+2]=1,dp[u][n]=1;
	for(int v:G[u]) if(v!=f) {
		dfs(v,u);
		cmax(D[u],D[v]+1);
		rep(i,0,m) g[i]=dp[u][i],dp[u][i]=0;
		tmp.clear();
		rep(i,0,m) if(dp[v][i]) tmp.pb(i);
		rep(i,0,m) if(g[i]) {
			for(int j:tmp) {
				if(max(j-n-2,i-n-2)>=max(n-i,n-j)) dp[u][max(i,j)]=(dp[u][max(i,j)]+1ll*g[i]*dp[v][j])%P;
				else dp[u][min(i,j)]=(dp[u][min(i,j)]+1ll*g[i]*dp[v][j])%P;
			}
		}
	}
	rep(i,0,m) g[i]=dp[u][i],dp[u][i]=0;
	rep(i,1,n) dp[u][i-1]=g[i];
	rep(i,n+2,m) dp[u][i-1]=g[i];
	dp[u][n+1]+=g[n+1],Mod1(dp[u][n+1]);
}

int main(){
	n=rd(),m=n*2+2;
	rep(i,2,n) {
		int u=rd(),v=rd();
		G[u].pb(v),G[v].pb(u);
	}
	int all=qpow(2,n),ans=0;
    // d枚举到n-1，正好抵消了n 和 -1的贡献
	for(d=1;d<n;++d) {
		dfs(1,0);
		int s=all;
		rep(i,n+1,m) s-=dp[1][i],Mod2(s);
		ans=(ans+s)%P;
	}
	ans=ans*qpow(all)%P;
	printf("%d\n",ans);
}
0%