Algorithms&Data Structures

智算之道高校组复赛集锦

还是太菜了啊,120名GG,D题想了一个多小时影响了后面题思考时间,中间过程还需反思,先把做题时的思考过程记录一下,题解等后续补题后再完善

A 数字

100分,直接100~999暴力枚举即可

B 网格

100分,这题卡了一小会,一开始想的是贪心地走魔法格子,把贪心的判断条件写错了,后来发现贪心并不是最优解,我们需要的是全局最优,也就是针对一个序列,选择最长上升子序列,因为k值最大是2000,直接上n^2的DP即可

C 有向无环图

60分,直接枚举构造,不牵扯边之间的复用,后续补题解

UPD.其实是一道水题啊→_→,考场上手玩5个点数错数了,要不然肯定能想到2^{n-i}规律的

我们发现每个点往后面点连的时候,假如所有有向无环图全部边都连接,设除了1和n以外的所有中间点的个数为x,则最终路径数为2^x,通过手玩我们可以找到每个中间点对答案的贡献,故我们可以根据k的二进制来决定每个中间点是否向n连边,另外k的范围应该在unsigned long long范围内,会爆long long

D 分数

100分,其实一开始思路没有错只是没有想得太全面,O(n)的欧拉筛筛素数,然后分情况讨论,任意整数可被质因数唯一分解,我们手玩前20个数发现,像16这种分解出来是2^4这种,在筛的时候循环首先是在i循环到8时,prime[j]为2的时候把16这个合数筛掉的,然而在8时的q为2,说明还需要乘以2,我们可以得到结论如果除以最小质因子的q值等于该最小质因子而不为1时说明我们这里的q值也为该最小质因子,这是特殊的情况,另外平方数的q值也是最小质因子,除了以上两种情况如果合数能够表示为两个质因子的乘积的形式,说明这里q值为1,最后直接统计答案即可,时间复杂度O(n)

E 树数数

20分暴力,后续补题解

 

发表评论

邮箱地址不会被公开。 必填项已用*标注