Reincarnation

正因为梦易碎，才格外美好。

ZROI - 20连测Day7

发表于 分类于 ，
本文字数： 14k 阅读时长 ≈ 13 分钟

最不良心的一集。

比赛链接：http://zhengruioi.com/contest/1473

A. 仙客来

题目简介

给定 个有序正整数以及 个有序的运算符（只有 ），现在你可以在任意位置加入合法括号，使得最后运算结果最大。

数据范围：

首先肯定的是在 号后加入左括号显然是愚蠢的。

我们考虑所有右括号都加在整个算式的末尾，那么加入一个括号就会使后面的所有运算符全部取反，但是这个时候如果有 号被取反可能会使答案变劣，所以我们观察性质。

对于一个 号，我们将其后方一个连续段括起来后，会形成一个减数，减数越小，总和越大。而这个减数最终还是会形成一个被减数和减数，我们需要这个被减数越小，且减数越大，而这个被减数，实际上就是 号之后的一个 号连续段连接的所有数的和，而被减数就是之后括号内的所有和，你发现一定存在一种添加括号的方案，使得减数内所有的数都对减数产生正贡献。也就是把之后的所有 号全部括起来即可。

所以我们预处理一个位置的后缀和，后缀最大 连续段以及其位置。然后我们枚举 号，并对之后贡献取 即可。

时间复杂度 。

破案了，正解是 ，观察性质有：

所以花花说有个性质是答案中括号嵌套不超过 层，所以你设计状态 表示当前前 个位置中括号的状态，递推转移即可。

AC 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
// ----- Eternally question-----
// Problem: A. 【noip赛前20天冲刺集训 day7】仙客来
// Contest: ZROI - 23noip赛前20天冲刺 day7
// URL: http://zhengruioi.com/contest/1473/problem/2756
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-18 08:30:20
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N,a[MAXN];
char Op[MAXN][2];
ll suf[MAXN],sufo[MAXN],sufpos[MAXN];
inline ll getSum(int l,int r){ return l>r?0ll:suf[l]-suf[r+1]; }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<N;++i) read(a[i]),scanf("%s",Op[i+1]+1);
	read(a[N]);
	suf[N]=a[N],sufo[N]=0,sufpos[N]=N;
	for(int i=N-1;i;--i)
	{
		if(Op[i+1][1]=='+') sufpos[i]=sufpos[i+1],sufo[i]=sufo[i+1]+a[i+1];
		else sufpos[i]=i,sufo[i]=0;
		suf[i]=suf[i+1]+a[i];
	}
	ll ans=-1,sum=a[1];
	for(int i=2;i<=N;++i)
	{
		if(Op[i][1]=='-')
		{
			checkMax(ans,sum-((a[i]+sufo[i])-getSum(sufpos[i]+1,N)));
			sum-=a[i];
		}
		else sum+=a[i];
	}
	write(ans);
	return 0;
}
/*

*/

B. 白兰花

题目简介

给定一个有 个结点 条边的无向图，边带权。定义 的最短路为其经过的边权和减去极差（边权最大值减边权最小值），求从 开始的单源全局最短路。或报告无法到达。

数据范围：

考虑实际意义，最小边权被算了两边，而最大边权免费了。

我们先不计较这个最值的限制，直接改为可以选择一条边不计入贡献，但是需要选择另外一条边计算两次。然后你发现基于贪心思路，不计入贡献的边一定最大，二倍权重的边一定最小。

所以考虑分层图，第 层到第 层的边不计入贡献，第 层到第 层的边边权翻倍。

但是注意这两者顺序不定，所以第 层应该有 张图，一张是免费的图，一张是翻倍的图，所以是 倍点数。

时间复杂度 。

