T1
最开始是爱丽丝尽量远离绿,绿去追爱丽丝,如果爱丽丝和绿初始位置距离小于等于 555 (不是 666 是因为爱丽丝先手,等绿出手会远离一格),那么等绿刷出来技能可以直接干掉爱丽丝,否则爱丽丝会干掉绿。
T2
一个区间如果纳入新的数,那么这个数有可能会成为这个区间最大值或最小值,那么肯定是不优的,所以只需要枚举每相邻的两个的差就可以了。
时间复杂度 O(n)O(n)O(n)
T3
分块,每个点如果块有标记则颜色为块的标记,没有则是原数组颜色,更新完整块直接给块打标记,非完整先下放标记,再暴力更新。
时间复杂度 O(qn)O(q \sqrt{n})O(qn ) 。
T4
定义状态 dpidp_idpi 为走到 iii 所需最小的步数,每一位可以从上一位走过来,即
dpi=dpi−1+1dp_i=dp_{i-1} + 1 dpi =dpi−1 +1
也可以从之前的位置跳跃而来,设 jjj 为蓄力的时间
dpi=min(dpi−j2+j+1)dp_i=\min(dp_{i-j^2}+j+1) dpi =min(dpi−j2 +j+1)
初始在 111 点
dp1=0dp_1=0 dp1 =0
时间复杂度 O(nn)O(n \sqrt{n})O(nn )
T5
感觉 T5 有问题啊,感觉我做法没啥问题,大家都 20 分,是都忽略啥了吗。
设 dpi,j,kdp_{i,j,k}dpi,j,k 为在第 kkk 秒走到点 (i,j)(i,j)(i,j) 的方案数,你可以从上一秒相邻安全的点转移。其中起点在第 000 秒为 111 ,答案是第 ttt 秒的终点。
时间复杂度 O(nmt)O(nmt)O(nmt)
非AC代码:
T6
设 fif_ifi 为以 iii 为根的子树魔法值之和,si,js_{i,j}si,j 为以 iii 为根的子树颜色为 jjj 结点总数,di,jd_{i,j}di,j 为如果 iii 的父亲结点颜色为 jjj,子树中所有颜色为 jjj 的结点与他相连能产生的除去这个父亲节点外能产生的魔法值。
对于每个结点:
sss 直接累加所有子树的每种颜色,最后在自己的颜色 +1+1+1。
ddd 也是直接累加,但对于自己的颜色,要额外加上那个子树的 sss,因为上面的点连接下面的点都会穿过他。
fff 先直接累加,对于与自己相连产生的贡献,就是那个子树与自己颜色相同的 d+sd + sd+s ,原因:累加 ddd 请看他的定义, sss 是因为还要算上当前结点产生的贡献。
然后考虑跨过当前结点产生的贡献,在每个子树内,其他子树所有颜色相同的节点都可以和自己的所有结点连接,设当前节点为 uuu,当前子树根结点为 vvv 贡献就是 dv(su−sv)d_v(s_u-s_v)dv (su −sv ) ,对于每种颜色都要统计。还要额外颜色与当前结点相同时跨过当前结点产生的贡献。
时间复杂度 O(nc)O(nc)O(nc)