Reincarnation

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

长沙一中NOIP2021模拟题 - Test20211109

发表于 分类于
本文字数： 9.6k 阅读时长 ≈ 9 分钟

非常坏题目，喷来自选手。

情景剧（sitcom）

形式化题意

给定一个长度为 的序列 ，定义一个区间 的权值为：

求出最大子区间权值。

数据范围：

时空限制：

很好的题，结果给我卡得妈都被抓走了。

考虑一个经典的结构，就是以 表示当 作为最值的时候能够延伸到的最大区间。那么答案一定是当某一个 作为最值时，其对应最大区间里找到的反向最值之积。

对 的处理是一个非常经典的单调栈问题，可以 全部处理出来，现在的瓶颈在于如何能过快速的多次求区间最值。显然线段树 是非常不可接受的，而最优秀的 表也只能做到 。

题解的做法运用了一些性质，在于 一定是互相包含或相离的，所以这是一个经典的笛卡尔树结构，所以用笛卡尔树分治是可以线性求解的。

但我是暴力选手，而四毛子我又不会，所以我选择 lxl 表，也就是分块 表。

考虑将整个序列分块，每一块长度为 ，对每一个散块记录 表示前后缀最值。然后将每个块作为结点建立块间的 表。

对于询问，如果是很多个块，就可以用块间 表配合前后缀最值直接查，块内也只能暴力扫，当然也可以 处理区间最值，但你这样写不如直接写 。

所以现在我们得到了一个 的做法。你取个 都行，反正不会超线性即可。

