ZR8.31
题目链接:http://www.zhengruioi.com/contest/388
版权原因,不放题面
A
首先,排序肯定要根据工作经验排序,因为这样便于选择
之后,如果两个人工作经验相同,要尽量把只能当组员的放在前面
都可以的次之,只能当组长的放在最后
我们设(f_{i,j,k})表示前(i)个人选择了(j)个组长,(k)个组员的方案数
转移的话就看看这个人当什么就可以了
但是要保证组员的人数时刻大于组长的人数
因为我们让组长去选择组员就能够保证满足工作经验的条件
我的错误:转移的过程中组员0不能从-1转移过来
至于时间复杂度
首先$ k imes 2 > n $肯定无解
因为保证
(n imes k <= 10^5)
(k)的最大值也只不过(sqrt {50000})
所以时间复杂度为
(n imes k imes k)
可以通过本题
听说可以wqs二分优化,Orz suwakow神仙
B
首先可以发现,横竖互不影响,折纸可以变成裁纸
所以方案数= 横着的方案数 * 竖着的方案数
由于计算单个方向的方案数的时候
另一个方向长度始终不会改变
所以二维的矩阵就可以通过(hash)压成一个维度
近下来想一维的问题该如何解决
由于两个方案不同当且仅当最后剩下的区间在原数组的位置不同
所以就变成了能否通过一些操作
使得最后数组中只有([l,r])
也就是说([l,n]),([1,r])要满足条件
这两个问题本质是相同的问题,我们只考虑第一个
我们设上一次折的位置是(j)
那么(i)这个位置合法
当且仅当
以(i -0.5)为中心的极长回文子串包含了(j)
由于本来没有(i - 0.5)这种下标,同一左移或者右移去表示,这个细节还是挺要命的
对于一个(i),如果存在一个可以折叠的位置(j,(j < i))
使得
(len_i)就是以(i)为中心的极长子串的长度
那么(i)便是合法的,很明显,我们只需要维护最大的(j)即可
最后前缀和维护左向右的答案
第二遍统计([r,n])的时候统计答案即可
C
神仙(01)Trie
首先,插入删除
这个东西(01)Trie是可以完成的
将下来想,怎么满足+1
一个数(x)变为((x + 1) mod 2^{30})次方的本质
是找到最小的一个二进制位(i)使得(a_i = 0)且(a_{1dots i -1} = 1)
然后把(a_{1dots i})全部取反
取反操作在Trie树上对应的就是交换左右儿子
我们要从低位向高位建Trie树
因为这样所有的应该被反转的链和子树都一定在一条链上
所以单词时间复杂度为(log_n)
异或操作就打(tag)把
注意打(tag)后要反转的链不一定是全(1)链了,而应该是全(1)异或tag之后的对应值
另外第一股不满足条件的也是要反转的