Codeforces Round #768 (Div. 2) ABCDEF代码+题解

很有价值的一场比赛（完整题面链接：Codeforces Round #768 (Div. 2)），遂写下此篇。代码包含头文件OrbitZore/ATL/base/include/cardinal.hpp

A. Min Max Swap

题意

给定长度为nn的两个数组aa和bb，你可以任意执行下面的操作

  • 选定一个i (1≤i≤n)i\ (1\le i\le n)，交换aia_i和bib_i。

求ans=max⁡(a1,a2,…,an)⋅max⁡(b1,b2,…,bn)ans=\max(a_1,a_2,\dots,a_n)\cdot \max(b_1,b_2,\dots,b_n)的最小值

解法

因为乘法满足单调性，则∀i,j:ans=max⁡(ai⋅bj)\forall i,j:ans=\max(a_i\cdot b_j)

要使max⁡(ai⋅bj)\max(a_i\cdot b_j)最小，考察aia_i和bib_i中的最大值max⁡({a}∩{b})\max(\{a\}\cap \{b\})，其显然会在最终计算乘法时出现。

因为{ai}\{a_i\}和{bi}\{b_i\}有对称性，不妨令max⁡({a}∩{b})\max(\{a\}\cap \{b\})出现在{ai}\{a_i\}中，我们现在要做的就是尽可能缩小{bi}\{b_i\}使ansans最小。

因为操作之间无关，贪心即可。

代码

int main(){
	int T;cin>>T;
	while (T--){
		int n;vec<int> a[2];
		cin>>n>>rtar(a[0],n)>>rtar(a[1],n);
		using T=pair<int,bool>;
		auto [ma,j]=max({
			T{*max_element(all(a[0])),0},
			T{*max_element(all(a[1])),1}
		});
		for (int i=0;i<n;i++)
			if (a[j][i]<a[!j][i])
				swap(a[j][i],a[!j][i]);
		int mb=*max_element(all(a[!j]));
		cout << ma*mb << endl;
	}
}

B. Fun with Even Subarrays

题意

给定长度为nn的数组aa，你可以任意执行下面的操作。

  • 选定aa数组的一个在ll出开始长度为2k2k的子序列 (1≤l≤l+2⋅k−1≤n,k≥11\le l \le l+2\cdot k-1\le n,k\ge 1)，对于每一个i∈[0,k−1]i\in[0,k-1]，令al+i=al+k+ia_{l+i}=a_{l+k+i}

比如对于a=[2,1,3,4,5,3]a=[2,1,3,4,5,3]，选定l=1,k=2l=1,k=2，结果是a=[3,4,3,4,5,3]a=[3,4,3,4,5,3]。

求使整个数组所有元素相等的最小操作次数。

解法

不难发现最终相等的数字一定是ana_n。接下来贪心倒着执行操作即可。注意aia_i等于ana_n的情况。

代码

int main(){
	int T;cin>>T;
	while (T--){
		int n;
		vec<int> v;
		cin>>n>>rtar(v,n);
		int l=n-1,r=n-1,c=0;//(l,r]为所有元素相等的区间
		while (l>=0){
			while (l>=0&&v[l]==v[r]) l--;
			if (l<0) break;
			l-=(r-l);
			c++;
		}
		cout<<c<<endl;
	}
}

C. And Matching

题意

给定一个n=2mn=2^m元素的集合SS，s⊂{0,1,2,…,n−1}s\subset\{0,1,2,\dots,n-1\}。

在SS中找n2\frac n2对元素(ai,bi)(a_i,b_i)，满足

  • ∀a∈S\forall a\in S，在对中只出现过一次
  • 其∑i=1n/2ai&bi=k\sum_{i=1}^{n/2}a_i\&b_i=k,&\&为位并运算

输出任意一个解，如果无解，输出−1-1

解法

考虑k=0k=0，对于所有i≤n/2i\le n/2，生成(i,¬i)(i,\lnot i)即可。

