专栏文章

题解：P13093 [FJCPC 2025] 卡牌游戏

MMeickol
P13093题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min7bcbj
此快照首次捕获于
2025/12/01 21:45
3 个月前
此快照最后确认于
2025/12/01 21:45
3 个月前
查看原文

性质挖掘 + 前缀和 + 贪心 + STL set + STL 二分查找

首先要能手玩样例发现出一个性质：对于区间 [l,r][l,r]，若区间长度为偶数，区间 [l,r][l,r] 内的数的位置奇偶互换；若为奇数，区间 (l,r](l,r] 内的数的位置奇偶互换。
由于考虑区间长度为奇数时等价于修改一个区间 (l,r](l,r]。所以实际上我们只需考虑长度为偶数的区间。
在知道了上面那个性质之后，就可以考虑枚举长度为偶数的区间 [l,r][l,r] 作为修改的区间，当确定了 [l,r][l,r] 时，其实当前整个序列的答案就确定出来了，结合前缀和快速计算。因为 [l,r][l,r] 中的奇偶性反转了，以奇数下标元素之和为例，当操作 [l,r][l,r] 后奇数下标的元素之和为：
res_odd=prefix_oddl−1+(prefix_evenr−prefix_evenl−1)+prefix_odd2n−prefix_oddrres\_odd=prefix\_odd_{l-1}+(prefix\_even_{r}-prefix\_even_{l-1})+prefix\_odd_{2n}-prefix\_odd_{r}
偶数下标元素之和同理，但其实可以直接通过 ∑i=1nai−res_odd\displaystyle \sum _{i=1}^n a_i - res\_odd 得到，不需要再考虑其计算式。
但上面这个枚举 [l,r][l,r] 区间做法是 O(n2)O(n^2) 的，显然会 TLE，考虑优化。
对于前面当操作 [l,r][l,r] 后奇数下标的元素之和，其实你可以对式子移项进行简单转化，把下标相同的放一起：
(prefix_oddl−1−prefix_evenl−1)−(prefix_oddr−prefix_evenr)+prefix_odd2n(prefix\_odd_{l-1}-prefix\_even_{l-1})-(prefix\_odd_{r}-prefix\_even_{r})+prefix\_odd_{2n}
定义 diffi=prefix_oddi−prefix_evenidiff_i=prefix\_odd_i-prefix\_even_i。则当操作 [l,r][l,r] 后，奇数下标的元素之和为：
res_odd=diffl−1−diffr+prefix_odd2nres\_odd=diff_{l-1}-diff_{r}+prefix\_odd_{2n}
根据贪心的考虑，要让最坏情况下得到的数字之和最大，即考虑让当前操作 [l,r][l,r] 区间后奇数下标的元素之和与偶数下标的元素之和最大，即最大化下式：
min⁡(res_odd,∑i=1nai−res_odd)\min \Big(res\_odd,\displaystyle \sum _{i=1}^n a_i- res\_odd \Big)
那么显然两者尽可能接近，即考虑让 res_oddres\_odd 尽可能接近 ∑i=1nai2\dfrac{\sum _{i=1}^n a_i}{2}。
即让 diffl−1−diffr+prefix_odd2ndiff_{l-1}-diff_{r}+prefix\_odd_{2n} 尽可能接近 ∑i=1nai2\dfrac{\sum _{i=1}^n a_i}{2}。
那么可以考虑每次枚举右端点 rr，从前面的位置中找值尽可能接近 ∑i=1nai2+diffr−prefix_odd2n\dfrac{\sum _{i=1}^n a_i}{2}+diff_r-prefix\_odd_{2n} 的 diffl−1diff_{l-1}，考虑经典处理方式二分查找即可。
具体地说：记 val=∑i=1nai2+diffr−prefix_odd2nval=\dfrac{\sum _{i=1}^n a_i}{2}+diff_r-prefix\_odd_{2n}，则可以通过找 ≥val\ge val 的第一个值，其迭代器为 it⁡\operatorname{it}，那么 it⁡\operatorname{it} 和 it⁡−1\operatorname{it}-1 这两个迭代器可以作为备选答案。在保证迭代器合法性的基础上打擂台比较即可。
细节一：用 STL set 维护 diffdiff 值。
细节二：由于 [l,r][l,r] 长度是偶数，那么 l,rl,r 奇偶性相异，但是我们要找的下标为 l−1l-1，而 l−1l-1 和 rr 奇偶性相同。所以我们在 set STL 上二分查找时需要从与 rr 的奇偶性相同的 diffdiff 值中查找，于是 STL set 需要分下标的奇偶来维护 diffdiff 值。
细节三：在 STL set 上查找 ≥val\ge val 的值时，可能找不到，迭代器可能不存在，需要特判，避免计算错误。
代码如下：
CPP
#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int N=2e5+5;
int n;
int a[N];
LL diff[N];
void solve(){
	cin>>n;
	rep(i,1,n*2) cin>>a[i];
	LL sum=0;
	LL odd_sum=0,even_sum=0;
	rep(i,1,n*2){
		sum+=a[i];
		if(i&1) odd_sum+=a[i];
		else even_sum+=a[i];
		diff[i]=odd_sum-even_sum;
	}
	set<LL> se[2];
	LL ans=0;
	rep(r,0,n*2){
		if(r){
			LL val=sum/2+diff[r]-odd_sum;
			auto it=se[r&1].lower_bound(val);
			if(it!=se[r&1].end()){
				LL res_odd=*it-diff[r]+odd_sum;
				ans=max(ans,min(res_odd,sum-res_odd));
			}
			if(it!=se[r&1].begin()){
				it--;
				if(it!=se[r&1].end()){
					LL res_odd=*it-diff[r]+odd_sum;
					ans=max(ans,min(res_odd,sum-res_odd));
				}
			}
		}
		se[r&1].insert(diff[r]);
	}
	cout<<ans;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...