前言
康复训练Day2。wdnmd又双叒叕是赛后1A。
题解
A - p-binary
考虑是否存在使得能被表示成个之和,即二进制表示中的个数小于等于且本身大于等于。暴力枚举就行辣。
B - Power Products
用一个长度为的记录每个数小于的质因子的次数对取模的情况,并根据剩余的最大质因子存放到对应的中,对每个数求一个补集然后查询补集出现次数就好了。
C - Rock Is Push
假设没有石头。
记为在这个位置先向下走走到的方案数,为在这个位置先向右走到的方案数。
那么显然有转移方程还有。
分析发现被推过去的石头并不影响转弯之后的走法,只影响能沿着推石头的方向走多远,即状态转移的范围。
如果下边有个石头,则有,同理,如果右边有个石头,则有。
只有一行或一列或是石头的时候要特判一下。
D - Tree Factory
每次操作能把一部分节点的深度-1,那么肯定是每次操作都尽可能影响多的节点比较好。
考虑按照dfs序来安置节点,贪心地优先安置高度低的子树,回溯的时候把剩余的一整条链往上提。