考虑k=0∧k=n−1k\not=0\land k\not=n-1，在上述方案中将(0,n−1)(0,n-1)和(k,¬k)(k,\lnot k)中的00和kk交换即可。

考虑k=n−1k=n-1，先使用上一个方案凑出⌊(n−1)/2⌋\lfloor(n-1)/2\rfloor即2m−1−12^{m-1}-1，然后凑出2m−12^{m-1}，交换(2m−1,x)(2^{m-1},x)中的2m−12^{m-1}到任意一个(i,¬i)(i,\lnot i)中的ii即可。

考虑到m=2,n=4,k=3m=2,n=4,k=3时无法进行此操作，考察这种情况。此时相当于在1,2,31,2,3中选两个数位并，观察到a&b<min⁡(a,b) (a=b)a\&b<\min(a,b)\ (a\not=b)，其结果<3< 3。没有答案。

代码

using uint32=unsigned int;
int main(){
	int T;
	cin>>T;
	while (T--){
		uint32 n,k;
		cin>>n>>k;
		unsigned int li=n-1;
		if (n==4&&k==3){
			cout << -1 << endl;
			continue;
		}
		vec<pair<uint32,uint32>> v(n/2);
		for (int i=0;i<n/2;i++)
			v[i]={i,li&~i};
		if (k!=li){
			if (k<n/2) swap(v[k].x,v[0].x);
			else swap(v[li&~k].y,v[0].x);
		}else{
			swap(v[1].y,v[0].x);
			swap(v.back().y,v.end()[-2].y);
		}
		for (auto& [a,b]:v)
			cout<<a<<" "<<b<<"\n";
	}
}

D. Range and Partition

题意

给定一个长度为nn的数组aa，将其分割成kk个子序列，满足每个子序列中，元素c1∈[x,y]c_1\in[x,y]的数量严格大于c2∈[x,y]c_2\not\in[x,y]的数量。要求最小化y−xy-x，求一个分割方案。

解法

