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:50] lak [李元恺] |
2020-2021:teams:acm_life_from_zero:5.09-5.15 [2020/05/15 22:49] (当前版本) kipple [袁熙] |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| 都是补比赛的题 | 都是补比赛的题 | ||
| - | 2018-2019ACM-ICPC，Asia Xuzhou Regional Contest L.Rikka with grid graphs | + | ==== Rikka with grid graphs ==== |
| + | |||
| + | [[https://codeforces.com/gym/102012/problem/L|题目链接]] | ||
| 分类：轮廓线dp、传递闭包 | 分类：轮廓线dp、传递闭包 | ||
| 行 23: | 行 26: | ||
| 网格图、连通性两个关键词提示轮廓线dp，观察一下性质发现没法用括号表示法，只能用传递闭包记录状态，跑一下可以发现单步有效状态数极限在1万左右，复杂度O(49*4*10000*36)如果是60组极限数据时间非常卡，但是好像默认多组数据的话不会都出极限数据？ | 网格图、连通性两个关键词提示轮廓线dp，观察一下性质发现没法用括号表示法，只能用传递闭包记录状态，跑一下可以发现单步有效状态数极限在1万左右，复杂度O(49*4*10000*36)如果是60组极限数据时间非常卡，但是好像默认多组数据的话不会都出极限数据？ | ||
| - | 2018-2019ACM-ICPC，Asia Xuzhou Regional Contest M.Rikka with Illuminations | + | ==== Rikka with Illuminations ==== |
| - | 题意：一个凸n边形，外面有m个灯塔，问最少需要多少个灯塔使多边形每条边都能被覆盖 | + | [[https://codeforces.com/gym/102012/problem/M|题目链接]] |
| - | 题解：n m都是1000，1000组数据，可以暴力过。暴力即通过叉积判断每条边和每个灯塔的照射关系，确定每个灯塔的范围，然后$m^2$dp一下。O(nlogn)做法：求凸多边形重心，然后得出边的极角范围，然后每个灯塔可以O(logn)求出和重心连线所经过的两条边，以这两条边为边界二分即可。后面dp部分先对每个点倍增一下，dp就可以O(nlogn) | + | 题意：一个凸n边形，外面有m个灯塔，问最少需要多少个灯塔使多边形每条边都能被覆盖和方案。 |
| + | |||
| + | 分类：计算几何、dp | ||
| + | |||
| + | 题解：n m都是1000，最多1000组数据，可以暴力过。暴力即通过叉积判断每条边和每个灯塔的照射关系，确定每个灯塔的范围，然后$m^2$dp一下。O(nlogn)做法：求凸多边形重心，然后得出边的极角范围，然后每个灯塔可以O(logn)求出和重心连线所经过的两条边，以这两条边为边界二分即可。后面dp部分先对每个点倍增一下，dp就可以O(nlogn) | ||
| ====== 姜维翰 ====== | ====== 姜维翰 ====== | ||
| 行 37: | 行 44: | ||
| ====== 袁熙 ====== | ====== 袁熙 ====== | ||
| + | |||
| ===== 专题 ===== | ===== 专题 ===== | ||
| 行 43: | 行 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，可以直接看cdq的ppt | + | 推荐插头dp，以便遇到问题可以及时跳过 |
| + | |||
| + | 可以插头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.1589539847.txt.gz · 最后更改: 2020/05/15 18:50 由 lak
