Reincarnation

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

ZROI - 20连测day4

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

遗憾离场。

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
// ----- Eternally question-----
// Problem: A. 【noip赛前20天冲刺集训 day4】正在出模拟赛
// Contest: ZROI - 23noip赛前20天冲刺 day4
// URL: http://zhengruioi.com/contest/1468/problem/2701
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-12 08:44:43
// ----- 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; }
#define popcount(x) __builtin_popcount(x)
const int MAXN=1e5+10,MAXM=5,MAXS=1<<4|10;
const int Inf=0x3f3f3f3f;
int N,M,K[MAXM],St[MAXN],ans;
int Cnt[MAXS];
std::vector<int>vec;
inline bool cmp(int a,int b){ return popcount(a)<popcount(b); }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	for(int i=1;i<=M;++i)
	{
		read(K[i]);
		for(int j=1,x;j<=K[i];++j) read(x),St[x]|=1<<(i-1);
	}
	std::sort(St+1,St+N+1);
	std::reverse(St+1,St+N+1);
	Cnt[0]=Inf;
	for(int i=1;i<=N;++i)
		for(int s=(1<<M)-1;~s;--s)
			if(Cnt[s]&&(s&St[i])==0){ --Cnt[s],++Cnt[s|St[i]];break; }
	for(int s=1;s<(1<<M);++s) ans+=Cnt[s];
	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
