0912模拟

0912模拟

T1题解:
对于一个已有的n的单峰排列,n+1只能放在n两边,所以就是ans[n-1]*2,所以就是ksm(2,n-1)

AC代码:

T2题解:
贪心搞最小生成树,很显然啊……

AC代码:

T3题解:
考试的时候写的贪心……
事实上我们会发现这是对于一个无向图中访问每一条边并只访问一次,也就是欧拉回路
然后我就学习了一下欧拉回路……

AC代码:

T4题解:
//对于每个点,我们有一个约数和,但会有很多对应的值,所以会想到是一颗树,其约数和是父亲
通过手动打表等我们会发现,所有素数被连向1
而其余符合条件的数的约数和被连向小于他的素数或另一个符合条件的数,也就是最终都回到了1
所以这构成了一棵树,而答案就是树的直径(边权为1) ,且一定经过根结点1

对于符合条件的数来说,sum[i]等价于其树中的父亲
简单的说,树的直径是其最长边和次长边的合,而一个节点的子树均又比他大的数组成,所以降序处理即可

AC代码:

0

发表评论

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