比较逆天的是写这个之后 挂掉了，所以拼了一个普通 表才过。太抽象了。

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
#pragma GCC optimize("O2")

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
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 ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(char c){ putchar(c); }
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
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 Int=__int128_t;
const int MAXN=2e6+10;
const int Inf=0x3f3f3f3f;
int N,val[MAXN],Uni,Tot;
int Stk[MAXN],Top;
int Lst[2][MAXN],Rst[2][MAXN],Lg[MAXN];
int Pre[MAXN][2],Suf[MAXN][2];
int St[2][MAXN][22],Bel[MAXN];
inline void build()
{
	for(int i=2;i<=N;++i) Lg[i]=Lg[i>>1]+1;
	int j=1;Uni=Lg[N];
	for(int i=1;i<=N;++i)
	{
		Bel[i]=j;
		if(Bel[i]==Bel[i-1])
		{
			Pre[0][i]=std::min(Pre[0][i-1],val[i]);
			Pre[1][i]=std::max(Pre[1][i-1],val[i]);
		}
		else Pre[0][i]=Pre[1][i]=val[i];
		if(!(i%Uni)) ++j;
	}
	if(N%Uni) Tot=j;
	else Tot=j-1;
	for(int i=N;i;--i)
	{
		if(Bel[i]==Bel[i+1])
		{
			Suf[0][i]=std::min(Suf[0][i+1],val[i]);
			Suf[1][i]=std::max(Suf[1][i+1],val[i]);
		}
		else Suf[0][i]=Suf[1][i]=val[i];
	}
	for(int i=1;i<=Tot;++i) St[0][i][0]=Suf[0][Uni*(i-1)+1],St[1][i][0]=Suf[1][Uni*(i-1)+1];
	for(int s=1;s<=Lg[Tot];++s)
		for(int i=1;i+(1<<s)-1<=Tot;++i)
		{
			St[0][i][s]=std::min(St[0][i][s-1],St[0][i+(1<<(s-1))][s-1]);
			St[1][i][s]=std::max(St[1][i][s-1],St[1][i+(1<<(s-1))][s-1]);
		}
}
inline Int queryMax(int l,int r)
{
	int bl=Bel[l],br=Bel[r],mx=-Inf;
	if(bl!=br)
	{
		++bl,--br;
		if(bl<=br)
		{
			int lg=Lg[br-bl+1];
			mx=std::max(St[1][bl][lg],St[1][br-(1<<lg)+1][lg]);
		}
		checkMax(mx,std::max(Suf[1][l],Pre[1][r]));
	}
	else for(int i=l;i<=r;++i) checkMax(mx,val[i]);
	return mx;
}
inline Int queryMin(int l,int r)
{
	int bl=Bel[l],br=Bel[r],mn=Inf;
	if(bl!=br)
	{
		++bl,--br;
		if(bl<=br)
		{
			int lg=Lg[br-bl+1];
			mn=std::min(St[0][bl][lg],St[0][br-(1<<lg)+1][lg]);
		}
		checkMin(mn,std::min(Suf[0][l],Pre[0][r]));
	}
	else for(int i=l;i<=r;++i) checkMin(mn,val[i]);
	return mn;
}
inline void getMin()
{
	val[0]=val[N+1]=-Inf;
	Stk[Top=1]=0;
	for(int i=1;i<=N;++i)
	{
		while(Top&&val[Stk[Top]]>=val[i]) --Top;
		Lst[0][i]=Stk[Top]+1;
		Stk[++Top]=i;
	}
	Stk[Top=1]=N+1;
	for(int i=N;i>=1;--i)
	{
		while(Top&&val[Stk[Top]]>=val[i]) --Top;
		Rst[0][i]=Stk[Top]-1;
		Stk[++Top]=i;
	}
}
inline void getMax()
{
	val[0]=val[N+1]=Inf;
	Stk[Top=1]=0;
	for(int i=1;i<=N;++i)
	{
		while(Top&&val[Stk[Top]]<=val[i]) --Top;
		Lst[1][i]=Stk[Top]+1;
		Stk[++Top]=i;
	}
	Stk[Top=1]=N+1;
	for(int i=N;i>=1;--i)
	{
		while(Top&&val[Stk[Top]]<=val[i]) --Top;
		Rst[1][i]=Stk[Top]-1;
		Stk[++Top]=i;
	}
}
namespace Subtask2
{
	inline void build()
	{
	    St[0][1][0]=St[1][1][0]=val[1];
	    for(int i=2;i<=N;++i) St[0][i][0]=St[1][i][0]=val[i],Lg[i]=Lg[i>>1]+1;
	    for(int s=1;(1<<s)<N;++s)
	        for(int i=1;i+(1<<s)-1<=N;++i)
	        {
	            St[0][i][s]=std::min(St[0][i][s-1],St[0][i+(1<<(s-1))][s-1]);
	            St[1][i][s]=std::max(St[1][i][s-1],St[1][i+(1<<(s-1))][s-1]);
	        }
	}
	inline int queryMin(int l,int r)
	{
	    int lg=Lg[r-l+1];
	    return std::min(St[0][l][lg],St[0][r-(1<<lg)+1][lg]);
	}
	inline int queryMax(int l,int r)
	{
	    int lg=Lg[r-l+1];
	    return std::max(St[1][l][lg],St[1][r-(1<<lg)+1][lg]);
	}
	inline bool main()
	{
		build();
		Int ans=0;
		for(int i=1;i<=N;++i)
		{
			checkMax(ans,(Int)val[i]*(Rst[0][i]-Lst[0][i]+1)*queryMax(Lst[0][i],Rst[0][i]));
			checkMax(ans,(Int)val[i]*(Rst[1][i]-Lst[1][i]+1)*queryMin(Lst[1][i],Rst[1][i]));
		}
		write(ans);	
		return 0;
	}
}
int main()
{
	freopen("sitcom.in","r",stdin);
	freopen("sitcom.out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(val[i]);
	getMin(),getMax();
	if(N<=100000) return Subtask2::main();
	build();
	Int ans=0;
	for(int i=1;i<=N;++i)
	{
		checkMax(ans,(Int)val[i]*(Rst[0][i]-Lst[0][i]+1)*queryMax(Lst[0][i],Rst[0][i]));
		checkMax(ans,(Int)val[i]*(Rst[1][i]-Lst[1][i]+1)*queryMin(Lst[1][i],Rst[1][i]));
	}
	write(ans);
	return 0;
}
/*

*/

跳棋（checkers）

形式化题意

给定一个长度为 的 串，其中存在 ? 表示既可为 也可为 。 表示跳棋棋子，可以跳过一个相邻的棋子落到另外一边的空地上。求对于每一种初始情况，结束情况之和（如果有两个初始状态对应了同一个终止状态，计算 次答案）。对 取模。

数据范围：

本来以为是一个比较厉害的区间 ，但不过还是一个比较厉害的线性 。

题目中给了一个较为复杂的操作，但事实上就是让 110 与 011 相互变化。

我们考虑将每一次贡献拆分成两部分。第一部分，我们考虑求解 ?，得到当有 个 11， 个 0 的初始情况有多少种。

这个转移可以通过 实现，表示当前第 位中，有 个 11，有 个 0 ，而第 位是否为 的状态总数。这个转移可以通过时间复杂度 ，空间复杂度 实现。

然后考虑对于每个 ，我们怎么求终止状态。对于任意有奇数个 的连续区间，无论如何变化，必存在至少 个 在原位置无法移动。

那么， 与奇数段 的相对位置，顺序和个数都不会变化，而奇数段 将整个序列划分成了很多部分。在其中 0 和 11 的位置随意。一共有至多 个奇数段 。然后考虑组合意义，将 0 和 11 组合得到答案：

总时间复杂度 ，空间那么多会炸，所以滚动一下 。

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
#pragma GCC optimize("O2")

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
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 ...Arc>
inline void read(T &x,Arc &...arc){ read(x),read(arc...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+48);
}
inline void write(char c){ putchar(c); }
inline void write(bool x){ putchar(x?'1':'0'); }
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...Arc>
inline void write(T x,Arc ...arc){ write(x),write(arc...); }
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=5e2+10;
const int Mod=1e9+7;
template<class T>
inline void add(T &x,T y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N;
char Str[MAXN];
int Dp[2][MAXN][MAXN][2];
int C[MAXN<<1][MAXN<<1];
inline void init(int n)
{
	for(int i=1;i<=n;++i) C[i][0]=C[0][i]=1;
	for(int i=1;i<=n;++i)
		for(int j=0;j<=i;++j)
			if(!j) C[i][j]=1;
			else C[i][j]=(C[i-1][j-1]+C[i-1][j])%Mod;
}
int main()
{
	freopen("checkers.in","r",stdin);
	freopen("checkers.out","w",stdout);
	read(N),scanf("%s",Str+1);
	init(MAXN*2-20);
	Dp[0][0][0][0]=1;
	for(int i=1;i<=N;++i)
	{
		int o=i&1;
		for(int j=0;j<=i;++j)
			for(int k=0;k<=i;++k)
				Dp[o][j][k][0]=Dp[o][j][k][1]=0;
		if(Str[i]!='0')
		{
			for(int j=0;j<=i;++j)
				for(int k=0;k<=i;++k)
				{
					if(j) add(Dp[o][j][k][0],Dp[o^1][j-1][k][1]);
					add(Dp[o][j][k][1],Dp[o^1][j][k][0]);
				}
		}
		if(Str[i]!='1')
		{
			for(int j=0;j<=i;++j)
				for(int k=0;k<=i;++k)
				{
					if(k) add(Dp[o][j][k][0],Dp[o^1][j][k-1][0]);
					if(k) add(Dp[o][j][k][0],Dp[o^1][j][k-1][1]);
				}
		}
	}
	ll ans=0;
	for(int j=0;j<=N;++j)
		for(int k=0;k<=N;++k)
			add(ans,(ll)Dp[N&1][j][k][0]*C[j+k][j]%Mod),
			add(ans,(ll)Dp[N&1][j][k][1]*C[j+k][j]%Mod);
	write(ans);
	return 0;
}
/*

*/

抽卡（drawing）

印象深刻（unforget）

相关文章