2020-2021:teams:legal_string:组队训练比赛记录:contest1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest1 [2020/05/14 12:28] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:contest1 [2021/07/11 10:01] (当前版本) jxm2001 ↷ 页面2020-2021:teams:legal_string:contest1被移动至2020-2021:teams:legal_string:组队训练比赛记录:contest1 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| + | [[https://codeforces.com/gym/102569|比赛链接]] | ||
| + | |||
| ====== 题解 ====== | ====== 题解 ====== | ||
| 行 16: | 行 18: | ||
| ===== B. Bonuses on a Line ===== | ===== B. Bonuses on a Line ===== | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | 数轴上有 $n$ 份奖金，每份奖金的坐标为 $x_i$ ，总共有 $t$ 秒的时间，每秒可走 $1$ 的距离。初始在原点 $0$ 位置，问最多能获得多少份奖金？ | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 先向某一方向跑，然后再折返跑向另一方向。例如先向负方向跑，在每份奖金处，利用二分查找，找到能够折返跑到正方向的奖金的最大份数即可。 | ||
| + | |||
| + | 时间复杂度 $O\left(n\log n\right)$ | ||
| + | |||
| + | === 代码 === | ||
| + | |||
| + | <code cpp> | ||
| + | |||
| + | #include<bits/stdc++.h> | ||
| + | using namespace std; | ||
| + | const int N=200005; | ||
| + | typedef long long ll; | ||
| + | vector<ll>neg; | ||
| + | vector<ll>pos; | ||
| + | int main(){ | ||
| + | ll n,t; | ||
| + | scanf("%lld %lld",&n,&t); | ||
| + | for(ll i=1;i<=n;i++){ | ||
| + | ll x; | ||
| + | scanf("%lld",&x); | ||
| + | if(x<0) neg.push_back(-x); | ||
| + | else pos.push_back(x); | ||
| + | } | ||
| + | reverse(neg.begin(),neg.end()); | ||
| + | neg.push_back(1e15);pos.push_back(1e15); | ||
| + | ll maxx=0; | ||
| + | for(ll i=0;i<neg.size()-1;i++){ | ||
| + | if(t>=neg[i]) maxx=max(maxx,i+1); | ||
| + | ll left=t-2*neg[i]; | ||
| + | ll p=upper_bound(pos.begin(),pos.end(),left)-pos.begin()-1; | ||
| + | if(p>=0) maxx=max(maxx,i+1+p+1); | ||
| + | } | ||
| + | for(ll i=0;i<pos.size()-1;i++){ | ||
| + | if(t>=pos[i]) maxx=max(maxx,i+1); | ||
| + | ll left=t-2*pos[i]; | ||
| + | ll p=upper_bound(neg.begin(),neg.end(),left)-neg.begin()-1; | ||
| + | if(p>=0) maxx=max(maxx,i+1+p+1); | ||
| + | } | ||
| + | printf("%lld",maxx); | ||
| + | return 0; | ||
| + | } | ||
| + | |||
| + | </code> | ||
| ===== C. Manhattan Distance ===== | ===== C. Manhattan Distance ===== | ||
| 行 21: | 行 73: | ||
| ===题意=== | ===题意=== | ||
| - | 在直角坐标系中给定$n$整点$\left(-10^8\le x_i,y_i\le 10^8\right)$，可以得到$\frac{n\times \left(n+1\right)}{2}$个点对，将所有点对的哈密顿距离排序，要求输出第k大的哈密顿距离$\left(2\le n\le 100000,1\le k\le \frac{n\times \left(n+1\right)}{2}\right)$ | + | 在直角坐标系中给定$n$整点$\left(-10^8\le x_i,y_i\le 10^8\right)$，可以得到$\frac{n\times \left(n-1\right)}{2}$个点对，将所有点对的哈密顿距离排序，要求输出第k大的哈密顿距离$\left(2\le n\le 100000,1\le k\le \frac{n\times \left(n-1\right)}{2}\right)$ |
| ===题解=== | ===题解=== | ||
| 行 131: | 行 183: | ||
| ===== E. Fluctuations of Mana ===== | ===== E. Fluctuations of Mana ===== | ||
| + | 签到题 | ||
| ===== F. Moving Target ===== | ===== F. Moving Target ===== | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest1.1589430495.txt.gz · 最后更改: 2020/05/14 12:28 由 jxm2001
