2020-2021:teams:legal_string:组队训练比赛记录:contest1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest1 [2020/05/13 18:27] jxm2001 M题 |
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|比赛链接]] | ||
| + | |||
| ====== 题解 ====== | ====== 题解 ====== | ||
| 行 5: | 行 7: | ||
| === 题意 === | === 题意 === | ||
| - | 给定一个长度为$n$的数组，这么定义该数组的哈希值：每次从数组开头取出两个数，将后一个数减去前一个数得到的数值放入数组开头，如此重复，直到数组中只剩下一个数，最后这个数便为数组的哈希值。现在每次操作把一段区间的数加上$v$，要求输出每次操作后数组的哈希值 | + | 给定一个长度为$n$的数组，这么定义该数组的哈希值：每次从数组开头取出两个数，将后一个数减去前一个数得到的数值放入数组开头，如此重复，直到数组中只剩下一个数，最后这个数便为数组的哈希值。现在有$m$次操作，每次操作把一段区间的数加上$v$，要求输出每次操作后数组的哈希值 |
| ===题解=== | ===题解=== | ||
| 行 13: | 行 15: | ||
| 因此当区间左右端点奇偶性相同时对哈希值无贡献，奇偶性不同时如果区间左端点与$n$奇偶性相同则哈希值加$v$，否则减$v$ | 因此当区间左右端点奇偶性相同时对哈希值无贡献，奇偶性不同时如果区间左端点与$n$奇偶性相同则哈希值加$v$，否则减$v$ | ||
| - | 时间复杂度$O\left(n\right)$ | + | 时间复杂度$O\left(n+m\right)$ |
| ===== 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)$ |
| ===题解=== | ===题解=== | ||
| 行 27: | 行 79: | ||
| 大概思路为二分答案$d$，统计哈密顿距离$\le d$的点对个数 | 大概思路为二分答案$d$，统计哈密顿距离$\le d$的点对个数 | ||
| - | 首先，将坐标系顺时针旋转$45$度，放大$\sqrt{2}$倍，所以所有点坐标变为$\left(x-y,x+y\right)$，与某个点哈密顿距离$\le d$转化为在以该点为中心的边与坐标轴平行且长度为$2d$的正方形中 | + | 首先，将坐标系顺时针旋转$45$度，放大$\sqrt{2}$倍，所以所有点坐标变为$\left(x-y,x+y\right)$，与某个点哈密顿距离$\le d$转化为在以该点为中心的边长为$2d$的网格正方形中 |
| 考虑用滑动窗口+树状树组统计答案，具体过程见代码 | 考虑用滑动窗口+树状树组统计答案，具体过程见代码 | ||
| + | |||
| + | 时间复杂度$O\left(\log\left(4\times 10^8\right) n\log n\right)$ | ||
| ===代码=== | ===代码=== | ||
| 行 129: | 行 183: | ||
| ===== E. Fluctuations of Mana ===== | ===== E. Fluctuations of Mana ===== | ||
| + | 签到题 | ||
| ===== F. Moving Target ===== | ===== F. Moving Target ===== | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest1.1589365671.txt.gz · 最后更改: 2020/05/13 18:27 由 jxm2001
