2021.02.27【NOIP提高B组】模拟 总结

第一题：把所有质数找出来，然后两两乘一下，用前缀和即可。欧拉筛：设当前第 j j j个质数为 p j p_j pj​，则当 i ≡ 0 ( m o d    p j ) i\equiv 0(\mod p_j) i≡0(modpj​)时，就不用再筛了。原因： i p j + 1 ≡ 0 ( m o d    p j ) ip_{j+1}\equiv0(\mod p_j) ipj+1​≡0(modpj​)，所以这个数在用 p j p_j pj​筛时就已经被筛了。因为每个数被筛一次，所以时间 O ( n ) O(n) O(n)。

第二题：一个贪心：任意相邻的两个企鹅匹配是最优的。所以我们先求出最多能有多少个组匹配，假设为 x x x，如果 2 x ≥ k 2x\geq k 2x≥k，说明我们直接放就行了，答案为 ⌈ k 2 ⌉ \lceil\frac k 2\rceil ⌈2k​⌉。否则我们就把剩下的继续放，就是 x + ( k − 2 x ) x+(k-2x) x+(k−2x)。匹配的求法：可以贪心，从下往上，遇到没有匹配的就直接匹配；也可以动态规划，设 f i , 0 / 1 f_{i,0/1} fi,0/1​分别表示当前子树的答案（这个节点选还是不选）。转移的话也是没有匹配就匹配。

实话说这道题目考察了动态规划和贪心。

第三题：状压一下，跑一遍搜索或者 S P F A SPFA SPFA。时间是一样的。

第四题：有一个贪心：从小到大遍历，我们从左到右找到一合法位置，从右到左找到一个合法位置（合法位置指的是满足是第 b + 1 b+1 b+1个空位，因为空位的都是比它大的，空位没放）。然后看一看哪个比较小即可。用数据结构优化，因为空位个数是递增的，所以二分就行了。因为要查询加二分，所以大概就是 O ( n ( log ⁡ 2 n ) 2 O(n(\log_2^n)^2 O(n(log2n​)2。

这一题这个贪心思路要仔细想一想。