警示:看到一道做过的题不要着急上头去写,写炸了心态就崩了。
T1
题意:
有 \(n\) 个人,每个人有经验 \(w_i\)、薪水 \(s_i\)、意愿 \(p_i\) 三个属性。要选出 \(2k\) 个人组成 \(k\) 组,每组两个人。每个组内一人做组长,一人做组员。要求组长经验 \(\ge\) 组员。
每个人可能有三种意愿:组员、组长或者都行。选择人必须根据他的意愿来选。
问能否选出 \(k\) 个组;如果能,最小薪水总和是多少。
\(n\cdot k\le 10^5\)。
首先 \(k>[n/2]\) 肯定没法选出来,直接特判 \(-1\)。
于是 \(10^5\ge n\cdot k\ge 2k^2\),可以得到 \(k\le \dfrac{\sqrt {10^5}}{2}\),也就是 \(O(nk^2)\) 是可行的。
观察到如果人员是按工作经验从小到大排序选择,那么后选择的组长的待选组员集合肯定包含前选择的组长;也就是前面选的组长选了组员,不会影响后面组长选组员。这是无后效性,启发我们动态规划。
一个想法就是 \(dp[i][j][k]\) 表示前 \(i\) 个人有 \(j\) 组,多余 \(k\) 个组员的最小薪水和。转移比较显然。
但是如果只按照工作经验排序无法通过,因为在相同的工作经验人员内部,DP 时必须先遍历到组员,再遍历到组长才行,不然有可能最优解是在这个相同工作经验人员内部选了几组,无法覆盖到这个可能性。
所以排序时按照组员、全能、组长的意愿排序即可。
坑点:sort 的 cmp 函数必须是 \(<\) 而不是 \(\le\)。
T2
原题,做法在动态规划合集的 BoardFolding 处。
T3
维护一个数据结构,支持加数、删数、全体 \(+1\)、全体异或 \(x\)。
显然是 \(01\) Trie。维护前三个操作是很简单的,考虑异或操作对 \(+1\) 操作的影响。
维护一个数 \(tag\),表示此时 Trie 里的所有数,要异或 \(tag\) 后才是真实值。
原本 \(+1\) 操作是沿着 \((111\dots 1)_2\) 的边走,然后把路径上的点交换左右儿子;但是现在多了一个 \(tag\),也就是在 Trie 里 \(\bigoplus tag=(111\dots 1)_2\) 才是真正要进位的数。
所以沿着 \((111\dots 1)_2\bigoplus tag\) 的路径走一遍,交换儿子即可。
标签:NOIP,组长,ge,tag,111,组员,排序,模拟 From: https://www.cnblogs.com/FLY-lai/p/18415151