ZROI CSP-S失恋测(1)

传送门

写在前面：为了保护正睿题目版权，这里不放题面，只写题解。

“怎么大家一个暑假不见都变菜了啊。”——蔡老板

考虑一个\(nk^2\)的dp，按\(w_i\)排序，则每个组长只能匹配排在他前面的组员，每个组员也只能等待排在他后面的组长。

设\(f_{i,j,l}\)表示前\(i\)个人，配好了\(j\)对，有\(k\)个组员等待匹配的最优解，直接dp即可。

注意到\(2k>n\)时一定无解，因此\(O(nk^2)=O(nk\cdot\min(n,k))\leq O(nk\sqrt{nk})\)。

另外一种做法是状态中不记录配好了多少对，而是直接wqs二分出每配成一对减免的补偿值，使得最优情况下恰好配成\(k\)对，时间复杂度\(O(nk\log a)\)。

无论哪种方法都需要注意排序时\((p_i=)2<3<1\)。~~（否则就会wa飞）~~

比较显然的一点是行和列是独立的。可以分别哈希出每行、列代表的字符，从而算出按照行、列划分时的答案，相乘即可。

由回文串的性质可以证明（猜出），\([l,r]\)可能成为答案的充要条件是\([1,r]\)和\([l,n]\)均能成为答案。两种是对称的，分别计算即可。

用\(\text{manacher}\)（二分哈希）算出以每个空隙为对称中心的最长回文串，假设已经算出\(j\in[1,i-1]\)的每一个\([j,n]\)是否可行，\([i,n]\)可行的充要条件是存在一个可行的\([k,n]\)使得以\((i-1,i)\)为对称中心的最长回文串可以覆盖到\(k\)，显然这个\(k\)取合法的最大值最优。

两种部分分都很好做，维护一个懒标记即可。

考虑整体\(+1\)反映到二进制上的表现。设\(x\)的二进制位从低到高分别为\(a_0,a_1,…,a_{29}\)，则\(+1\)后的表现为：找到最低的\(i\)，使得\(a_0,a_1,…,a_{i-1}=1,a_i=0\)，将\(a_0,…,a_i\)全部翻转。

如果将每个数倒着插入trie中（即从低位到高位插入），那么每次都是交换一条从根到叶子的链的每个节点的左右儿子，根据异或懒标记决定这条链的走向即可。

巴特西

ZROI CSP-S失恋测(1)

最新文章

热门文章