2020-2021:teams:intrepidsword:2020.05.08-2020.05.14_周报
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020.05.08-2020.05.14_周报 [2020/05/16 21:47] chielo 创建 |
2020-2021:teams:intrepidsword:2020.05.08-2020.05.14_周报 [2020/05/17 21:44] (当前版本) toxel [zzh] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ===== 团队 ===== | ===== 团队 ===== | ||
| - | TODO | + | 2020.05.10: [[2019-hdu-multi-u-1|2019 Multi-University Training Contest 1]] ''pro: 8/9/13'' ''rk: 15/1105'' |
| ===== 个人 ===== | ===== 个人 ===== | ||
| ==== zzh ==== | ==== zzh ==== | ||
| + | |||
| + | 2020.05.12 [[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_641_div._1|Codeforces Round 641 (Div. 1)]] ''pro:4/7'' | ||
| ==== pmxm ==== | ==== pmxm ==== | ||
| 行 14: | 行 16: | ||
| * 5/10 - Codeforces Round #641 (Div. 1): ''pro: 2/3/7'' ''rk: 932/1213'' | * 5/10 - Codeforces Round #641 (Div. 1): ''pro: 2/3/7'' ''rk: 932/1213'' | ||
| * 5/14 - Codeforces Round #642 (Div. 3): ''pro: 6/6/6'' ''rk: 170/16950'' | * 5/14 - Codeforces Round #642 (Div. 3): ''pro: 6/6/6'' ''rk: 170/16950'' | ||
| - | * 5/15 - Codeforces Round #319 (Div. 1): ''pro: 3/5'' (vp) | ||
| + | 详细：[[.:jiangshenghu:2020.05.08-2020.05.14 周报]] | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| 行 21: | 行 23: | ||
| ==== zzh ==== | ==== zzh ==== | ||
| + | [[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_432_div._1#f_rainbow_balls|Codeforces Round 432 (Div. 1): F. Rainbow Balls]] | ||
| + | |||
| + | [[2020-2021:teams:intrepidsword:zhongzihao:codeforces_round_641_div._1#d_slime_and_biscuits|Codeforces Round 641 (Div. 1): D. Slime and Biscuits]] | ||
| + | |||
| + | 都是比较有趣的一维随机游走题，虽然出题人/验题人把它放在 D 不知道是在想啥 | ||
| ==== pmxm ==== | ==== pmxm ==== | ||
| ==== jsh ==== | ==== jsh ==== | ||
| + | |||
| + | === 牛客练习赛63 - F - 牛牛的树行棋 === | ||
| + | |||
| + | [[https://ac.nowcoder.com/acm/contest/5531/F|题目链接]] | ||
| + | |||
| + | == 题意 == | ||
| + | |||
| + | 一棵以 1 为根的树，树上每个节点都有一个棋子，两人轮流进行如下操作： | ||
| + | * 选择某个不在叶子上的棋子 | ||
| + | * 将棋子移动到所在子树的任意某个节点上（除了棋子当前所在的节点） | ||
| + | 轮流操作的过程中，节点上可以有多个棋子。 | ||
| + | |||
| + | 询问先手是否能够必胜，同时，先手必胜的前提下，输出先手的第一步操作有多少种。 | ||
| + | |||
| + | == 题解 == | ||
| + | |||
| + | > 博弈论+树上的数据结构 | ||
| + | |||
| + | 容易发现对于每个棋子的游戏过程，都是独立、互不影响的组合游戏。 | ||
| + | 由于是两个人轮流进行的多个游戏，我们只需要获得每个棋子对应的游戏的 SG，异或起来即为题目给定游戏的 SG。 | ||
| + | |||
| + | 对于一个棋子的游戏，子树除了自己的所有结点都能移动，容易得知 SG 即为子树的高度（离子树的根最远的节点的距离）。 | ||
| + | |||
| + | 这样我们就能得到当前游戏的 SG，答案的第一步就有了。 | ||
| + | |||
| + | 对于必胜前提下，先手的第一步操作，必然是要走到 SG 为 $0$ 的情况。 | ||
| + | 记当前游戏的 SG 为 $g$。 | ||
| + | |||
| + | 对于节点 $u$ 为根的子树，记它的高度为 $h_u$。 | ||
| + | 那么第一步如果是挪动 $u$ 节点上面的棋子，必然是要挪动到子树中高度为 $g \oplus h_u$ 的节点。 | ||
| + | 只有这样才能使后手的局面的 SG 为 $0$。 | ||
| + | |||
| + | 对于快速地计算上面说的点对数量，我的做法是启发式合并（dsu on tree）。 | ||
| + | 以高度为 key，维护当前子树中，对应高度的节点的数量， | ||
| + | 对每个结点算一下就行了。 | ||
2020-2021/teams/intrepidsword/2020.05.08-2020.05.14_周报.1589636827.txt.gz · 最后更改: 2020/05/16 21:47 由 chielo
