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)