考虑到要比较数量，不妨设bi={1, ai∈[x,y] −1, ai∈[x,y]b_i=\begin{cases}1,\ a_i\in[x,y]\ \\ -1,\ a_i\not\in[x,y]\end{cases}，每个子序列[l,r][l,r]中∑i=lrbi≥1\sum_{i=l}^rb_i\ge1。

显然x−yx-y关于kk单调，考察固定x,yx,y下能分割子序列数量KK的最大值。

观察一个子序列，如∑i=lrbi>1\sum_{i=l}^rb_i>1，其一定可以更细分，增加分割子序列数量。下证

  • 如果bl=1∨br=1b_l=1\lor b_r=1：显然。
  • 如果bl=1∧br=1b_l\not=1\land b_r\not=1，即bl=br=−1b_l=b_r=-1：因为所有的bi=1 or −1b_i=1\ or\ -1。考察前缀和bpx=∑i=lxbibp_x=\sum_{i=l}^xb_i，bpl=−1,bpr>1bp_l=-1,bp_r>1。由离散观点上的连续性知∃t,bpt=1∧t<r−1\exist t,bp_t=1\land t<r-1。拆分成[l,t],[t+1,r][l,t],[t+1,r]即可。

所以在KK取最大值时，其每个子区间[l,r][l,r],∑i=lrbi=1\sum_{i=l}^rb_i=1，每个子区间构成了bb数组的分割，∑i=1K∑i=liribi=K=∑i=1nbi\sum_{i=1}^K\sum_{i=l_i}^{r_i}b_i=K=\sum_{i=1}^nb_i。

现在考虑固定K=kK=k，问题变成了求[x,y][x,y]，使ai∈[x,y]a_i\in[x,y]数量为kk。

观察到xx增加时，yy也增加，考虑双指针法求出每一个xx对应的yy。

现在求出了[x,y][x,y]，考虑怎么构造子序列。

既然已知∑i=lrbi=1\sum_{i=l}^{r}b_i=1，固定住ll，循环rr，如果条件成立就立即建立子序列。但是考虑到过程中可能会超过KK，还需要将最后一个区间[?,n][?,n]手动建立。

代码

int main(){
	int T;cin>>T;
	while (T--){
		int n,k;
		vec<int> v;
		cin>>n>>k>>rtar(v,n);
		vec<int> sv=v;
		sort(all(sv));
		int vl=0,vr=INF;
		auto dnext=[&](int r){
			while (r+1<n&&sv[r]==sv[r+1]) r++;
			++r;
			return r;
		};
		auto Dnext=[&](int l,int r){
			while (r<n&&r-l-n+(r-l)<k){
				r=dnext(r);
			}
			return r;
		};
		for (int l=0,r=0;l<n;l=dnext(l)){
			r=Dnext(l,r);
			if (r-l-n+(r-l)>=k){
				if (vr-vl>sv[r-1]-sv[l]){
					vr=sv[r-1];
					vl=sv[l];
				}
			}
		}
		print("{} {}\n",vl,vr);
		int b=0,cnt=1;
		for (int i=0,c=0;i<n;i++){
			c+=vl<=v[i]&&v[i]<=vr?1:-1;
			if (c==1&&cnt<k){
				cnt++;
				print("{} {}\n",b+1,i+1);
				c=0;
				b=i+1;
			}
		}
		if (cnt<=k){
			print("{} {}\n",b+1,n);
		}
	}
}

E. Paint the Middle

题意

给定一个长度为nn的数列aa和色块cc。开始时所有ci=0c_i=0。你可以进行以下操作。

  • 选中三个元素i,j,k(1≤i<j<k≤n)i,j,k(1\le i<j<k\le n)，满足ci=cj=ck=0∧ai=akc_i=c_j=c_k=0\land a_i=a_k，令cj=1c_j=1。

求∑i=1nci\sum_{i=1}^nc_i的最大值。

解法

如果∃l1<l2<r2<r1\exist l_1<l_2<r_2<r_1，满足cl1=cl2=cr2=cr2=0∧al1=ar1∧al2=ar2c_{l_1}=c_{l_2}=c_{r_2}=c_{r_2}=0\land a_{l_1}=a_{r_1}\land a_{l_2}=a_{r_2}。那么可以不管l2,r2l_2,r_2。（区间包含）

有了这个结论，我们就可以对于每一个x=ai=akx=a_i=a_k，考察min⁡i\min{i}和max⁡k\max k即可。

如果∃l1<l2<r1<r2\exist l_1<l_2<r_1<r_2，满足cl1=cl2=cr2=cr2=0∧al1=ar1∧al2=ar2c_{l_1}=c_{l_2}=c_{r_2}=c_{r_2}=0\land a_{l_1}=a_{r_1}\land a_{l_2}=a_{r_2}。那么可以令cl2∨r1c_{l_2\lor r_1}变成1。令cl2c_{l_2}还是cr1c_{r_1}变成1都是一样的，因为对两个区间包含的元素的操作我们可以在令cl2c_{l_2}还是cr1c_{r_1}变成1之前进行。对于两个区间之外的，则不影响。不妨就令cl2=1c_{l_2}=1。（区间交叉）

将视角放回在cic_i数组上，尝试循环设置cic_i。我们首先根据区间包含，考虑维护一个最长区间，如果点在区间内则设置cic_i；而根据区间交叉，循环到l2l_2时一定要将r2r_2代入最长区间并设置cl2c_{l_2}。但是这样r1r_1会被设置，我们不想要设置r1r_1，拿个变量记录即可。

代码

int main(){
	int n;
	vec<int> v;
	cin>>n>>rtar(v,n);
	vec<int> lst(n+2,0);
	for (int i=0;i<n;i++) lst[v[i]]=i;
	int mlst=-1,pre=-1,cnt=0;//mlst即最长区间，pre即记录r1，cnt为计数
	for (int i=0;i<n;i++){
		cmax(mlst,lst[v[i]]);
		if (pre<=i) pre=mlst;
		else cnt++;
	}
	cout<<cnt<<endl;
}

F. Flipping Range

题意

给定一个长度为nn的数组aa和mm个正整数（1≤bi≤⌊n2⌋1\le b_i\le \lfloor\frac{n}{2}\rfloor）的集合BB。可以对数组aa执行下面的操作:

  1. 选中一个x∈Bx\in B
  2. 在aa中选中长度为xx的区间[l,l+x−1][l,l+x-1]，对其上每一个数乘以−1-1。正式地￥￥，即选定ll,1≤l∧l+x−1≤n1\le l\land l+x-1\le n，对于所有i∈[l,l+x−1]i\in[l,l+x-1]令ai:=−aia_i:=-a_i。（翻转）

求∑i=1nai\sum_{i=1}^na_i的最大值。

解法

观察到1≤bi≤⌊n2⌋1\le b_i\le \lfloor \frac n 2 \rfloor，对于bb数组的两个元素bi<bjb_i<b_j，可以有这两种组合，长度为bib_i的区间和长度为bjb_j的区间共用一个起点；共用一个终点。起点的组合可以使[l+bi,l+bj−1],1≤l≤n−bj+1[l+b_i,l+b_j-1],1\le l\le n-b_j+1这些区间翻转，终点的组合可以使[l,l+bj−bi−1],1≤l≤n−bj+1[l,l+b_j-b_i-1],1\le l\le n-b_j+1这些区间翻转。其长度均为bj−bib_j-b_i，前者起点为[bi+1,n−bj+bi+1][b_i+1,n-b_j+b_i+1]，后者起点为[1,n−bj+1][1,n-b_j+1]，因为所有bi≤⌊n2⌋b_i\le \lfloor\frac n 2 \rfloor，所以n−bj+1≥bi+1n-b_j+1\ge b_i+1。其结果是组合等价于产生新的集合BB元素bj−bib_j-b_i。考虑更相减损法，其等价于BB集合中只有一个元素Bm=gcd(B)Bm=gcd(B)。

定义cic_i为对一个元素aia_i为区间起点的翻转次数，因为重复翻转没有意义，所以ci={0,1}c_i=\{0,1\}。

现在我们要处理的区间长度是固定的，那么不难发现∀x∈[0,(n−1)%Bm],⊕i∈[1,n]∩{k∗x+1∣k∈Z}ci\forall x\in[0,(n-1)\%Bm],\oplus_{i\in [1,n]\cap\{k*x+1|k\in Z\}}c_i都是一个定值（⊕\oplus表示异或），其等于总翻转次数模2。

定义状态函数f[res][d],i∈[0,Bm),d∈{0,1}f[res][d],i\in[0,Bm),d\in\{0,1\}，意义为aa数组中{ai∣i∈[1,n]∩{k∗x+res+1∣k∈Z}}\{a_i|i\in [1,n]\cap\{k*x+res+1|k\in Z\}\}取得最大值的情况。

对于每个aia_i都可能翻转，更新状态即可。

初始化为f[i][0]=0,f[i][1]=−∞f[i][0]=0,f[i][1]=-\infin。因为后者必须要有操作。

转移方程见代码。

代码

int main(){
	int T;cin>>T;
	while (T--){
		int n,m,g=0;vec<int> v,z;
		cin>>n>>m>>rtar(v,n)>>rtar(z,m);
		for (auto i:z) g=gcd(i,g);
		vec<array<ll,2>> dp(g,{0,(ll)MINF/2});
		for (int i=0;i<n;i++){
			int rem=i%g;
			tie(dp[rem][0],dp[rem][1])=tuple(
				max(dp[rem][0]+v[i],dp[rem][1]-v[i]),
				max(dp[rem][0]-v[i],dp[rem][1]+v[i])
			);
		}
		ll sum0=0,sum1=0;
		for (int i=0;i<g;i++){
			sum0+=dp[i][0];
			sum1+=dp[i][1];
		}
		cout << max(sum0,sum1) << endl;
	}
}