AC 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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
// ----- Eternally question-----
// Problem: B. 【noip赛前20天冲刺集训 day7】白兰花
// Contest: ZROI - 23noip赛前20天冲刺 day7
// URL: http://zhengruioi.com/contest/1473/problem/2757
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-18 10:40:23
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10,MAXV=1e6+10,MAXE=4e6+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll LIMIT=1e18;
namespace Eternity
{
	typedef long long ll;
	const int MAXN=2e5+10;
	const int Inf=0x3f3f3f3f;
	const ll LIMIT=1e18;
	int N,M;
	struct G
	{ int next,to,val; }Edge[MAXN<<1];
	int Head[MAXN],Total;
	inline void addEdge(int u,int v,int w)
	{
		Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
		Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
	}
	namespace Brute
	{
		bool Vis[MAXN];
		ll Dist[MAXN];
		struct Node
		{
			int pos,mx,mn;
			ll val;
			Node(int _p=0,ll _x=0,ll _n=0,ll _v=0):pos(_p),mx(_x),mn(_n),val(_v){}
		};
		inline void Bfs()
		{
			std::queue<Node>Q;
			Q.push(Node(1,-1,Inf,0));
			while(!Q.empty())
			{
				auto u=Q.front();Q.pop();
				for(int e=Head[u.pos];e;e=Edge[e].next)
				{
					int v=Edge[e].to,vl=Edge[e].val;
					if(checkMin(Dist[v],-std::max(u.mx,vl)+std::min(u.mn,vl)+u.val+vl))
						Q.push(Node(v,std::max(u.mx,vl),std::min(u.mn,vl),u.val+vl));
				}
			}
		}
		inline bool solveBrute()
		{
			for(int i=2;i<=N;++i) Dist[i]=1e18;
			Bfs();
			for(int i=2;i<=N;++i) write(Dist[i],' ');
			return 0;
		}
	};
	namespace Tree
	{
		bool Vis[MAXN];
		int Max[MAXN],Min[MAXN],Fa[MAXN];
		ll Dist[MAXN];
		inline bool checkTree()
		{
			std::queue<int>Q;
			Q.push(1);
			Max[1]=-Inf,Min[1]=Inf;
			while(!Q.empty())
			{
				int u=Q.front();Q.pop();
				Vis[u]=1;
				for(int e=Head[u],v;e;e=Edge[e].next)
				{
					if((v=Edge[e].to)==Fa[u]) continue;
					if(Vis[v]) return 0;
					Max[v]=std::max(Max[u],Edge[e].val),
					Min[v]=std::min(Min[u],Edge[e].val),
					Dist[v]=Dist[u]+Edge[e].val;
					Q.push(v),Fa[v]=u;
				}
			}
			return 1;
		}
		inline bool solveTree()
		{
			for(int i=2;i<=N;++i) write(Dist[i]+Min[i]-Max[i],' ');
			return 0;
		}
	}
	namespace Equal
	{
		inline bool checkEqual()
		{
			for(int i=2;i<=Total;++i) if(Edge[i].val!=Edge[i-1].val) return 0;
			return 1;
		}
		ll Dist[MAXN];
		bool Vis[MAXN];
		inline bool solveEqual()
		{
			std::queue<int>Q;
			Q.push(1);
			for(int i=2;i<=N;++i) Dist[i]=LIMIT;
			while(!Q.empty())
			{
				int u=Q.front();Q.pop();
				if(Vis[u]) continue;
				Vis[u]=1;
				for(int e=Head[u],v;e;e=Edge[e].next)
				{
					v=Edge[e].to;
					checkMin(Dist[v],Dist[u]+Edge[e].val);
					Q.push(v);
				}
			}
			for(int i=2;i<=N;++i) write(Dist[i],' ');
			return 0;
		}
	};
	inline bool main(int n,int m)
	{
		N=n,M=m;
		for(int i=1,u,v,w;i<=m;++i) read(u,v,w),addEdge(u,v,w);
		if(Tree::checkTree()) return Tree::solveTree();
		if(Equal::checkEqual()) return Equal::solveEqual();
		if(N<=10&&M<=10) return Brute::solveBrute();
		return 0;
	}
}
int N,M;
struct G
{ int next,to,val; }Edge[MAXE<<1];
int Head[MAXV],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
struct Node
{
	int pos;ll val;
	Node(int _p=0,ll _v=0):pos(_p),val(_v){}
	const bool operator<(const Node &x) const { return val>x.val; }
};
ll Dist[MAXV];
bool Vis[MAXV];
inline void Dijkstra()
{
	std::priority_queue<Node>Pq;
	Pq.push(Node(1,0));
	std::memset(Dist,0x3f,sizeof(Dist)),
	std::memset(Vis,0,sizeof(Vis));
	Dist[1]=0;
	while(!Pq.empty())
	{
		int x=Pq.top().pos;Pq.pop();
		if(Vis[x]) continue;
		Vis[x]=1;
		for(int e=Head[x],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(checkMin(Dist[v],Dist[x]+Edge[e].val)) Pq.push(Node(v,Dist[v]));
		}
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	// return Eternity::main(N,M);
	for(int i=1,u,v,w;i<=M;++i)
	{
		read(u,v,w);
		addEdge(u,v,w),addEdge(u+N,v+N,w),addEdge(u+N*2,v+N*2,w),addEdge(u+N*3,v+N*3,w);
		addEdge(v,u,w),addEdge(v+N,u+N,w),addEdge(v+N*2,u+N*2,w),addEdge(v+N*3,u+N*3,w);
		addEdge(u,v+N,0),addEdge(v,u+N,0);
		addEdge(u,v+N*2,2*w),addEdge(v,u+N*2,2*w);
		addEdge(u+N,v+N*3,2*w),addEdge(v+N,u+N*3,2*w);
		addEdge(u+N*2,v+N*3,0),addEdge(v+N*2,u+N*3,0);
	}
	Dijkstra();
	for(int i=2;i<=N;++i)
	{
		ll ans=std::min(Dist[i],Dist[i+N*3]);
		write(ans==INF?LIMIT:ans,' ');
	}
	return 0;
}
/*

*/

C. 月见草

题目简介

将 放入若干个集合中，要求对于 满足 。求本质不同的分组方案数（集合无序，集合内部无序）。对 取模。

数据范围：

你发现每个人的限制不一样就很难受，所以我们将 开入桶，用 表示限制为 的人数，然后从大到小考虑。

我们记录 表示当前考虑了 的所有人，还有 个没有被分组。

然后我们枚举分了 个大小为 的组，转移为：

除以 因为集合无序，而后面的连乘表示我们每次拿出 个并选择 个进入一个组，所以这个答案是一个前缀形式。

所以时间复杂度 ，但是你发现枚举 是一个调和级数形式，所以实现是 。

AC 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
// ----- Eternally question-----
// Problem: C. 【noip赛前20天冲刺集训 day7】月见草
// Contest: ZROI - 23noip赛前20天冲刺 day7
// URL: http://zhengruioi.com/contest/1473/problem/2758
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-18 11:02:39
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=3e3+10;
const int Mod=998244353;
template<class T1,class T2>
inline void add(T1 &x,T2 y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N,a,Dp[MAXN][MAXN];
int C[MAXN][MAXN],Cnt[MAXN],Inv[MAXN];
inline void init(int n)
{
	for(int i=0;i<=n;++i)
		for(int j=C[i][0]=1;j<=i;++j)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%Mod;
	Inv[1]=1;
	for(int i=2;i<=n;++i) Inv[i]=(ll)Inv[Mod%i]*(Mod-Mod/i)%Mod;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1,x;i<=N;++i) read(x),++Cnt[x];
	init(MAXN-10);
	Dp[N][0]=1;
	for(int i=N,sum=0;i;sum+=Cnt[i],--i)
		for(int j=0;j<=sum;++j) for(int k=0,delta=1;k*i<=j+Cnt[i];++k)
		{
			add(Dp[i-1][j+Cnt[i]-k*i],(ll)Dp[i][j]*delta%Mod);
			delta=(ll)delta*C[j+Cnt[i]-(k+1)*i+i][i]%Mod*Inv[k+1]%Mod;
		}
	// for(int i=0;i<=N;++i,puts(""))
		// for(int j=0;j<=N;++j) write(Dp[i][j],' ');
	write(Dp[0][0]);
	return 0;
}
/*

*/

首先按照 由大至小排序，那么所有限制都在当前的枚举位。我们对于每一种划分方法，都在最右侧时进行计数。

考虑部分分 。

设计状态 表示当前考虑 ，大小为 的集合有 个。有转移：

在 独立的时候特判即可。

滚动数组后发现这是一个多项式卷积，所以可以直接用 优化。

时间复杂度 ，但是跑不过另外一种做法。

D. 茉莉花

题目简介

有一个有 层，每层有 个点的分层图，第 层的点仅会向 层的点连有向边，定义 表示从第 层出发，到第 层结束的路径在点和边都不交的情况下最多的路径数。

求 。

数据范围：

时空限制：

暴力网络流有 ，但是输出 有 。

暴力网络流是好做的，但是要跑 次 。我们直接计算 。

我们首先拆点，然后连接原图上的边，源点连第 层的点，流量为 ，然后 的点连汇点，流量为 。时间复杂度懒得算，勉强跑过 。

考虑转化为最小割模型，直接上 。

反过来统一计算 ，设 表示当前到第 层，点能够被到达的状态为 ，点集不重是边集不重的充分条件，所以我们只考虑点集。转移直接枚举 的子集，时间复杂度 。

然后考虑优化：

  • 每次割一个点，然后直接集合按照由大到小依次转移，单次优化到 ；
  • 观察到 关于起点单调，所以一定有 。所以直接 （ 套 ），令 表示满足 的 。状态数变为 。

所以最后实现为 。

相关文章