大坑最后再填。
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\n",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\n",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\n",level[i]);
return 0;
}
poj2944 、sgu 336
不会做
强烈推荐在vjudge做