Gym 101620 题解

A

模拟。

F

特判掉 n\ge 2pn\ge p,枚举替换哪个数。

G

期望大的只向期望小的走,所以跑 dijkstra 即可。

H

每个目录建个 Trie 跑大暴力。(貌似直接暴力也行

J

枚举块的大小 d,若子树大小为 d 的倍数的有至少 n/d 个那么合法。

L

正着和斜着各弄一个前缀和优化。


B

从上往下扫,用一个 set 维护可以对每个点求出直接控制它的矩形是哪个,同时对每个矩形求出直接包含它的矩形是哪个。

按时间倒序处理矩形,每次把这个矩形的答案合并到父亲上,用并查集维护。

C

手玩几层的答案发现答案子树的形态只有两种,可以把一个问题左右两半划成子树上的问题,并且答案是 Ax+B 的形式。

F(k,start,len,step,0/1) 表示层数为 k,等差数列为 [start,len,step],且指定了树形态的一个子树的答案系数 A,B

对于层数 k \le 15 的时候,可以把无法继续延申的等差数列的答案记忆化下来。

D

首先预处理出第一列每个点走一圈以后走到第一列哪个点。询问的时候先暴力跳到第一列,然后在第一列上找环,最后再暴力跳出来。

修改的时候考虑向前推哪些点走到它,可以发现是一个区间,暴力向前维护。注意值修改以后上下 5 个点都会受影响。

E

细节超多的一个 DP。

先预处理链的答案,和一段链固定开头结尾的答案。

f_i 表示 i 放左上角的子树答案,g_{i,j} 表示 (1,2)i(2,1)j 的答案。

如果 i 下面是链,直接求答案。

如果 i 有两个儿子 x,yf_i=g_{x,y}+g_{y,x}

如果 i 只有一个儿子而且不是链,就分类大讨论一下,设 i 向下第一个分岔点是 x

* - * - * - *
            |   ^
     <- b - x - a ->
f[i] = LeftChain * f[a]  (b is chain)

* - * - * - x - a ->
            |
            b ->
f[i] = g[a,b]

* - * - * - x - a ->
            |   v
         <- b
f[i] = LeftChain * f[a] (b is chain)

* - * - * - x - a - w ->
            |
     <- u - b - v ->
f[i] = LeftChain * g[w,v] (u is chain)

g_{i,j} 就先看 i,j 哪个比较短,短的必须是一条链,长的就是向下跳若干步求一个 f

I

考虑相邻的两个位置都被选了,那么这两个值之间的值也要选,相当于选一个位置对就必须选一个区间内所有的位置对。

可以用线段树优化建边,也可以预处理值域和下标的区间最小最大值,把上面的扩展过程重复 O\left(\log(n)\right) 次。

K

先去掉全一样的,求出最优位置做一个差分,那么修改等价于一个数 -a 一个数 +a,相当于把数分成尽可能多的和为 0 的组。

0 的答案和 x+y=7 的答案先直接加上,对剩下的三个数做一个 O(n^3)​ DP 即可。

发表评论

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