大坑最后再填。
20160803：心情好回来填啦(5/7)
做的题目是：
poj2970
我们先每个人都不给钱qwq
然后我们发现有一位的工作时间超过了d
那么我们就从以前安排过工作的人里，a最大的，给他加上一定量的x，使得后面的这个超出di的工作者可以在di前完成任务，或者他的工作时间已经为0，则继续找剩下的当中a最大的
这个过程用堆维护，时间复杂度O(nlogn)
struct data{ int a,b,d; bool operator <(const data&b)const { return a<b.a; } }; bool cmp(const data&a,const data&b){ return a.d<b.d; } int n;data a[100005]; priority_queue<data>q; int main(){ n=gi; FOR1(i,n){ a[i].a=gi;a[i].b=gi;a[i].d=gi; } sort(a+1,a+n+1,cmp); long long sum=0; double ans=0; FOR1(i,n){ sum+=a[i].b; q.push(a[i]); while(!q.empty()&&sum>a[i].d){ data c=q.top();q.pop(); if(sum-c.b>a[i].d){ ans=ans+(double)c.b/c.a; sum=sum-c.b; } else{ ans=ans+(double)(sum-a[i].d)/c.a; c.b=c.b-sum+a[i].d; sum=a[i].d; q.push(c); } } } printf("%.2f ",ans); return 0; }
poj2796
首先由于元素非负，sum[l,r]的值随区间长度增长，单调不降
那么我们求出对于每个元素，以它为最小值的区间最左到哪里，最右到哪里即可
我们用单调栈实现，复杂度就是O(n)
int n,a[100005]; ll qzh[100005]; int pr[100005],nx[100005],ds[100005],top; int main(){ RI(n); FOR1(i,n){ a[i]=gi; qzh[i]=qzh[i-1]+a[i]; } FOR1(i,n){ while(top&&a[ds[top]]>=a[i])--top; pr[i]=top?ds[top]:0; ds[++top]=i; } top=0; FORD(i,n,1){ while(top&&a[ds[top]]>=a[i])--top; nx[i]=top?ds[top]:n+1; ds[++top]=i; } ll ans=0;int l=1,r=1; FOR1(i,n){ ll t=(qzh[nx[i]-1]-qzh[pr[i]])*(ll)(a[i]); if(t>ans){ r=nx[i]-1;l=pr[i]+1; ans=t; } } cout<<ans<<endl;cout<<l<<' '<<r; return 0; }
ural 1003
考虑前缀和的奇偶性
区间和是奇数的，说明头尾的前缀和奇偶性不同区间和是偶数的，说明头尾的前缀和奇偶性相同
直接使用并查集维护这个关系，回答询问
int l,n,block; int a[5001],b[5001],f[100006]; char s[5001][6]; int find(int x){ return f[x]==x?x:f[x]=find(f[x]); } void uni(int a,int b){ int p,q; p=find(a); q=find(b); if(q!=p) f[q]=p; } int main(){ block=50003; while (scanf("%d",&l),l!=-1){ scanf("%d",&n); FOR1(i,n) a[i]=gi,b[i]=gi,scanf("%s",s[i]); FOR1(i,block*2)f[i]=i; f[0]=1; int i=1; for(;i<=n;i++){ int x=(a[i]-1)%block,y=b[i]%block; if(s[i][0]=='e'){ if(find(x)==find(y+block))break; uni(x,y); uni(x+block,y+block); }else{ if(find(x+block)==find(y+block))break; uni(x,y+block); uni(x+block,y); } } printf("%d ",i-1); } }
sgu 180
逆序对裸题，有很多做法，过于简单不贴代码了
ural 1028
【题意】给定多个二维坐标，求每个点左下角的点数
树状数组
poj版需要特判重点
int c[32005]; int lowbit(int x){ return x &(-x); } int sum(int i){ int s=0; while(i>0){ s=s+c[i]; i=i-lowbit(i); } return s; } void update(int i,int value){ while(i<=32005){ c[i]=c[i]+value; i=i+lowbit(i); } } int level[32005]; int main(){ int Case; scanf("%d",&Case); int x,y; for(int i=0;i<Case;i++){ scanf("%d%d",&x,&y); int tmp=sum(++x); level[tmp]++; update(x,1); } for(int i=0;i<Case;i++) printf("%d ",level[i]); return 0; }
poj2944 、sgu 336
不会做
强烈推荐在vjudge做