2020-2021:teams:too_low:0725-0731
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:too_low:0725-0731 [2020/07/31 18:13] jim [比赛] |
2020-2021:teams:too_low:0725-0731 [2020/08/02 11:27] (当前版本) dragonylee |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| * [[https://blog.csdn.net/dragonylee/article/details/107707121|Codeforces Round #660 (Div. 2)]] ''%%pro: 4/4/5%%'' ''%%rk: 963/18771%%'' | * [[https://blog.csdn.net/dragonylee/article/details/107707121|Codeforces Round #660 (Div. 2)]] ''%%pro: 4/4/5%%'' ''%%rk: 963/18771%%'' | ||
| - | * [[https://blog.csdn.net/dragonylee/article/details/107711732|M-SOLUTIONS Programming Contest 2020]] ''%%pro: 6/6%%'' ''%%rk: NaN%%'' | + | * [[https://blog.csdn.net/dragonylee/article/details/107711732|M-SOLUTIONS Programming Contest 2020]] ''%%pro: 6/6%%'' ''%%rk: NaN%%'' **FINISHED** |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 50: | 行 50: | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| - | * [[2020-2021:teams:too_low:cf659_hj|cf 659]] ''%%pro: 2/4/7%%'' ''%%rank 2380/10822%%'' | + | * [[2020-2021:teams:too_low:cf659_hj|Codeforces Round #659 (Div. 2)]] ''%%pro: 2/4/7%%'' ''%%rank 2380/10822%%'' |
| - | * [[2020-2021:teams:too_low:cfedu92hj|cf edu 92]] ''%%pro: 4/4/7%%'' ''%%rank 989/13827%%'' | + | * [[2020-2021:teams:too_low:cfedu92hj|Educational Codeforces Round 92]] ''%%pro: 4/4/7%%'' ''%%rank 989/13827%%'' |
| ==== 题目 ==== | ==== 题目 ==== | ||
| 行 72: | 行 72: | ||
| ==== 胡琎 ==== | ==== 胡琎 ==== | ||
| - | [[https://blog.csdn.net/dragonylee/article/details/107706437|一般图最大匹配的一些总结]] | + | CF 659 B2 Koa and the Beach (Hard Version) |
| + | [[https://codeforces.com/contest/1384/problem/B2]] | ||
| + | |||
| + | |||
| + | ** 题意 ** 需要从海滩游到海岛上，给定初始时波浪高度等于0时的水深分布，波浪高度在0-k-0-k之间连续变动，已知最深能够游的水深D，求是否可以游到小岛 | ||
| + | |||
| + | ** 题解 ** 设波浪高度为k-0-k，维护到达位置i时，可能的波浪时间范围[l, r]。位置i+1时，波浪的范围为[l+1, r+1]和 [k - (D - d[i]), k + (D - d[i])]的交，如果长度为0则不可游到。特别的，如果D大于d[i]+k则时间范围为[0,2k-1]，即整个长度 | ||
| + | |||
| + | 特别要注意D - d[i]小于0的情况。这里pretest没有测结果B2 System test的时候WA了 | ||
| + | |||
| + | ** Tag ** dp | ||
| + | |||
| + | ** Comment ** 这道题需要基于位置思考，而不是基于时间思考，因为波浪的变化是周期性有规律的，便于处理，而水深的变化是任意的。 | ||
| + | |||
| + | <hidden> | ||
| + | <code cpp> | ||
| + | |||
| + | #include <bits/stdc++.h> | ||
| + | |||
| + | using namespace std; | ||
| + | |||
| + | |||
| + | int d[300005]; | ||
| + | int main(){ | ||
| + | int t = 0; | ||
| + | cin>>t; | ||
| + | while(t--){ | ||
| + | int n, k, l; | ||
| + | cin>>n>>k>>l; | ||
| + | |||
| + | for (int i = 1; i <= n; ++i) { | ||
| + | cin>>d[i]; | ||
| + | } | ||
| + | |||
| + | int t1 = 0, t2 = 2*k-1; | ||
| + | bool ok = true; | ||
| + | for (int i = 1; i <= n; ++i) { | ||
| + | if(l - d[i] >= k){ | ||
| + | t1 = 0, t2 = 2*k-1; | ||
| + | } | ||
| + | |||
| + | else{ | ||
| + | |||
| + | if(l < d[i]){ | ||
| + | ok = false;break; | ||
| + | } | ||
| + | int tt1 = k - (l - d[i]); | ||
| + | int tt2 = k + (l - d[i]); | ||
| + | |||
| + | t1++, t2++; | ||
| + | |||
| + | if(tt2 < t1 || tt1 > t2) { | ||
| + | ok = false; | ||
| + | break; | ||
| + | } | ||
| + | t1 = max(tt1, t1); | ||
| + | t2 = min(tt2, t2); | ||
| + | } | ||
| + | } | ||
| + | |||
| + | cout<<(ok ? "Yes" : "No")<<endl; | ||
| + | } | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/too_low/0725-0731.1596190407.txt.gz · 最后更改: 2020/07/31 18:13 由 jim
