C/C++教程

XX Open Cup, Grand Prix of Tokyo D,L

本文主要是介绍XX Open Cup, Grand Prix of Tokyo D,L,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

D
二分max值为L,判定能否使用\(\leq L\)的数构造出答案。

暂时不管L的限制。此时如果我们有一组解,表示为\(c_{0},c_{1},...,c_{60}\),其中\(c_{i}\)是有多少个数在第\(i\)位为\(1\)。那么我们可以将\(c_{i}\)减\(2\),\(c_{i-1}\)加\(4\);或者\(c_{i}\)减\(4\),\(c_{i+1}\)加\(2\),构造出所有合法解。(为什么不是\(c_{i}\)减\(1\),\(c_{i-1}\)加\(2\)呢?因为我们不仅要让\(sum\)不变,还要让\(xor\)不变,所以加减的数必然是偶数)

那么我们如何构造\(c\)?设\(x_{i}\)为异或和\(X\)的第\(i\)位,\(s_{i}\)为和\(S\)的第\(i\)位。那么\(x_{i}=1\)意味着\(c_{i}\)为奇数,也就是\(c_{i}\geq 1\),那么我们不妨将\(X\)减去\(S\),此时每个数都出现了偶数次,那么我们将其除以二,我们设这样操作后的数为\(Y\)(\(Y=(S-X)/2\)),第\(i\)位为\(y_{i}\)。不难构造出\(c_{i}=2y_{i}+x_{i}\)。

L
我们对第一个限制分治,也就是,我们对\(y\)坐标从小到大排序,每次分成左右两个区间,并且记录出现在左侧的红点和出现在右侧的蓝点,那么我们就想让红点和蓝点匹配。

直接暴力匹配是\(O(n^2)\)的(当然也体现不出分治的意义),但是这里有一个结论:最大权值的匹配必然是有一个颜色的点的权值最大。也就是,只能是左侧红点中\(w\)最大的和右侧所有蓝点匹配;或者右侧蓝点\(w\)最大的和左侧红点匹配。

证明很简单——假设当前我们的询问为\([L,R]\),当前分治的区间为\([lef,rig]\),左半部分为\([lef,mid]\),右半部分为\([mid+1,rig]\)。若\(L\leq lef\leq rig\leq R\),那么区间内所有点对都满足条件\(2\)。否则若\(lef\leq L\leq mid\leq R\leq rig\),则左侧最大值和右侧最大值会落到\([lef,L-1],[L,mid],[mid+1,R],[R+1,rig]\)这四个区间的两个中,那么根据抽屉原理,我们取\(1,4\)和\(2,3\)段时,必然会出现包含左侧最大值或右侧最大值的段。否则就是相交的情况,其实就是将四段变成三段或更少,也是满足条件的。

那么这样点对数就降到\(O(n\log n)\)。我们处理出这些点对。回答询问可以让询问离线,将询问和点对按左节点从小往大\从大往小排序,用BIT处理前缀和后缀max即可。具体实现看程序。(有点像扫描线,但这里空间有些大,开线段树很危险,只能用树状数组了)

https://codeforces.com/gym/102586/submission/168237465

这篇关于XX Open Cup, Grand Prix of Tokyo D,L的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!