Reincarnation

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

ZROI - 20连测Day8

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

最提瓦特的一集。

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

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
81
// ----- Eternally question-----
// Problem: A. 【noip赛前20天冲刺集训 day8】串
// Contest: ZROI - 23noip赛前20天冲刺 day8
// URL: http://zhengruioi.com/contest/1477/problem/2705
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-19 08:42:17
// ----- 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=5e5+10,MAXS=1e6+10,MAXC=30;
char S[MAXN],T[MAXN];
char Str[MAXS];
int Nxt[MAXS][MAXC],Pos[MAXC];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s%s",S+1,T+1);
	int Len=std::strlen(S+1);
	for(int i=1;i<=Len;++i) Str[i]=Str[Len+i]=S[i];
	for(int c=1;c<=26;++c) Pos[c]=Len*2+1;
	for(int i=Len*2;i;--i)
	{
		for(int c=1;c<=26;++c) Nxt[i][c]=Pos[c];
		Pos[Str[i]-'a'+1]=i;
	}
	for(int c=1;c<=26;++c) Nxt[0][c]=Pos[c];
	for(int i=1;i<=Len;++i)
		for(int c=1;c<=26;++c)
			Nxt[i][c]-=Nxt[i][c]>Len?Len:0;//write(Nxt[i][c],' ');
	int pos=1,pnt=0,tar=std::strlen(T+1),ans=1;
	while(pos<=tar)
	{
		int nxt=Nxt[pnt][T[pos]-'a'+1];
		if(nxt>Len) return puts("-1"),0;
		if(nxt<=pnt) ++ans;
		// write(pnt,' ',nxt,' ',pos,'\n');
		pnt=nxt,++pos;
	}
	write(ans);
	return 0;
}
/*

*/

B. 最大权独立集问题

题目简介

原题链接：https://www.luogu.com.cn/problem/P8424

数轴上有 个权重为 的点，每次从最左端或者最右端删除一个点直到删空，你需要在数轴上找到一段实数域 ，使得存在一种删数方案使得任意时刻剩下的所有 的平均值都在 内，求出最短的 的长度，可以是实数。

数据范围：

首先答案区间 一定包含点 ，否则无解（当然这道题不可能无解）。

我们记录 ，那么我们的贪心思路就是希望在操作期间我们的重心位置从 向左右偏移的量尽可能少。

考虑当前进行了若干次操作剩下的区间是 （下标区间而不是值域区间）。然后我们考虑重心 的最靠近 的区间 和重心 的最靠近 区间 ，这时一定有性质 ，否则一定存在更优。

我们当前操作的最优情况一定是上述二者之一，最终答案为 。

所以我们双指针扫描 ，如果当前平均权重大于 ，则 减 （相当于 ），然后我们记录所有合法答案，首先按照 排序，然后对 取后缀最大值。

时间复杂度 ，排序的 。

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
// ----- Eternally question-----
// Problem: B. 【noip赛前20天冲刺集训 day8】最大权独立集问题
// Contest: ZROI - 23noip赛前20天冲刺 day8
// URL: http://zhengruioi.com/contest/1477/problem/2706
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-19 19:40:07
// ----- 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; }
using Pir=std::pair<double,double>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=2e5+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,a[MAXN];
ll pre[MAXN];
double ans=INF,Mx;
Pir res[MAXN];
inline double calc(int l,int r){ return 1.0*(pre[r]-pre[l-1])/(r-l+1); }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(a[i]),pre[i]=pre[i-1]+a[i];
	double k=calc(1,N);
	for(int i=N-1,l=2,r=N;i;--i,++l)
	{
		if(calc(l,r)>=k) --l,--r;
		res[i]=Mkr(k-calc(l,r),calc(l+1,r+1)-k);
	}
	std::sort(res+1,res+N);
	for(int i=N-1;i;--i) checkMin(ans,res[i].fir+Mx),checkMax(Mx,res[i].sec);
	printf("%.10lf",ans);
	return 0;
}
/*

*/

C. 喵了个喵

题目简介

原题链接：https://www.luogu.com.cn/problem/P9291

给定一种操作 表示将 变为 。

现在给定一个排列 ，要求对其做若干次操作使得最后从大到小排序。其中 表示操作次数。

数据范围：

比较牛的乱搞题。

首先考虑朴素的做法，如果 ，那么 操作等价于交换相邻的数，所以我们可以选择直接冒泡排序，就是这道题的暴力分。

然后考虑 的实质，就是没有实质，但是我们每一次都可以把 后移到至少 的位置。

所以我们从后往前分别考虑 ，然后类似倍增的思想将 一步一步移到 的位置，操作复杂度 ，时间复杂度 ，有一半左右的分。

当然，基于乱搞之神的引导，你可以花费 左右的次数随机打乱序列，以避免出题人真的给你卡满了 过不了第二档分。

