JOISC 2023 D2T2 Council
注意到,钦定一个人为主席后,对于此时得票数大于 \(\lfloor \frac{n}{2} \rfloor\) 的议案,不管怎么选副主席,均能通过;对于此时得票数小于 \(\lfloor \frac{n}{2} \rfloor\) 的议案,不管怎么选副主席,均不能通过。所以需要考虑的只有此时得票数恰好等于 \(\lfloor \frac{n}{2} \rfloor\) 的议案。
记 \(S_i\) 为:钦定 \(i\) 为主席后,得票数等于 \(\lfloor \frac{n}{2} \rfloor\) 的议案集合。记 \(T_i\) 为 \(i\) 的投票状态取反后的状态。记 \(base_i\) 为:钦定 \(i\) 为主席后,此时得票数大于 \(\lfloor \frac{n}{2} \rfloor\) 的议案的个数。那么对于 \(i\) 的答案,形式化表述即为:
\(base_i+\max_{T_j \bigcap S_i} \mid T_j \bigcap S_i \mid\)
这是一个我们熟知的高维前缀 \(\max\) 的形式。但是我们还要对 \(T_j\) 这个条件进行限制,所以不能直接做高维前缀 \(\max\)。接下来考虑如何处理这个限制:注意到,\(T_j\) 是 \(T_j \bigcap S_i\) 的超集,而 \(T_j \bigcap S_i\) 又是 \(S_i\) 的子集。那么,我们可以先以 \(T_j\) 为基础做一遍高维后缀 \(\max\)(即超集 \(\max\)),再做一遍高维前缀 \(\max\) 即可。这样就能保证枚举到的集合同时满足是 \(S_i\) 和 \(T_j\) 的子集这两个条件,因此是合法的。
因为本题还要求主席与副主席的编号不同,所以在转移的时候,不仅要维护最大值和最大值编号,还要维护次大值及其编号。写起来有点令人暴躁。
ARC 100 E - Or Plus Max
先写上一题再写这一题,简直是不要太容易。
标签:lfloor,frac,max,rfloor,SOS,得票数,DP,高维 From: https://www.cnblogs.com/Day0/p/18095247