2020-2021:teams:mian:hdu_training:2016_multi-university_training_contest_1
目录
2016 Multi-University Training Contest 1
Results
Summary
- Solved 6 out of 11 problems
- Rank 27/532 in official records
- Solved 6 out of 11 afterwards
Virtual Participation
| # | = | Penalty | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 33 | 6 | 1223 20:23:41 |
00:43:29 (-1) |
04:32:18 (-3) |
(-1) |
02:03:26 (-1) |
02:34:44 (-4) |
04:28:51 |
03:00:53 |
Submit Distribution in Members
| Solved | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Pantw | √ | √ | |||||||||
| Withinlover | √ | ○ | √ | √ | |||||||
| Gary | √ |
(√ for solved during VP, ○ for after VP, - for tried but not solved)
Solutions
A: Abandoned country
- Solved by Pantw
题意
给一个边权两两不同的无向图。求最小生成树，以及最小生成树中使得所有点对最短路平均值的最小值。
$n\le 10^5, m\le 10^6$。
解法
由于边权不同我们可以直接知道最小生成树是唯一的，那么求出来之后 DP 一下即可。
B: Chess
- Idea by Pantw, Withinlover, Gary
- Debug by Pantw, Withinlover, Gary
- Code by Pantw
题意
$n\times 20$ 的棋盘，有若干相同的棋子，每个格子上至多有一个棋子，移动方式是：
- 若一个棋子右边是空格子，那么它可以移动到该格子；
- 若一个棋子隔着连续的一堆棋子，那么它可以跳过这些棋子，达到右边的第一个空格。
- 棋子不能超出右边界。
给定初始状态，问先手必胜还是先手必败。
解法
由于 $20\times 2^{20}$ 不大，可以直接预处理出 SG 函数值。
然后就是经典的 Nim 游戏了。
C: Game
题意
解法
D: GCD
题意
解法
E: Necklace
题意
解法
F: PowMod
题意
解法
G: Rigid Frameworks
题意
解法
H: Shell Necklace
题意
解法
I: Solid Dominoes Tilings
题意
解法
J: Subway
题意
解法
K: tetrahedron
题意
解法
Timeline
| Time | Action |
|---|---|
| 0 | Start |
| 300 | End |
Reflections
2020-2021/teams/mian/hdu_training/2016_multi-university_training_contest_1.1590328901.txt.gz · 最后更改: 2020/05/24 22:01 由 withinlover
