NOIP模拟 22

　　剧情回放：xuefeng：考场上你们只打暴力不打正解，我不满意！

　　skyh：考场怒切T2以表明自己拥护xuefeng的决心

　　BoboTeacher：这场考试就没想让你们上100

　　神犇skyh：（笑而不语）

　　众蒟蒻：跪。

　　T1 数论

　　　　忘删调试信息跪了20。

　　　　正解运用了迭代收敛的思想..

　　　　首先$ d(x)=\pi (c_i +1) $表明$ d(x) $中各个质数的贡献是独立的

　　　　即：考虑了一部分质数之后，如果此时数x不优，那么将来加（乘）上其他质数相同的贡献之后仍然不优。

　　　　举例，$ d(x)=4,d(y)=5 $，那$ d(x)*2 $一定小于$ d(y)*2 $吧

　　　　所以分别考虑每个质数，具体做法：

　　　　　　0.开个数组$a$，初始只有一个数1.

　　　　　　1.进入迭代，枚举下一个质数$p$，用数组中每个数乘上它的次幂$p^c$塞到数组$b$，当然结果要在$M$以内

　　　　　　2.将b数组按原数大小排序，从头开始枚举，用堆维护已经枚举到的数中前$K+1$大的约数个数，如果大于堆内所有元素就抛弃，否则塞进$a$并更新堆

　　　　　　3.检测到$a$数组多次迭代没有变化，结束循环，否则返回1

　　　　Ps:1.这是分别考虑每个质数的贡献，拓展可能为优秀解的数来找到更多的可能优秀解

　　　　　 2.堆的使用是根据题目定义，直接去掉目前不优的数的策略具有正确性

　　　　　 3.由于加入大质数是非常不优的，所以可能枚举到很小的p就结束了

　　　神题。积累思想。

　　T2 位运算

　　　　天皇用脚切掉的题

　　　　首先注意到他只需要构！造！出！一！组！可！行！解！解没有限制，有就行

　　　　其次是否有解只与数中1的个数有关，和1的位置也无关。

　　　　所以可以dp判断有没有达到$cnt[c]$个1的可行解，然后疯狂构造就行

　　　　讨论，特判，考虑各种特殊情况，善用$min，max$。

　　T3 旅行

　　　　NC哥一眼艹掉的题

　　　　与其说是$DFS$，不如说是在$B$序列上$DP$,只不过是在树上转移罢了。

　　　　所以注定了$DFS$不再是板子..一切打板子的习惯都将被粉碎..

　　　　发现如果现在停一个点$B[id]$，且当前$DFS$序列与$B$的前$1~id$位全部匹配

　　　　若下一步走向点$t$且$t<B[id+1]$,那么可以确定此次$DFS$序列的字典序一定小于$B$序列

　　　　如果$t>B[id+1]$，则一定大于，不合法。

　　　　所以当$t!=B[id+1]$时，接下来的贡献都在这个地方解决了，不需要递归。

　　　　只有$t==B[id+1]$时，需要递归解决。

　　　　注意到当走完一个子树之后，可能目前的$DFS$序仍然与$B$匹配，还要重复执行这个过程。

　　　　所以$DFS$的主体是循环。

　　　　递归的过程，与其说是递归，不如说是状态的转移。

　　　　回溯的过程，与其说是回溯，不如说是回父亲找下一个状态。

　　　　根本不是搜索，不是换根树P，而是在树上转移的序列$DP$（胡绉）

　　　　每一次回到（或第一次到达）一个节点，都可以选择走序列的下一位（如果找的到的话）

　　　　或者走小于下一位的儿子。如果是后者，那么剩余的路径可以自由排列了。

　　　　注意，“剩余的路径”也是需要维护的。因为可能此时位置的其他儿子是之前走过的路径，是唯一确定的，不能参与排列。

　　　　注意，“剩余的路径”的总方案数很难确定。除了当前位置的儿子可以自由排列，排完之后父亲的儿子，爷爷的儿子，太爷的儿子...都解放了可以自由排列。

　　　　为了解决前者，对每个节点使用数据结构。观察到每个点对此贡献相同，只需维护个数。

　　　　为了解决后者，维护一个全局变量。观察到每从$a$走到$b$，只是让$a$处的阶乘降了一阶。又考虑到“剩余路径”的总方案是各个节点方案的乘积，不妨直接让全局变量除去$a$剩余儿子数，即可正确维护“剩余路径”的总方案。

　　　　考场上要大胆。

巴特西

NOIP模拟 22

最新文章

热门文章