T1

题意

有一个$1…n$的排列,现在给出$n$和一个正整数$k$,代表目标是原序列右移$k$次的结果(右移一位代表将当前的序列末尾插入头上,如$12345$右移两次是$45123$)你可以进行任意次操作,每次反转一个区间$[l,r]$,最终使得原序列变为目标序列.最小化操作次数并输出任意一组方案.

$0≤k<n≤100$

解法

事实上,这个题完全是结论题因为你可以发现,无论是什么样的情况,都只需要0或1或2或3次就搞定了.因为根本上,它的原始序列是$1…n$,所以右移后一定能分成至多两个有序的部分.

0:没有右移,不需要反转

1:$n=2$且$k=1$时

2:$k=n-1$或$k=1$时,只要先反转$1…n-1$或$2…n$,然后全局反转就可以了

3:其他情况,懒得讲了.

T2

题意

现在给出$n$个在$1…9$之间的正整数,你可以将它们任意排列组合,并分成$k$份,每份组成一个十进制数字.最小化这些数字的最大值.

$1≤k≤n≤100000,1≤t≤5$

解法

首先我们可以发现一些性质:

  1. 所有这些十进制数字都是按位递增的,也就是没有$54321$这种数
  2. 最大值的位数是$ceil(n/k)$位,而有些是$floor(n/k)$位.

我们可以把最大的数丢给位数少的数字.

T3

题意

给定一棵$n$个点的树,从中选出若干个点,使得任意选中的两点之间距离$\le k$,两点之间的距离定义为树上两点间简单路径经过的边数.询问有多少符合题意的选择方法.

$1≤n≤10000,1≤k≤min(500,n)$

解法

我们来考虑如何判断两点之间的距离是不是小于等于$k$.假设我们的两棵子树内的点已经都满足了.那么我们就需要判断子树间点的距离.我们记录离这个点最近的点

即设$f_{i,j}$表示以$i$为根的子树,子树内部已经满足条件了,选出的点中离$i$最近的点的距离为$j$的方案数.合并子树时要满足的条件是:子树间点的距离$>=k,j_1+j_2+2>=k$.新的$j=max(j_1,j_2)+1$

合并子树时,枚举$j_1,j_2$满足$j_1+j_2+2>=k$.$f_{x,max(j_1,j_2)+1}+=f_{c_1,j_1}×f_{c_2,j_2}$

——Gensokyo