然后是一个比较牛的优化，我们考虑对排列取逆，记 表示 的位置，取逆意味着 ，也就是考虑每个位置，那么相应的，操作以及操作顺序都需要交换（没注意到这一点调了半天）。

然后根据观察，这样做可以做到 左右的操作复杂度。

至于证明，颜桉在题解中写道：

考虑把排列取个逆，然后把操作也取个逆，然后改为从大到小枚举 。求逆之后的操作的优势在哪里呢？注意到此时我们操作的过程是首先倍增把 移到 上，然后用一次操作挪到 。虽然挪一个数使用的操作次数同为 ，但是常数大大减小了！一个很显然的例子是，当 本身已经位于 上时，我们仅需一次操作就能还原，这是上面的每次折半的操作所无法达成的。

假设当前的数要挪到 ，分析之后可以发现，若现在的位置 满足 ，则至多需要进行 次操作，所以随机化之后还原一个位置的期望步数为 ，从表现上来看，随机化之后有大约两倍的常数。

什么？证明没搞懂？我也没搞懂。

操作复杂度 ，时间复杂度 。

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
// ----- Eternally question-----
// Problem: C. 【noip赛前20天冲刺集训 day8】喵了个喵
// Contest: ZROI - 23noip赛前20天冲刺 day8
// URL: http://zhengruioi.com/contest/1477/problem/2707
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-19 10:07:16
// ----- 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; }
using Pir=std::pair<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=3e3+10;
int N,a[MAXN],tmp[MAXN],Pos[MAXN];
std::vector<Pir>vec;
std::mt19937 rnd(time(NULL));
inline void action(int l,int r)
{
	if(l>=r) return ;
	vec.push_back(Mkr(l,r));
	int cnt=l-1;
	for(int i=l+1;i<=r;i+=2) tmp[i]=a[++cnt];
	for(int i=l;i<=r;i+=2) tmp[i]=a[++cnt];
	for(int i=l;i<=r;++i) a[i]=tmp[i];
	for(int i=l;i<=r;++i) Pos[a[i]]=i;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(Pos[i]),a[Pos[i]]=i;
	for(int i=1;i<=100;++i)
	{
		int l=rnd()%N+1,r=rnd()%N+1;
		if(l>r) std::swap(l,r);
		action(l,r);
	}
	for(int i=N;i;--i)
		while(Pos[i]!=i)
		{
			if(Pos[i]*2>=i) action(2*Pos[i]-i+1,i);
			else action(1,2*Pos[i]);
		}
	write(vec.size(),'\n');
	std::reverse(vec.begin(),vec.end());
	for(auto x:vec) write(x.fir,' ',x.sec,'\n');
	return 0;
}
/*

*/

D. 过河卒

题目简介

原题链接：https://www.luogu.com.cn/problem/P7353

猫抓老鼠，这个游戏会在一张有 个点 条边的无向图中上演 次：

每一回合会依次进行以下操作：

  • 老鼠可以移动到任何不经过猫所在结点的结点上（包括自身）；
  • 猫会向于自己相邻的任意结点移动（包括自身）。

如果某一回合结束猫与老鼠位于同一结点，则猫获胜，否则如果直到 回合猫都没有获胜，则老鼠获胜。

每次给定猫和老鼠的初始结点 ，判断谁会获胜。

数据范围：

这个奇妙的设定，所以一定和点双连通分量有关，首先缩点。

然后考虑汤姆胜利的条件，那就是他能够一步一步将杰瑞逼进一个死角，所以如果这是一棵树那就好做的扣了。

所以我们建圆方树！

将 作为圆方树的根，设 为换根后的树上位于 的 子树上，则 只能在 内活动。

设当前汤姆在 ，他将移动至 满足：

  • 为割点或者杰瑞在 点；
  • 在圆方树中 的子树中；
  • 原图 有边。

所以 一定满足在 所在某个点双连通分量除了 之外的点中且距离为 。因为杰瑞先手，可以逃到一些很远很远的点上，所以如果 ，满足按照上述行动后存在最终 ，则汤姆获胜。

预处理 表示以 为根时内外子树是否满足上述条件，可以做到 分讨查询。

如果 开始不是割点，汤姆依然有获胜的可能，到达点 满足以 为根时满足上述条件。此时 也类似于割点。

所以对于讨论，我们判断是否存在结点 满足 ，如果有，那么就存在 ，此时汤姆全胜。

