2020-2021:teams:no_morning_training:week1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:no_morning_training:week1 [2020/05/08 21:10] shaco |
2020-2021:teams:no_morning_training:week1 [2020/06/05 15:27] (当前版本) shaco ↷ 链接因页面移动而自动修正 |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| ===== 王瑞琦 ===== | ===== 王瑞琦 ===== | ||
| - | ---- | ||
| **专题** | **专题** | ||
| - 树 | - 树 | ||
| 还没有打比赛orz，稍微练了几道树的题 | 还没有打比赛orz，稍微练了几道树的题 | ||
| ===== 冯宇扬 ===== | ===== 冯宇扬 ===== | ||
| + | **专题** | ||
| - | ---- | + | - lct复健 |
| + | |||
| + | |||
| + | **比赛** | ||
| + | |||
| + | - 没打 | ||
| ===== 常程 ===== | ===== 常程 ===== | ||
| - | ---- | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| - | * [[2020-2021:teams:no_morning_training:尺取法|尺取法]] | + | * [[2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法|尺取法]] |
| - | * [[2020-2021:teams:no_morning_training:前缀和|前缀和]] | + | * [[2020-2021:teams:no_morning_training:shaco:知识点:基础:前缀和|前缀和]] |
| （由于我太菜了所以写一点基础的） | （由于我太菜了所以写一点基础的） | ||
| === 比赛 === | === 比赛 === | ||
| 行 30: | 行 34: | ||
| ===== 本周推荐 ===== | ===== 本周推荐 ===== | ||
| + | |||
| ==== 王瑞琦 ==== | ==== 王瑞琦 ==== | ||
| + | 一个模板题，[[2020-2021:teams:no_morning_training:表达式的计算]] | ||
| + | |||
| + | |||
| ==== 冯宇扬 ==== | ==== 冯宇扬 ==== | ||
| + | 搓了一道 [[https://www.luogu.com.cn/problem/P1600|P1600 天天爱跑步]] | ||
| + | |||
| + | 发现了绝妙的做法，但是还没有debug出来 | ||
| + | |||
| + | 思路是求完dfn以后转化成三维偏序，然后能压掉一维 | ||
| ==== 常程 ==== | ==== 常程 ==== | ||
| + | poj 2566 （专题里有，不过我觉得挺好的） | ||
| + | |||
| 给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小。数组中的数可正可负。 | 给定一个数组和一个值t，求一个子区间使得其和的绝对值与t的差值最小。数组中的数可正可负。 | ||
| 将前缀和排序，排序后每两个位置的前缀和之差代表一个原来的区间的和的绝对值(妙啊），同时在这个排序后的前缀和序列中随区间增缩所取的区间和的绝对值也增缩。这样运用尺取法是一个好的选择。 | 将前缀和排序，排序后每两个位置的前缀和之差代表一个原来的区间的和的绝对值(妙啊），同时在这个排序后的前缀和序列中随区间增缩所取的区间和的绝对值也增缩。这样运用尺取法是一个好的选择。 | ||
| - | #include<cstdio> | + | [[2020-2021:teams:no_morning_training:poj2566|代码]] |
| - | #include<algorithm> | + | |
| - | #define INF 0x3f3f3f3f | + | |
| - | using namespace std; | + | |
| - | int n,k,a; | + | |
| - | typedef pair<int,int> unit; | + | |
| - | unit sum[100005]; | + | |
| - | int main() | + | |
| - | { | + | |
| - | while(scanf("%d%d",&n,&k)&&n) | + | |
| - | { | + | |
| - | for(int i=1;i<=n;i++) | + | |
| - | { | + | |
| - | scanf("%d",&a); | + | |
| - | sum[i]=unit(sum[i-1].first+a,i); | + | |
| - | } | + | |
| - | sort(sum+1,sum+1+n); | + | |
| - | for(int i=1;i<=k;i++) | + | |
| - | { | + | |
| - | scanf("%d",&a); | + | |
| - | int t=INF,l,r; | + | |
| - | for(int left=1,right=1;right<=n;right++) | + | |
| - | { | + | |
| - | while(sum[right].first-sum[left].first>a) | + | |
| - | { | + | |
| - | if(sum[right].first-sum[left].first-a<t) | + | |
| - | { | + | |
| - | t=sum[right].first-sum[left].first-a; | + | |
| - | l=sum[left].second; | + | |
| - | r=sum[right].second; | + | |
| - | } | + | |
| - | left++; | + | |
| - | } | + | |
| - | if(a-sum[right].first+sum[left].first<t) | + | |
| - | { | + | |
| - | t=a-sum[right].first+sum[left].first; | + | |
| - | l=sum[left].second; | + | |
| - | r=sum[right].second; | + | |
| - | } | + | |
| - | } | + | |
| - | printf("%d %d %d\n",sum[r].first-sum[l].first,l,r); | + | |
| - | } | + | |
| - | } | + | |
| - | return 0; | + | |
| - | } | + | |
2020-2021/teams/no_morning_training/week1.1588943436.txt.gz · 最后更改: 2020/05/08 21:10 由 shaco
