首页 > 代码库 > 2015 一中培训 day 5
2015 一中培训 day 5
又是一天的爆零！！！！！
原本第一题 很容易做 竟然优化过度
丢了答案
先贴上一题
1693: ksum
- Time Limit
- 1000 ms
- Memory Limit
- 524288 KBytes
- Judge
- Standard Judge
- Solved
- 18
- Submit
- 41
Submit Status
Description
Peter喜欢玩数组。NOIP这天，他从Jason手里得到了大小为n的一个正整数 数组。
Peter求出了这个数组的所有子段和，并将这n(n+1)/2个数降序排序，他想 知道前k个数是什么。
Input Format
输入文件名为 ksum.in。
输入数据的第一行包含两个整数 n 和 k。
接下来一行包含 n 个正整数，代表数组。
Output Format
输出文件名为 ksum.out。
输出 k 个数，代表降序之后的前 k 个数，用空格隔开。
Sample Input
input13 41 3 4input23 310 2 7
Sample Output
output18 7 4 4output219 12 10
Hint
测试点编号 n ≤ k ≤
1 100 5000
2 500 100000
3 1000 80000
4 1000 100000
5 10000 50000
6 20000 80000
7 50000 80000
8 100000 80000
9 100000 100000
10 100000 100000
对于所有数据，满足 ai≤10 9 k≤n(n+1)/2,n≤100000,k≤100000
明显的堆维护 对于一段连续序列 它的一系列次小值 一定是这段序列的子集；
只要每次取出 堆顶 将堆顶序列分别由 （l+1,r）&&(l,r-1)的子序列塞入堆中
进行堆维护即可 注意过程可能出现重复顶点 用哈希表维护即可；
#include<cstdio>#include<iostream>#include<cstring>#include<cmath>#include<algorithm>#include<map>#include<vector>#define maxn 100010using namespace std;struct st{ int l,r; long long sum;}mu[2*maxn];typedef pair<int,int> pa;map <pa,bool>q1;int n,m,k,l,n1,i;int a[maxn];void down(int x){ int fa=x,son; while(fa*2<=n1) { son=fa*2; if(mu[son+1].sum>mu[son].sum&&son+1<=n1)son++; if(mu[fa].sum>mu[son].sum)break; swap(mu[fa],mu[son]); fa=son; }}void up(int x){ int fa,son=x; while(son/2) { fa=son/2; if(mu[fa].sum>mu[son].sum)break; swap(mu[fa],mu[son]); son=fa; }}void push (st x){ n1++; q1[pa(x.l,x.r)]=1; mu[n1]=x; up(n1);}int main(){// freopen("ksum.in","r",stdin);// freopen("ksum.out","w",stdout); scanf("%d%d",&n,&k); for(i=1;i<=n;++i) { scanf("%d",&a[i]); mu[1].sum+=a[i]; } n1=1;mu[1].l=1;mu[1].r=n;q1[pa(mu[1].l,mu[1].r)]=1; for(i=1;i<=k;++i) { printf("%lld ",mu[1].sum); if(mu[1].l<mu[1].r) { st q; q=mu[1]; q.sum-=a[q.l]; q.l++; if(!q1[pa(q.l,q.r)]) push(q); q=mu[1]; q.sum-=a[q.r]; q.r--; if(!q1[pa(q.l,q.r)]) push(q); } mu[1]=mu[n1--]; down(1); }}
2015 一中培训 day 5
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。