时间复杂度 。

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
// ----- Eternally question-----
// Problem: D. 【noip赛前20天冲刺集训 day8】过河卒
// Contest: ZROI - 23noip赛前20天冲刺 day8
// URL: http://zhengruioi.com/contest/1477/problem/2708
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-19 10:33: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=2e5+10,MAXM=5e5+10,MAXS=20;
int N,M,Q;
struct G
{ int next,to; }Edge[MAXN<<1],NewEdge[MAXN<<1];
int Head[MAXN],Total,NewHead[MAXN],NewTotal;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
inline void addNewEdge(int u,int v)
{
	NewEdge[++NewTotal]=(G){NewHead[u],v};NewHead[u]=NewTotal;
	NewEdge[++NewTotal]=(G){NewHead[v],u};NewHead[v]=NewTotal;
}
int Dfn[MAXN],Low[MAXN],Cnt,Bcc_cnt;
bool Ins[MAXN];
std::stack<int>Stk;
std::set<int>Set1,Set2[MAXN];
void Tarjan(int x,int last,int n,int &id,int &bcc_cnt)
{
	int son_cnt=0;
	Dfn[x]=Low[x]=++id,Ins[x]=1,Stk.push(x);
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if(!Ins[(v=Edge[e].to)])
		{
			++son_cnt;
			Tarjan(v,x,n,id,bcc_cnt);
			checkMin(Low[x],Low[v]);
			if(Low[v]>=Dfn[x])
			{
				int pos=++bcc_cnt+N,cur;
				addNewEdge(pos,x);
				do
				{
					cur=Stk.top();Stk.pop();
					addNewEdge(pos,cur);
				}while(cur!=v);
			}
		}
		else checkMin(Low[x],Dfn[v]);
	}
	if(!last&&!son_cnt)
	{
		int pos=++bcc_cnt+N;
		addNewEdge(pos,x);
	}
}
int Dep[MAXN],In[MAXN],Out[MAXN],Idx;
int Dp1[MAXN],Dp2[MAXN],Fa[MAXN][MAXS];
void dfsGraph(int x,int last,int n,int &id)
{
	Dep[x]=Dep[last]+1;
	int t=std::log2(Dep[x]);
	In[x]=++id,Fa[x][0]=last;
	for(int i=1;i<=t;++i) Fa[x][i]=Fa[Fa[x][i-1]][i-1];
	Dp1[x]=1;
	for(int e=NewHead[x],v;e;e=NewEdge[e].next)
	{
		v=NewEdge[e].to;
		if(v==last) continue;
		dfsGraph(v,x,n,id);
		Dp1[x]&=Dp1[v];
		if(x>n) Dp1[x]&=Set2[last].count(v);
	}
	Out[x]=id;
}
void dfsCalc(int x,int n)
{
	int cnt1=0;
	Set1.clear();
	if(Fa[x][0]!=0) Set1.insert(Fa[x][0]);
	for(int e=NewHead[x],v;e;e=NewEdge[e].next)
	{
		v=NewEdge[e].to;
		if(v==Fa[x][0]) continue;
		Set1.insert(v);
		if(!Dp1[v]) ++cnt1;
	}
	int siz=Set1.size();
	for(int e=NewHead[x],v;e;e=NewEdge[e].next)
	{
		v=NewEdge[e].to;
		if(v==Fa[x][0]) continue;
		Dp2[v]=Dp2[x]&&(cnt1==0||(cnt1==1&&!Dp1[v]));
		if(x>N)
		{
			int cnt2=0;
			for(int e1=Head[v];e1;e1=Edge[e1].next)
				if(Set1.count(Edge[e1].to)) ++cnt2;
			Dp2[v]&=cnt2+1==siz;
		}
	}
	for(int e=NewHead[x],v;e;e=NewEdge[e].next)
	{
		v=NewEdge[e].to;
		if(v==Fa[x][0]) continue;
		dfsCalc(v,n);
	}
}
inline bool check(int u,int v){ return In[u]<=In[v]&&In[v]<=Out[u]; }
inline int jump(int x,int k)
{
	for(int i=0;(1<<i)<=k;++i) if(k>>i&1) x=Fa[x][i];
	return x;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M,Q);
	for(int i=1,u,v;i<=M;++i)
	{
		read(u,v);
		Set2[u].insert(v),Set2[v].insert(u);
		addEdge(u,v);
	}
	Tarjan(1,0,N,Cnt,Bcc_cnt);
	dfsGraph(1,0,N,Idx);
	Dp2[1]=1;
	dfsCalc(1,N);
	for(int i=1;i<=N;++i)
		if(Dp1[i]&&Dp2[i])
		{
			for(int qx,qy;Q--;)
			{
				read(qx,qy);
				puts("Yes");
			}
			return 0;
		}
	for(int x,y;Q--;)
	{
		read(x,y);
		if(!check(x,y))
		{
			if(Dp2[x]) puts("Yes");
			else puts("No");
		}
		else if(Dp1[jump(y,Dep[y]-Dep[x]-1)]) puts("Yes");
		else puts("No");
	}
	return 0;
}
/*

*/
相关文章