XIX Open Cup named after E.V. Pankratiev. Grand Prix of Peterhof, Division 1.

Problem A

Solved by Xiejiadong. 0:13 (+)

题意：给出在三角形的网格中走过的路径，要求回去。

题解：倒着还原回去。

考虑如果之前走了一步 $l$ ，可以通过走五次 $l$ 回去； 之前走了一步 $r$ ，可以通过走五次 $r$ 回去，而如果走了 $b$ 的话，直接 $b$ 就回去了。

Problem B

Unsolved.

Problem C

Solved by Weaver_zhu. 4:10 (+3)

Problem D

Unsolved.

Problem E

Solved by Kilo_5723. 0:23 (+1)

Problem F

Solved by Kilo_5723. 0:11 (+)

Problem G

Solved by Xiejiadong. 1:20 (+3)

题意：先手可以每次标记一个叶子结点，后手一开始在根结点，每次可以走到一个相邻的结点或者不走，如果后手走到了一个没有被标记过的叶子结点，那么后手就赢了，否则先手赢，如果先手赢的话，需要给出一个先手一开始标记的点。

题解：考虑当后手位于一个结点的时候，先手至少已经标记了多少的点。

显然当后手维护叶子结点的时候，至少已经标记了一个。

而位于其他结点的时候，显然就是孩子中需要至少标记的数量 $-1$ ，因为还有一步多余。

即用 $f[x]$ 表示到 $x$ 结点至少已经标记的点数的话，如果 $x$ 是叶结点的话， $f[x]=1$ ，否则 $f[x]=max(0,\sum _{y\in child\{x\}}f[y]-1)$ 。

Problem H

Solvde by Xiejiadong. 0:30 (+2)

题意：每次猜一个数，你需要告诉他是小了还是大了。要符合逻辑，至少 $30$ 次才能猜出。

题解：显然，对于当前的区间 $[L,R]$ ，如果他猜了 $x$ ，那么显然选择区间 $[l,x-1]$ 和 $[x+1,r]$ 中较大的一个区间即可。

Problem I

Solved by Xiejiadong. 0:59 (+1)

题意：每次一个将一个数 $+1$ ，或者 $/2$ （本身能被 $2$ 整除） ，或者 $/3$ （本身能被 $3$ 整除），要求最小化 $+1$ 的次数，让这个数变成 $1$ 。

题解：跑边权为 $0$ 或者 $1$ 的最短路即可。用优先队列维护，相当于就是 bfs 了。

Problem J

Solved by Weaver_zhu. 0:40 (+)

Problem K

Solved by Kilo_5723. 1:42 (+4)