Hdu暑期多校训练4

来自PC Wiki
跳到导航 跳到搜索

Records

[Contest]

Solutions

A

考虑以$$1$$为根,剩下点找父亲

然后就是偶数点以$$1$$为父亲

奇数点以最低一位为$$0$$的,把他变成$$1$$当作父亲;如果不存在就以$$1$$为父亲

B

C

$$n$$为偶,$$\frac{n}{k}$$为偶的时候对称着取即可

$$n$$为偶,$$\frac{n}{k}$$为奇的时候从和可以判断无解

$$n$$为奇,$$\frac{n}{k}$$为奇的时候是本题的难点:

考虑$$\frac{n}{k}=1$$特判,那么$$\frac{n}{k} \geq 3$$

这种情况我们单独构造前三列,后面转化为偶数的情况

前三列可以这么构造:

第一列 $$1 , 2 , 3 , 4 , 5 , … , k$$

第二列 $$\frac{k+1}{2}+1 , \frac{k+1}{2}+2 , … , k , 1 , 2 , … , \frac{k+1}{2}$$

第三列拿总和减一下就行了

D

E

考虑直接状态压缩每个数字模3的余数,然后做数位DP.

因为长度高达$$10^{18}$$,我们可以预处理$$2$$的幂次的结果,然后每次查询做合并.

如果首位不能为0,一种方案是做$$N - 1$$位的DP,再与不含$$0$$的一位做合并;另一种方案是简单容斥,即总方案减去$$N - 1$$位,$$0$$的个数为$$3k + 2$$的情况的方案数.

现在唯一难点在于合并,共有$$3^8$$个状态,如果直接合并复杂度就炸了,观察形式可以发现这是三进制异或卷积,我们直接动用$$K$$进制异或卷积即可.

F

考虑如果没有吃树和恢复,那么答案是$$-h_1-(h_1+h_2)-(h_1+h_2+h_3)-……-(h_1+h_2+……+h_n)$$

然后我们考虑吃树对答案的贡献是$$Ans_1 = \sum {h_{pos}*(n-h_{pos}+1)}$$

然后考虑每次休息,可以看作把$$h$$的前缀和分$$k+1$$段,然后变成每段$$[L,R]$$是$$h_L+(h_L+h_{L+1})+……+(h_L+h_{L+1}+……+h_R)$$,$$Ans_2$$是这些段的贡献和

这样休息对答案的贡献就和吃树的独立了,可以分别计算

吃树的直接对$${h_i*(n-h_i+1)}$$排个序然后取前$$m$$项

休息的部分考虑DP,设$$s$$为$$h$$的前缀和,$$ss$$为$$s$$的前缀和

然后$$dp[i][k] = min (dp[j][k-1]+ss_i-ss_j-s_j*(i-j))$$

这个式子满足决策单调性,可以用经典的单调栈优化决策单调性DP的方法来优化

复杂度$$O(T(n \log n + m + kn \log n))$$

G

15数码的解最多80步,因此只需要判断是否有解即可

对于$$N$$数码问题,可以利用以下方法判断他是否有解:

当$$N$$为奇数时逆序对数奇偶同性可互达,$$N$$为偶数时,逆序对数加上空格所在行距目标空格行的距离要和终点状态逆序数同奇偶则可以互达

(其中计算逆序对数的时候不算入0)

H

二分答案+主席树check

I

J

考虑大约$$(4 * 10^3)^5 > 10^{18}$$,因此我们可以暴力算出$$4 * 10^3$$以内的素数,这样可以把答案大于等于$$5$$的情况考虑完毕.

接下来分别对答案可能为$$4, 3, 2, 1$$的情况考虑即可,直接暴力测试.