// ----- Eternally question-----
// Problem: B. 【noip赛前20天冲刺集训 day4】正在打模拟赛
// Contest: ZROI - 23noip赛前20天冲刺 day4
// URL: http://zhengruioi.com/contest/1468/problem/2702
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-12 09:54: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<int,int>;
#define fir first
#define sec second
#define Mkr std::make_pair
const int MAXN=2e5+10;
int N,K;
ll Dp[MAXN][2],ans;
std::vector<Pir>Edges[MAXN];
inline bool cmp(int a,int b){ return Dp[a][0]>Dp[b][0]; }
void dpTree(int x,int last)
{
	std::vector<int>Son;
	for(auto v:Edges[x])
	{
		if(v.fir==last) continue;
		dpTree(v.fir,x);
		Dp[v.fir][0]+=v.sec,Dp[v.fir][1]+=v.sec;
		Son.push_back(v.fir);
	}
	std::sort(Son.begin(),Son.end(),cmp);
	int cnt=0;ll sum=0;
	for(int v:Son)
	{
		Dp[x][1]+=Dp[v][0];
		++cnt<K?Dp[x][0]+=Dp[v][0]:0;
		cnt<=K?sum+=Dp[v][0]:0;
	}
	cnt=0;
	ll res=Dp[x][1];
	for(int v:Son)
	{
		++cnt;
		if(K>1) checkMax(Dp[x][1],Dp[x][0]-Dp[cnt<K?v:Son[K-2]][0]+Dp[v][1]);
		checkMax(res,sum-Dp[cnt<=K?v:Son[K-1]][0]+Dp[v][1]);
	}
	checkMax(ans,res);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K);
	if(!K) return puts("0"),0;	
	for(int i=2,u,v,w;i<=N;++i)
	{
		read(u,v,w);
		Edges[u].push_back(Mkr(v,w));
		Edges[v].push_back(Mkr(u,w));
	}
	dpTree(1,0);
	write(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天冲刺集训 day4】遗憾离场
// Contest: ZROI - 23noip赛前20天冲刺 day4
// URL: http://zhengruioi.com/contest/1468/problem/2703
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-12 10:08:50
// ----- 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=4e5+10;
const int Inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int S,C;
int Dp[MAXN],g[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(S,C);C>>=1;
	int Len=S<<1;
	std::memset(Dp,0x3f,sizeof(Dp));
	for(int i=0;i<=C-2;++i) Dp[i]=i+2;
	for(int h=1;h*h<=S;++h)
	{
		for(int i=0;i<=Len;++i) g[i]=Dp[i];
		g[0]=0;
		for(int w=0;w<=Len;++w)
		{
			if(w>=2*h-1) checkMin(g[w],g[w-(2*h-1)]+1);
			if(w>=2*h*(h-1)) checkMin(Dp[w],g[w-2*h*(h-1)]+2*h);
		}
	}
	ll ans=0;
	for(int i=0;i<=Len;++i) if(Dp[i]<=C)
		ans+=std::max(0ll,std::min((ll)S-(Dp[i]+i)/2+1,(ll)(C-Dp[i])2+1));
	write(ans);
	return 0;
}
/*

*/

D. 正在重测

题目简介

给定一个长度为 的序列 ，保证 互不相同。定义一次合法的操作为：

  • 选择 ，满足 ，将 变成 。

然后定义一个序列合法，当且仅当这个序列在进行若干次合法操作后能够变成一个严格单调递增的序列。

给定 的排列 ，以及 次操作，每次交换 和 ，操作结束后求出最小的 满足子序列 是一个合法序列。保证 唯一存在。

数据范围：

时空限制：

你考虑逆向这个过程，我们从严格递增序列向前回推，发现一个有趣的性质，任何一个数，其右侧小于它的数的个数始终为偶数。且这个条件是充分必要的，也就是满足这个形式的序列都是合法的。

考虑使用超级武器分块维护这个奇妙的信息，设 右侧小于 的数有 个，对于操作 ，我们对其所属块暴力重构，然后对于其中间的块，影响了一个值域区间的 。

我们对每一块进行内部有序排序，然后维护 的差分，然后对中间的块进行 std::lower_bound 后可以进行前缀后缀维护，而块是可以通过线性重构的，所以这样做的时间复杂度为 。已经可以通过了。

但是还可以优化，也就是去掉 std::lower_bound 的过程，发现修改和查询是单点和前缀的区分，可以用 的二次分块做到 ，空间也需要这么多，且常数巨大。

还有时间分块的 的做法，但是出题人不讲我也不会。

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
// ----- Eternally question-----
// Problem: D. 【noip赛前20天冲刺集训 day4】正在重测
// Contest: ZROI - 23noip赛前20天冲刺 day4
// URL: http://zhengruioi.com/contest/1468/problem/2704
// Memory Limit: 1024 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-10-12 21:06:14
// ----- 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; }
#define getCp(b,v) (!v?0:(Cpb[b][Bel[v]-1]+Cps[b][v]))
const int MAXN=1e5+10,MAXB=4e2+10,MAXM=8e2+10;
int N,Q,Uni,p[MAXN],r[MAXN],ans;
int Bel[MAXN],Lst[MAXB],Rst[MAXB];
int Id[MAXN],Cnt[MAXN],Diff[MAXN],tmp[MAXB];
short Cps[MAXM][MAXN],Cpb[MAXM][MAXM];
bool Tag[MAXB];
inline bool cmp(int i,int j){ return p[i]<p[j]; }
struct BIT
{
	int Tre[MAXN],Siz;
	inline void build(int n){ Siz=n;for(int i=0;i<=n;++i) Tre[i]=0; }
	inline int lowbit(int x){ return x&(-x); }
	inline void add(int x){ for(;x<=Siz;x+=lowbit(x)) Tre[x]^=1; }
	inline int query(int x)
	{
		int res=0;
		for(;x;x-=lowbit(x)) res^=Tre[x];
		return res;
	}
	inline int get(int l,int r){ return query(r)^query(l-1); }
}Tre;
inline void build(int bel)
{
	if(!Tag[bel]) return ;
	int l=Lst[bel],r=Rst[bel];
	Tag[bel]=0,::r[Id[l]]=Diff[l];
	for(int i=l+1;i<=r;++i) ::r[Id[i]]=::r[Id[i-1]]^Diff[i];
}
inline void rebuild(int bel)
{
	int l=Lst[bel],r=Rst[bel];
	Diff[l]=::r[Id[l]],tmp[bel]=Diff[l];
	for(int i=l+1;i<=r;++i) Diff[i]=(::r[Id[i]]^::r[Id[i-1]]),tmp[bel]+=Diff[i];
}
inline void modify(int bel,int x)
{
	int l=Lst[bel],r=Rst[bel],pos=0;
	for(int i=l;i<=r;++i) if(p[Id[i]]==x){ pos=i;break; }
	for(int i=pos;i>l;--i)
	{
		if(p[Id[i]]<p[Id[i-1]]) std::swap(Id[i-1],Id[i]);
		else break;
	}
	for(int i=pos;i<r;++i)
	{
		if(p[Id[i]]>p[Id[i+1]]) std::swap(Id[i],Id[i+1]);
		else break;
	}
}
inline void modifyBlock(int l,int r,int vl,int vr)
{
	if(l>r) return ;
	--vl;
	for(int bel=Bel[l];bel<=Bel[r];++bel)
	{
		int _l=Lst[bel],_r=Rst[bel];
		if(bel==Bel[l]||bel==Bel[r])
		{
			build(bel);
			int ml=std::max(l,_l),mr=std::min(r,_r);
			for(int i=ml;i<=mr;++i) if(vl<p[i]&&p[i]<=vr) ::r[i]^=1;
		}
		else
		{
			int nl=getCp(bel,vl)+_l,nr=getCp(bel,vr)+_l-1;
			if(nl>nr||nr<_l||_r<nl) continue;
			Tag[bel]=1,++nr;
			tmp[bel]+=(Diff[nl]?-1:1),Diff[nl]^=1;
			if(nr<=_r) tmp[bel]+=(Diff[nr]?-1:1),Diff[nr]^=1;
		}
	}
}
inline void modifyCp(int bel,int l,int r,int v)
{
	int bl=Bel[l],br=Bel[r+1];
	for(int i=bl;i<br;++i) Cpb[bel][i]+=v;
	for(int i=l;i<=Rst[bl];++i) Cps[bel][i]+=v;
	for(int i=r+1;i<=Rst[br];++i) Cps[bel][i]-=v;
}
inline int query(int x,int k)
{
	if(!x||!k) return 0;
	int res=0,b=Bel[x];
	for(int i=1;i<b;++i) res^=getCp(i,k);
	for(int i=Lst[b];i<=x;++i) res^=(p[i]<=k);
	return res;
}
inline void modifySwap(int x,int y)
{
	x=N-x+1,y=N-y+1;
	if(x>y) std::swap(x,y);
	modifyBlock(x,y,std::min(p[x],p[y]),std::max(p[x],p[y]));
	r[x]=query(y-1,p[x]-1)&1,r[y]=query(x-1,p[y]-1)&1;
	if(p[x]<p[y])
	{
		modifyCp(Bel[x],p[x],p[y]-1,-1),
		modifyCp(Bel[y],p[x],p[y]-1,1);
	}
	else
	{
		r[x]^=1;
		modifyCp(Bel[x],p[y],p[x]-1,1),
		modifyCp(Bel[y],p[y],p[x]-1,-1);
	}
	std::swap(p[x],p[y]),std::swap(r[x],r[y]);
	if(Bel[x]==Bel[y])
	{
		int b=Bel[x];
		int l=Lst[b],r=Rst[b],px=0,py=0;
		for(int i=l;i<=r;++i)
		{
			if(Id[i]==x) px=i;
			if(Id[i]==y) py=i;
		}
		std::swap(Id[px],Id[py]);
	}
	else modify(Bel[x],p[x]),modify(Bel[y],p[y]);
	rebuild(Bel[x]);
	if(Bel[x]!=Bel[y]) rebuild(Bel[y]);
	ans=N+1;
	for(int l=1,bel=1;l<=N;l+=Uni,++bel)
	{
		int r=std::min(l+Uni-1,N);
		if(!tmp[bel]) continue;
		build(bel);
		for(int i=l;i<=r;++i) if(::r[i]){ ans=i;break; }
		break;
	}
	write(N-ans+2,'\n');
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);Tre.build(N);
	Uni=std::sqrt(4.0*N)+1;
	for(int i=1;i<=N;++i) read(p[N-i+1]);
	for(int i=1;i<=N;++i) r[i]=Tre.query(p[i]),Tre.add(p[i]);
	for(int i=1;i<=N;++i) Id[i]=i;
	for(int l=1,t=1;l<=N;l+=Uni,++t)
	{
		int r=std::min(N,l+Uni-1);
		for(int i=l;i<=r;++i) Bel[i]=t;
		Lst[t]=l,Rst[t]=r;
		std::sort(Id+l,Id+r+1,cmp);
		rebuild(t);
		for(int i=l;i<=r;++i) ++Cnt[p[i]];
		for(int vl=1,bel=1;vl<=N;vl+=Uni,++bel)
		{
			int vr=std::min(N,vl+Uni-1);
			Cps[t][vl]=Cnt[vl];
			for(int i=vl+1;i<=vr;++i) Cps[t][i]=Cps[t][i-1]+Cnt[i];
			Cpb[t][bel]=Cpb[t][bel-1]+Cps[t][vr];
		}
		for(int i=l;i<=r;++i) Cnt[p[i]]=0;
	}
	Bel[N+1]=(N+Uni-1)/Uni+1;
	for(int x,y;Q--;)
	{
		read(x,y);
		modifySwap(x,y);
	}
	return 0;
}
/*

*/
相关文章