2020-2021:teams:acm_life_from_zero:5.09-5.15
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:acm_life_from_zero:5.09-5.15 [2020/05/15 18:55] lak [李元恺] |
2020-2021:teams:acm_life_from_zero:5.09-5.15 [2020/05/15 22:49] (当前版本) kipple [袁熙] |
||
|---|---|---|---|
| 行 44: | 行 44: | ||
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| + | |||
| ===== 专题 ===== | ===== 专题 ===== | ||
| 行 50: | 行 51: | ||
| 没有比赛 | 没有比赛 | ||
| ===== 题目 ===== | ===== 题目 ===== | ||
| + | ==== C Rikka with Consistency==== | ||
| + | 题意：在0-n上的整数坐标上,有n+1个点在高度$a_0,..,a_n$形成折线，有两人分别从(0,0),(n,0)出发，保持相同高度沿这些折线移动，最终到达(n,0),(0,0)，求这个过程需要走的最小长度。500组数据，$n,a_i≤50$\\ | ||
| + | 分类：dp\\ | ||
| + | 思路：dp，记x,y,h表示从0出发的人位于区间[x,x+1],从n出发的人位于区间[y,y+1],高度为h的状态，转移时考虑相邻的x,y和高度差为1的状态转移,复杂度O($hn^2$)\\ | ||
| + | [[http://codeforces.com/gym/102012/problem/C|题目链接]]\\ | ||
| + | === K Rikka with Ants === | ||
| + | 题意：n个点形成的环，两只队伍从$s1,s2$到$e1,e2$,路径长度为路径边权和（两支队伍共同走的边长度视为原来的3倍）。求纳什均衡时两队各走的路径长度（如果存在混合纳什均衡优先输出混合纳什均衡结果），5000组数据，n和边权≤50\\ | ||
| + | 分类：博弈-纳什均衡\\ | ||
| + | 题解：大概是纳什均衡的裸题。算一下两队两种选择形成的4个结果，再用来检查是否存在混合纳什均衡后，输出题目要求的解，复杂度O(n)。\\ | ||
| + | [[http://codeforces.com/gym/102012/problem/K|题目链接]] | ||
| ====== 本周推荐 ====== | ====== 本周推荐 ====== | ||
| ===== 李元恺 ===== | ===== 李元恺 ===== | ||
| - | 推荐插头dp，和斯坦纳树，以便遇到问题可以及时跳过 | + | 推荐插头dp，以便遇到问题可以及时跳过 |
| 可以插头dp建议直接看看cdq的ppt | 可以插头dp建议直接看看cdq的ppt | ||
| + | |||
| [[https://wenku.baidu.com/view/3e90d32b453610661ed9f4bd.html|链接]] | [[https://wenku.baidu.com/view/3e90d32b453610661ed9f4bd.html|链接]] | ||
| ===== 姜维翰 ===== | ===== 姜维翰 ===== | ||
| ===== 袁熙 ===== | ===== 袁熙 ===== | ||
| + | CF1299D 线性基[[http://codeforces.com/contest/1299/problem/D|题目链接]] | ||
2020-2021/teams/acm_life_from_zero/5.09-5.15.1589540125.txt.gz · 最后更改: 2020/05/15 18:55 由 lak
