[关闭]
@CQUPTacm 2017-03-05T22:06:29.000000Z 字数 17536 阅读 1349

萌新集中营第一期

题解

题目

A Sumsets (UVA - 10125)

题意：

    给一个集合，集合里有n(1<=n<=1000)个数，每个数的范围是(-536870912，+536870911)，并且每个数是不同的。求满足d=a+b+c的最大的d，abcd是集合内的不同元素。
    多组数据。

题解：

    预处理所有的a+b的和。
    枚举d，和其中一个加数c，然后去找所有a+b=d-c的情况，然后判断是否存在某个情况的a和b都不等于c和d。
    时间复杂度很迷。。。
    ps：网上的标程有问题。

代码：

方法1：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. int n;
  6. int num[1005],nums,ans;
  7. pair <int,int> p[1000005];
  8. bool cmp(pair<int,int> x1,pair<int,int> x2)
  9. {
  10.     if(x1.first==x2.first)
  11.         return x1.second<x2.second;
  12.     else
  13.         return x1.first<x2.first;
  14. }
  15. bool ask(int val,int x,int y)
  16. {
  17.     int l=0,r=nums-1,mid;
  18.     int minn,maxx;
  19.     while(l!=r)
  20.     {
  21.         mid=(l+r)/2;
  22.         if(p[mid].first<val)
  23.             l=mid+1;
  24.         else
  25.             r=mid;
  26.     }
  27.     minn=l;
  28.     l=0,r=nums-1;
  29.     while(l!=r)
  30.     {
  31.         mid=(l+r+1)/2;
  32.         if(p[mid].first>val)
  33.             r=mid-1;
  34.         else
  35.             l=mid;
  36.     }
  37.     maxx=r;
  38.     for(int i=minn;i<=maxx;i++)
  39.     {
  40.         if(p[i].first==val && p[i].second!=x && p[i].second!=y && num[x]+num[p[i].second]!=val && num[y]+num[p[i].second]!=val)
  41.             return 1;
  42.     }
  43.     return 0;
  44. }
  45. int main()
  46. {
  47.     while(~scanf("%d",&n),n)
  48.     {
  49.         ans=-2000000000;
  50.         for(int i=0;i<n;i++)
  51.             scanf("%d",num+i);
  52.         nums=0;
  53.         sort(num,num+n);
  54.         for(int i=0;i<n-1;i++)
  55.             for(int j=i+1;j<n;j++)
  56.             {
  57.                 p[nums].first=num[i]+num[j];
  58.                 p[nums].second=j;
  59.                 nums++;
  60.             }
  61.         sort(p,p+nums,cmp);
  62.         for(int i=n-1;i>=0 && ans==-2000000000;i--)
  63.             for(int j=n-1;j>=0 && ans==-2000000000;j--)
  64.                 if(i!=j && ask(num[i]-num[j],i,j))
  65.                     ans=num[i];
  66.         if(ans==-2000000000)
  67.             printf("no solution\n");
  68.         else
  69.             printf("%d\n",ans);
  70.     }
  71.     return 0;
  72. }

方法2：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #define INF -600000000
  5. using namespace std;
  6. int main()
  7. {
  8.     int n;
  9.     int ar[1005];
  10.     while(scanf("%d",&n)!=EOF&&n!=0)
  11.     {
  12.         for(int i=0;i<n;i++)
  13.             scanf("%d",&ar[i]);
  14.         sort(ar,ar+n);
  15.         n--;
  16.         int ans=INF;
  17.         for(int i=n;i>=0;i--)
  18.         {
  19.             for(int j=n;j>=0;j--)
  20.             {
  21.                 if(i==j)
  22.                     continue;
  23.                 int sum=ar[i]-ar[j];
  24.                 for(int l=0,r=j-1;l<r;)
  25.                 {
  26.                     if(ar[l]+ar[r]==sum)
  27.                     {
  28.                         if(l!=i && l!=j && r!=i && r!=j)
  29.                         {
  30.                             ans=ar[i];
  31.                             break;
  32.                         }
  33.                         else
  34.                         {
  35.                             if(l==i || l==j)
  36.                                 l++;
  37.                             else
  38.                                 r--;
  39.                         }
  40.                     }
  41.                     if(ar[l]+ar[r]>sum)
  42.                         r--;
  43.                     else
  44.                         l++;
  45.                 }
  46.                 if(ans!=INF)
  47.                     break;
  48.             }
  49.             if(ans!=INF)
  50.                 break;
  51.         }
  52.         if(ans==INF)
  53.             printf("no solution\n");
  54.         else
  55.             printf("%d\n",ans);
  56.     }
  57.     return 0;
  58. }

B Drying (POJ - 3104)

题意：

    有n(1<=n<=100000)件衣服，每件衣服有个湿度a(1<=a<=10^9)，一件衣服自然风干时每秒湿度下降1。每分钟可以把一件衣服放在烘干机上，使其湿度下降k(1<=k<=10^9)但不能低于0。
    问最少花多长时间能够让所有衣服湿度为0。

题解：

    二分枚举时间，判断能否在这个时间内完成干衣。
    判断的时候要注意：一件衣服放在烘干机上的时候是不能自然风干的，所以只能多降(k-1)的湿度。当k=1的时候，烘干机就没用了。
    时间复杂度o(n*log(10^9))。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. int n;
  6. long long k,num[100005];
  7. bool ok(long long x)
  8. {
  9.     long long ans=0;
  10.     for(int i=0;i<n;i++)
  11.     {
  12.         if(num[i]>x)
  13.         {
  14.             ans+=(num[i]-x)/(k-1);
  15.             if((num[i]-x)%(k-1))
  16.                 ans++;
  17.         }
  18.     }
  19.     return ans<=x;
  20. }
  21. int main()
  22. {
  23.     long long mid,l=0,r=0;
  24.     scanf("%d",&n);
  25.     for(int i=0;i<n;i++)
  26.     {
  27.         scanf("%lld",num+i);
  28.         r=max(r,num[i]);
  29.     }
  30.     scanf("%lld",&k);
  31.     if(k>1)
  32.     {
  33.         while(l!=r)
  34.         {
  35.             mid=(l+r)/2;
  36.             if(ok(mid))
  37.                 r=mid;
  38.             else
  39.                 l=mid+1;
  40.         }
  41.     }
  42.     printf("%lld\n",r);
  43.     return 0;
  44. }

C Potentiometers (UVA - 12086)

题意：

    有N(N<=200000)个串联的电阻，第i个电阻的阻值为Ri(0<=Ri<=1000)。有不超过200000个操作，操作分为三种：(1)S x r，表示把第x个电阻替换为阻值为r(0<=r<=1000)的电阻；(2)M x y，表示询问从第x个到第y个电阻的总电阻；(3)END，表示结束。
    多组数据。

题解：

    单点更新，区间求和。
    用线段树维护区间和或者用树状数组维护前缀和即可。
    时间复杂度都为o(N*log(N))，空间复杂度都为o(N)。
    ps：题目提示了输入数据相当大，用scanf输入为好。

代码：

线段树：

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. struct Node
  5. {
  6.     int l,r,mid,val;
  7. }tre[800005];
  8. int num[200005],n;
  9. char s[6];
  10. int build(int no,int l,int r)
  11. {
  12.     tre[no].l=l;
  13.     tre[no].r=r;
  14.     tre[no].mid=(l+r)/2;
  15.     if(l==r)
  16.         return tre[no].val=num[l];
  17.     else
  18.         return tre[no].val=build(no*2,l,tre[no].mid)+build(no*2+1,tre[no].mid+1,r);
  19. }
  20. void change(int no,int pos,int newval)
  21. {
  22.     if(tre[no].l==pos && pos==tre[no].r)
  23.         tre[no].val=newval;
  24.     else
  25.     {
  26.         if(pos<=tre[no].mid)
  27.             change(no*2,pos,newval);
  28.         else
  29.             change(no*2+1,pos,newval);
  30.         tre[no].val=tre[no*2].val+tre[no*2+1].val;
  31.     }
  32.     return;
  33. }
  34. int ask(int no,int lpos,int rpos)
  35. {
  36.     if(tre[no].l==lpos && tre[no].r==rpos)
  37.         return tre[no].val;
  38.     else
  39.     {
  40.         if(lpos<=tre[no].mid && rpos>tre[no].mid)
  41.             return ask(no*2,lpos,tre[no].mid)+ask(no*2+1,tre[no].mid+1,rpos);
  42.         else
  43.         {
  44.             if(rpos<=tre[no].mid)
  45.                 return ask(no*2,lpos,rpos);
  46.             else
  47.                 return ask(no*2+1,lpos,rpos);
  48.         }
  49.     }
  50. }
  51. int main()
  52. {
  53.     int t=0,x,y,r;
  54.     while(scanf("%d",&n),n)
  55.     {
  56.         if(t)
  57.             printf("\n");
  58.         t++;
  59.         printf("Case %d:\n",t);
  60.         for(int i=1;i<=n;i++)
  61.             scanf("%d",num+i);
  62.         build(1,1,n);
  63.         while(scanf("%s",s),s[0]!='E')
  64.         {
  65.             if(s[0]=='S')
  66.             {
  67.                 scanf("%d%d",&x,&r);
  68.                 change(1,x,r);
  69.             }
  70.             else
  71.             {
  72.                 scanf("%d%d",&x,&y);
  73.                 printf("%d\n",ask(1,x,y));
  74.             }
  75.         }
  76.     }
  77.     return 0;
  78. }

树状数组：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. int tre[200005],n,num[200005];
  6. char s[6];
  7. int lowbit(int x)
  8. {
  9.     return -x&x;
  10. }
  11. void add(int pos,int val)
  12. {
  13.     while(pos<=n)
  14.     {
  15.         tre[pos]+=val;
  16.         pos+=lowbit(pos);
  17.     }
  18. }
  19. int ask(int pos)
  20. {
  21.     int ans=0;
  22.     while(pos)
  23.     {
  24.         ans+=tre[pos];
  25.         pos-=lowbit(pos);
  26.     }
  27.     return ans;
  28. }
  29. int main()
  30. {
  31.     int t=0,x,y,r;
  32.     while(scanf("%d",&n),n)
  33.     {
  34.         if(t)
  35.             printf("\n");
  36.         t++;
  37.         printf("Case %d:\n",t);
  38.         memset(tre,0,sizeof(tre));
  39.         for(int i=1;i<=n;i++)
  40.         {
  41.             scanf("%d",num+i);
  42.             add(i,num[i]);
  43.         }
  44.         while(scanf("%s",s),s[0]!='E')
  45.         {
  46.             if(s[0]=='S')
  47.             {
  48.                 scanf("%d%d",&x,&r);
  49.                 add(x,r-num[x]);
  50.                 num[x]=r;
  51.             }
  52.             else
  53.             {
  54.                 scanf("%d%d",&x,&y);
  55.                 printf("%d\n",ask(y)-ask(x-1));
  56.             }
  57.         }
  58.     }
  59.     return 0;
  60. }

D I Hate It (HDU - 1754)

题意：

    中文题我就不翻译了。。。

题解：

    单点更新，区间求最值。
    线段树维护区间最值比较简单。重点说一下树状数组维护区间最值的方法。
    num[i]表示原序列的第i项，tre[i]表示[i-lowbit(i)+1，i]这个区间内的最值，换句话说，tre[i]的管辖范围为从i往前包括i在内的lowbit(i)个数。
    查询的时候，我们会把查询当前点now的管辖范围，如果小于左端点，那么我们就不用tre[now]而用num[now]的值去更新答案，同时下一个now就等于now-1，因为num[now]只能管辖自己，相当于管辖范围为1；如果不小于左端点，那么直接用tre[i]更新答案，同时下一个now就等于now-lowbit(now)，因为[now-lowbit(now)+1，now]这个区间内的所有值相当于都被考虑过了。
    更新的时候，如果更新后的num[i]大于原本的，那么直接更新他的所有父亲就可以了，但是如果比原本的小，我们就会发现，情况变得很复杂。为了保证tre数组的性质，我们在更新i的某个父亲fa的时候 还要考虑到fa的所有孩子，所以我们需要用ask(1，fa)来更新tre[fa]，但是这个时候fa还没更新，所以我们只能用ask(1,fa-1)和num[fa]去更新tre[fa]。
    线段树的时间复杂度为o(M*log(N))，空间复杂度为o(N)。
    树状数组的空间复杂度为o(N)，单次查询和更新的时间复杂度均为o(log(N)*log(N))。

代码：

线段树：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. struct Node
  6. {
  7.     int l,r,mid,val;
  8. }tre[800005];
  9. int num[200005],n;
  10. char s[6];
  11. int build(int no,int l,int r)
  12. {
  13.     tre[no].l=l;
  14.     tre[no].r=r;
  15.     tre[no].mid=(l+r)/2;
  16.     if(l==r)
  17.         return tre[no].val=num[l];
  18.     else
  19.         return tre[no].val=max(build(no*2,l,tre[no].mid),build(no*2+1,tre[no].mid+1,r));
  20. }
  21. void change(int no,int pos,int newval)
  22. {
  23.     if(tre[no].l==pos && pos==tre[no].r)
  24.         tre[no].val=newval;
  25.     else
  26.     {
  27.         if(pos<=tre[no].mid)
  28.             change(no*2,pos,newval);
  29.         else
  30.             change(no*2+1,pos,newval);
  31.         tre[no].val=max(tre[no*2].val,tre[no*2+1].val);
  32.     }
  33.     return;
  34. }
  35. int ask(int no,int lpos,int rpos)
  36. {
  37.     if(tre[no].l==lpos && tre[no].r==rpos)
  38.         return tre[no].val;
  39.     else
  40.     {
  41.         if(lpos<=tre[no].mid && rpos>tre[no].mid)
  42.             return max(ask(no*2,lpos,tre[no].mid),ask(no*2+1,tre[no].mid+1,rpos));
  43.         else
  44.         {
  45.             if(rpos<=tre[no].mid)
  46.                 return ask(no*2,lpos,rpos);
  47.             else
  48.                 return ask(no*2+1,lpos,rpos);
  49.         }
  50.     }
  51. }
  52. int main()
  53. {
  54.     int x,y,r,m;
  55.     while(~scanf("%d%d",&n,&m))
  56.     {
  57.         for(int i=1;i<=n;i++)
  58.             scanf("%d",num+i);
  59.         build(1,1,n);
  60.         while(m--)
  61.         {
  62.             scanf("%s",s);
  63.             if(s[0]=='U')
  64.             {
  65.                 scanf("%d%d",&x,&r);
  66.                 change(1,x,r);
  67.             }
  68.             else
  69.             {
  70.                 scanf("%d%d",&x,&y);
  71.                 printf("%d\n",ask(1,x,y));
  72.             }
  73.         }
  74.     }
  75.     return 0;
  76. }

树状数组：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. int tre[200005],n,num[200005];
  7. char s[6];
  8. int lowbit(int x)
  9. {
  10.     return -x&x;
  11. }
  12. int ask(int lpos,int rpos)
  13. {
  14.     int ans=0;
  15.     while(rpos>=lpos)
  16.     {
  17.         while(rpos>=lpos && rpos-lowbit(rpos)+1>=lpos)
  18.         {
  19.             ans=max(ans,tre[rpos]);
  20.             rpos-=lowbit(rpos);
  21.         }
  22.         if(rpos>=lpos)
  23.         {
  24.             ans=max(ans,num[rpos]);
  25.             rpos--;
  26.         }
  27.     }
  28.     return ans;
  29. }
  30. void add(int pos,int val)
  31. {
  32.     while(pos<=n)
  33.     {
  34.         if(val>=tre[pos])
  35.             tre[pos]=val;
  36.         else
  37.             tre[pos]=max(ask(pos-lowbit(pos)+1,pos-1),num[pos]);
  38.         pos+=lowbit(pos);
  39.     }
  40. }
  41. int main()
  42. {
  43.     int x,y,r,m;
  44.     while(~scanf("%d%d",&n,&m))
  45.     {
  46.         memset(tre,0,sizeof(tre));
  47.         memset(num,0,sizeof(num));
  48.         for(int i=1;i<=n;i++)
  49.         {
  50.             scanf("%d",num+i);
  51.             add(i,num[i]);
  52.         }
  53.         while(m--)
  54.         {
  55.             scanf("%s",s);
  56.             if(s[0]=='U')
  57.             {
  58.                 scanf("%d%d",&x,&r);
  59.                 num[x]=r;
  60.                 add(x,num[x]);
  61.             }
  62.             else
  63.             {
  64.                 scanf("%d%d",&x,&y);
  65.                 printf("%d\n",ask(x,y));
  66.             }
  67.         }
  68.     }
  69.     return 0;
  70. }

E A Simple Problem with Integers (POJ - 3468)

题意：

    数列有N(1<=N<=100000)个数，第i个数为Ai(-1000000000<=Ai<=1000000000)，有Q(1<=Q<=100000)个操作，操作分两种：(1)C a b c，表示把第a个数到第b个数加上c；(2)Q a b，表示询问第a个数到第b个数的和。

题解：

    区间更新，区间求和。
    线段树的话，区间更新要用到lazy标记，lazy标记的原理实际上就是延迟更新。更新到某个区间的时候，如果整个区间都需要更新，那么更新答案后直接修改标记，不用再往下层更新了。查询或者更新的时候，如果当前区间存在标记，但是整个区间不全需要更新或者查询，就先把标记下放，再进行更新或者查询。这样就可以做到每次更新和查询都是logN级别的。
    树状数组则用到了差分数列的知识。我们用num1[i]表示原数列的第i项，用num2[i]表示num1[i]-num1[i-1]即原数列第i项和第i-1项的差，我们会发现，当把[x,y]区间的数都加上C，num2[x]变为num2[x]+c，num2[y+1]变为num2[y+1]-c，而num2的其他项都不变。因为x之前的项数值都没变差值也不会变，第x项加了c所以差值也加了c，而x+1...y项也加了c，所以和前一项的差值不变，y+1项没有变但是由于第y项加了c所以差值相当于减c了，y+1之后的项都没变，所以y+2及以后的项，差值都不变。于是num2[1]+num2[2]+...+num2[i]就等于num1[i]。而我们要求的区间和，可以转化为两个前缀和的差，这个是区间和的一般做法，所以现在我们面对的问题是，如何求num1[1]+num1[2]...+num1[i]。因为num1[i]等于num2[i]前i项的和，所以简单转化一下，我们就可以得到num1[1]+num2[2]+...+num1[i]=num2[1]*i+num2[2]*(i-1)+...+num2[i]*1。但是这个式子还是没法求，于是我们再转化一下变成num2[1]*(i-0)+num2[2]*(i-1)+...+num2[i]*(i-(i-1))=(num2[1]*i+num2[2]*i+...+num2[i]*i)-(num2[1]*0+num2[2]*1+...+num2[i]*(i-1))，因为num1[i]=num2[1]+num2[2]+...+num2[i]，所以前一个括号相当于num1[i]*i，也就是num2的前i项和乘上i，而后一个括号，因为每一项的系数固定等于下标减一，所以我们可以用num3[i]表示num2[i]*(i-1)，因为num3和num2之间的关系是固定的，所以只有当num2变化，num3才变化，所以复杂度是一样的。这样后面一个括号就等于num3[1]+num3[2]+...num3[i]，等于num3的前i项和。于是我们用两个树状数组分别维护num2的前缀和和num3的前缀和，就可以通过之前的公式得到答案。从我给出的代码可以看出，num2和num3是可以没有实体的，因为每次的修改量和之前的值无关。
    线段树的时间复杂度o(Q*log(N))，空间复杂度o(N)。
    树状数组的时间复杂度o(Q*log(N))，空间复杂度o(N)。
    PS：常数级别的差异你们自己写一下或者交一下我的代码就知道了。

代码：

线段树：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. struct Node
  6. {
  7.     int l,r,mid;
  8.     long long val,lazy;
  9. }tre[800005];
  10. long long num[200005];
  11. int n;
  12. char s[6];
  13. long long build(int no,int l,int r)
  14. {
  15.     tre[no].l=l;
  16.     tre[no].r=r;
  17.     tre[no].mid=(l+r)/2;
  18.     tre[no].lazy=0;
  19.     if(l==r)
  20.         return tre[no].val=num[l];
  21.     else
  22.         return tre[no].val=build(no*2,l,tre[no].mid)+build(no*2+1,tre[no].mid+1,r);
  23. }
  24. void change(int no,int lpos,int rpos,long long newval)
  25. {
  26.     if(lpos==tre[no].l && rpos==tre[no].r)
  27.     {
  28.         tre[no].val+=newval*(rpos-lpos+1);
  29.         tre[no].lazy+=newval;
  30.     }
  31.     else
  32.     {
  33.         if(tre[no].lazy)
  34.         {
  35.             change(no*2,tre[no].l,tre[no].mid,tre[no].lazy);
  36.             change(no*2+1,tre[no].mid+1,tre[no].r,tre[no].lazy);
  37.         }
  38.         tre[no].lazy=0;
  39.         if(lpos<=tre[no].mid && rpos>tre[no].mid )
  40.         {
  41.             change(no*2,lpos,tre[no].mid,newval);
  42.             change(no*2+1,tre[no].mid+1,rpos,newval);
  43.         }
  44.         else
  45.         {
  46.             if(rpos<=tre[no].mid)
  47.                 change(no*2,lpos,rpos,newval);
  48.             else
  49.                 change(no*2+1,lpos,rpos,newval);
  50.         }
  51.         tre[no].val=tre[no*2].val+tre[no*2+1].val;
  52.     }
  53.     return;
  54. }
  55. long long ask(int no,int lpos,int rpos)
  56. {
  57.     if(tre[no].l==lpos && tre[no].r==rpos)
  58.         return tre[no].val;
  59.     else
  60.     {
  61.         if(tre[no].lazy)
  62.         {
  63.             change(no*2,tre[no].l,tre[no].mid,tre[no].lazy);
  64.             change(no*2+1,tre[no].mid+1,tre[no].r,tre[no].lazy);
  65.         }
  66.         tre[no].lazy=0;
  67.         if(lpos<=tre[no].mid && rpos>tre[no].mid)
  68.             return ask(no*2,lpos,tre[no].mid)+ask(no*2+1,tre[no].mid+1,rpos);
  69.         else
  70.         {
  71.             if(rpos<=tre[no].mid)
  72.                 return ask(no*2,lpos,rpos);
  73.             else
  74.                 return ask(no*2+1,lpos,rpos);
  75.         }
  76.     }
  77. }
  78. int main()
  79. {
  80.     int x,y,m;
  81.     long long r;
  82.     while(~scanf("%d%d",&n,&m))
  83.     {
  84.         for(int i=1;i<=n;i++)
  85.             scanf("%lld",num+i);
  86.         build(1,1,n);
  87.         while(m--)
  88.         {
  89.             scanf("%s",s);
  90.             if(s[0]=='C')
  91.             {
  92.                 scanf("%d%d%lld",&x,&y,&r);
  93.                 change(1,x,y,r);
  94.             }
  95.             else
  96.             {
  97.                 scanf("%d%d",&x,&y);
  98.                 printf("%lld\n",ask(1,x,y));
  99.             }
  100.         }
  101.     }
  102.     return 0;
  103. }

树状数组：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. long long tre1[200005],tre2[200005];
  6. long long num[200005];
  7. int n;
  8. char s[6];
  9. int lowbit(int x)
  10. {
  11.     return -x&x;
  12. }
  13. void add(long long tre[],int pos,long long val)
  14. {
  15.     while(pos<=n)
  16.     {
  17.         tre[pos]+=val;
  18.         pos+=lowbit(pos);
  19.     }
  20. }
  21. long long ask(long long tre[],int pos)
  22. {
  23.     long long ans=0;
  24.     while(pos)
  25.     {
  26.         ans+=tre[pos];
  27.         pos-=lowbit(pos);
  28.     }
  29.     return ans;
  30. }
  31. int main()
  32. {
  33.     int x,y,m;
  34.     long long r;
  35.     while(~scanf("%d%d",&n,&m))
  36.     {
  37.         memset(tre1,0,sizeof(tre2));
  38.         memset(tre1,0,sizeof(tre2));
  39.         for(int i=1;i<=n;i++)
  40.         {
  41.             scanf("%lld",num+i);
  42.             add(tre1,i,num[i]-num[i-1]);
  43.             add(tre2,i,(num[i]-num[i-1])*(i-1));
  44.         }
  45.         while(m--)
  46.         {
  47.             scanf("%s",s);
  48.             if(s[0]=='C')
  49.             {
  50.                 scanf("%d%d%lld",&x,&y,&r);
  51.                 add(tre1,x,r);
  52.                 add(tre1,y+1,-r);
  53.                 add(tre2,x,r*(x-1));
  54.                 add(tre2,y+1,-r*y);
  55.             }
  56.             else
  57.             {
  58.                 scanf("%d%d",&x,&y);
  59.                 printf("%lld\n",(ask(tre1,y)*y-ask(tre2,y))-(ask(tre1,x-1)*(x-1)-ask(tre2,x-1)));
  60.             }
  61.         }
  62.     }
  63.     return 0;
  64. }

F Sliding Window (POJ - 2823)

题意：

    数列有n(n<=10^6)个int，区间的长度为k(1<=k<=n)，分别求区间[1，k]，[2，k+1]，...，[n-k+1,n]的最大值和最小值。

题解：

    用线段树做的话，用线段树分别维护区间最小值和最大值，然后对于每个长度为k的区间查询一次即可。为了节省空间可以用一棵线段树同时维护最大最小值，查询的时候以flag标记来区别查询的是最小值还是最大值就行了。
    还有一种解法是单调队列。先讲单调队列的实现，以单调递减队列为例，每次加入新点的时候，如果原来的队尾大于等于新入队的点的话符合单调递减，才将新点入队；如果原来的队尾小于新入队的点，为了保持队列的单调性，要先把原来的队尾出队，直到队列为空或者当前队尾大于等于新入队的点，才将新点入队。单调递增队列则相反。
    当求区间最小值的时候，维护一个单调递增的队列。当区间往右移动1格，先判断原先的队首是不是还在新区间中，如果不在则出队，这是为了保证单调队列内的点都在新区间内。新区间的右端点则按照单调递增队列的入队操作进行入队。在新点入队过程中，只会将队列中在新端点左边并且比新端点大的点出队，因为之前的区间的最小值已经不用再去考虑了，而新点比出队的这些点要小，又出现的晚，所以之后这些出队的点一定没机会成为区间的最小值，所以可以直接出队。以上操作完成后，此时的队首就是以新端点为右端点的区间最小值。因为要判断之前的队首在不在新区间，所以每个节点除了记录值之外，还要记录在原数列中的下标。注意在每次判断出队之前，要先判断队列是否为空。
    线段树的时间复杂度为o(n*log(n))，空间复杂度为o(n)。
    单调队列的时间复杂度为o(n)，空间复杂度为o(n)。
    PS：本题由于输入输出数据量太庞大，时间复杂度的差异不明显。。。

代码：

线段树：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. struct Node
  6. {
  7.     int l,r,mid,minval,maxval;
  8. }tre[4000005];
  9. int num[1000005],n;
  10. void build(int no,int l,int r)
  11. {
  12.     tre[no].l=l;
  13.     tre[no].r=r;
  14.     tre[no].mid=(l+r)/2;
  15.     if(l==r)
  16.         tre[no].minval=tre[no].maxval=num[l];
  17.     else
  18.     {
  19.         build(no*2,l,tre[no].mid);
  20.         build(no*2+1,tre[no].mid+1,r);
  21.         tre[no].maxval=max(tre[no*2].maxval,tre[no*2+1].maxval);
  22.         tre[no].minval=min(tre[no*2].minval,tre[no*2+1].minval);
  23.     }
  24. }
  25. int ask(bool flag,int no,int lpos,int rpos)
  26. {
  27.     if(tre[no].l==lpos && tre[no].r==rpos)
  28.     {
  29.         if(flag)
  30.             return tre[no].maxval;
  31.         else
  32.             return tre[no].minval;
  33.     }
  34.     else
  35.     {
  36.         if(lpos<=tre[no].mid && rpos>tre[no].mid)
  37.         {
  38.             if(flag)
  39.                 return max(ask(flag,no*2,lpos,tre[no].mid),ask(flag,no*2+1,tre[no].mid+1,rpos));
  40.             else
  41.                 return min(ask(flag,no*2,lpos,tre[no].mid),ask(flag,no*2+1,tre[no].mid+1,rpos));
  42.         }
  43.         else
  44.         {
  45.             if(rpos<=tre[no].mid)
  46.                 return ask(flag,no*2,lpos,rpos);
  47.             else
  48.                 return ask(flag,no*2+1,lpos,rpos);
  49.         }
  50.     }
  51. }
  52. int main()
  53. {
  54.     int k;
  55.     scanf("%d%d",&n,&k);
  56.     for(int i=1;i<=n;i++)
  57.         scanf("%d",num+i);
  58.     build(1,1,n);
  59.     for(int i=1;i+k-1<=n;i++)
  60.     {
  61.         printf("%d",ask(0,1,i,i+k-1));
  62.         if(i+k>n)
  63.             printf("\n");
  64.         else
  65.             printf(" ");
  66.     }
  67.     for(int i=1;i+k-1<=n;i++)
  68.     {
  69.         printf("%d",ask(1,1,i,i+k-1));
  70.         if(i+k>n)
  71.             printf("\n");
  72.         else
  73.             printf(" ");
  74.     }
  75.     return 0;
  76. }

单调队列：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. struct Node
  6. {
  7.     int no,val;
  8. }q[1000005];
  9. int num[1000005];
  10. int l,r,n;
  11. int main()
  12. {
  13.     int k;
  14.     scanf("%d%d",&n,&k);
  15.     for(int i=1;i<=n;i++)
  16.         scanf("%d",num+i);
  17.     l=r=0;
  18.     for(int i=1;i<k;i++)
  19.     {
  20.         while(r>l && q[r-1].val>num[i])
  21.             r--;
  22.         q[r].no=i;
  23.         q[r].val=num[i];
  24.         r++;
  25.     }
  26.     for(int i=k;i<=n;i++)
  27.     {
  28.         if(r>l && q[l].no==i-k)
  29.             l++;
  30.         while(r>l && q[r-1].val>num[i])
  31.             r--;
  32.         q[r].no=i;
  33.         q[r].val=num[i];
  34.         r++;
  35.         printf("%d",q[l].val);
  36.         if(i==n)
  37.             printf("\n");
  38.         else
  39.             printf(" ");
  40.     }
  41.     l=r=0;
  42.     for(int i=1;i<k;i++)
  43.     {
  44.         while(r>l && q[r-1].val<num[i])
  45.             r--;
  46.         q[r].no=i;
  47.         q[r].val=num[i];
  48.         r++;
  49.     }
  50.     for(int i=k;i<=n;i++)
  51.     {
  52.         if(r>l && q[l].no==i-k)
  53.             l++;
  54.         while(r>l && q[r-1].val<num[i])
  55.             r--;
  56.         q[r].no=i;
  57.         q[r].val=num[i];
  58.         r++;
  59.         printf("%d",q[l].val);
  60.         if(i==n)
  61.             printf("\n");
  62.         else
  63.             printf(" ");
  64.     }
  65.     return 0;
  66. }

G Bad Hair Day (POJ - 3250)

题意：

    有N(N<=80000)头奶牛，第i头奶牛的身高为hi(1<=hi<=10^9)，奶牛a可以看到奶牛b必须满足3个条件：(1)b在a的右边；(2)ha>hb；(3)对于a<i<b，ha>hi。问每头奶牛能看到的奶牛的总和为多少。

题解：

    我们可以把问题转化为，对于第i头牛，它左边有多少头牛能看到它。要用到单调栈。
    单调栈和单调队列类似，只是没有了队列队首的概念，入栈和出栈都在栈顶完成。以单调递减栈为例，当新点入栈的时候，栈顶的点如果权值大于当前点，就将新点入队；否则先将栈顶的点出栈，直到栈为空或者当前的栈顶大于新点。
    这题我们维护一个单调递减队列，对于第i头牛，能看到它的牛为在它进栈的时候，还留在栈内的其他牛。考虑到第i头牛之前，栈里装的是能看到第i-1头牛的牛，如果栈里有牛的高度小于等于第i头牛，那么他们一定看不到第i头牛，也没机会看到第i头牛右边的任何牛，所以可以直接让他出栈。剩下来的牛，就一定能看到第i头牛。在这个过程中，因为第i头牛入栈的时候他下面都是比第i头牛高的牛，当第i+1头牛入栈的时候，下面又都是比第i+1头牛高的牛，所以在栈里，从底向顶牛的高度是递减的。所以每次我们只要从栈顶开始判断是否让牛出栈，就能保证栈里剩下的牛高度都超过新来的牛。因为每头牛是看不到自己的，所以要在新牛可以进栈但是还没进栈的时候更新答案。
    时间复杂度o(N)，空间复杂度o(N)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. int q[80005];
  6. int num[80005];
  7. int r,n;
  8. long long ans;
  9. int main()
  10. {
  11.     scanf("%d",&n);
  12.     for(int i=1;i<=n;i++)
  13.         scanf("%d",num+i);
  14.     ans=0;
  15.     r=0;
  16.     for(int i=1;i<=n;i++)
  17.     {
  18.         while(r && q[r-1]<=num[i])
  19.             r--;
  20.         ans+=1LL*r;
  21.         q[r++]=num[i];
  22.     }
  23.     printf("%lld\n",ans);
  24.     return 0;
  25. }

H Stripies (POJ - 1862)

题意：

    有N(1<=N<=100)个神奇的生物(百度也没告诉我是啥)，每个生物的初始重量为1到10000内的整数，两个生物碰♂撞后就会合体，重量变为两个生物原本的重量的乘积开平方的两倍，每次只会有两个生物相撞，问最后剩下一个生物时，重量最小是多少。输出保留三位小数。

题解：

    假设A、B、C三个生物的重量分别是a、b、c，如果A先和B撞再和C撞，最后的重量就是2*sqrt(2*sqrt(a*b)*c)，它的平方是8*sqrt(a*b)*c，四次方是64*a*b*c^2，而如果A撞C再撞B，四次方就是64*a*c*b^2，推广到多个也有类似的情况，系数和顺序无关，而处于越外层的项也就是越晚被合体的生物，指数越大。所以如果要让最后的重量最小，我们就让重量大的生物先碰撞。
    所以我们用一个重量大优先的优先队列装这些生物，每次从队首取出重量最大的两个生物，合体后再放回优先队列中，直到队列中只剩一个生物。
    时间复杂度o(N*log(N))，空间复杂度o(N)。
    PS：因为合体后的重量一定大于两者中重量较小的那个，所以也一定大于剩下的生物，其实从打到小排个序然后从前面开始合体就行了，时间复杂度是一样的。。。不过我就是要让你们练习怎么用优先队列~
    再PS：优先队列的原理是最小堆，有兴趣的同学可以去了解一下，竞赛上只要求掌握使用、修改优先级还有复杂度计算。对于实现不做要求，一般直接使用库函数。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<queue>
  5. using namespace std;
  6. priority_queue <double> pq;
  7. int main()
  8. {
  9.     int n;
  10.     double x,a,b;
  11.     scanf("%d",&n);
  12.     for(int i=1;i<=n;i++)
  13.     {
  14.         scanf("%lf",&x);
  15.         pq.push(x);
  16.     }
  17.     while(pq.size()>1)
  18.     {
  19.         a=pq.top();
  20.         pq.pop();
  21.         b=pq.top();
  22.         pq.pop();
  23.         x=2.0*sqrt(a*b);
  24.         pq.push(x);
  25.     }
  26.     x=pq.top();
  27.     pq.pop();
  28.     printf("%.3f\n",x);
  29.     return 0;
  30. }

I Black Box (POJ - 1442)

题意：

    一开始有一个空盒子，把M(30000)个数依次放入盒子，第i个数为Ai(-2*10^9<=Ai<=2*10^9)，有N(N<=30000)个询问，第i个询问为ui，表示在放入第ui个数后询问当前盒内第i小的数为多少。题目保证u不减，并且ui>=i。

题解：

    动态区间第k大，可以用主席树(滑稽
    实际上本题有几个关键点，首先每次询问的区间，左端点都是1，右端点不减，也就是说之后的询问只要考虑加入新的数不用考虑删除之前的数，第二每次询问的k都比上一次加一。
    所以我们实际上可以用两个优先队列来解决。
    pq1为数值大优先的优先队列，pq2为数值小优先的优先队列。我们用pq1来装当前盒子内最小的k-1个数，pq2来装剩下的数，这样pq1的队首就是盒子里的第k-1小的数，而pq2的队首是盒子里剩下数中最小的也就是盒子里第k小的数。如果我们要往盒子内加入一个数，我们可以通过这个数和pq2队首的大小比较，确定这个新数是前k-1小之内还是第k小或者更大，如果是前k-1小也就是说原来的第k-1小变成第k小，那么把pq1原本的队首弹出，压入pq2，再把新数压入pq1；否则直接把新数压入pq2。当压入的是第u[k]项时，因为pq2的队首就是盒中第k大的数，把他输出再将它从pq2中弹出，压入pq1，令k=k+1，就完成了k加一的全部维护。重复以上操作直到k超过n。
    时间复杂度o((N+M)*log(M))，空间复杂度o(M+N)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. #include<queue>
  5. using namespace std;
  6. struct cmp1
  7. {
  8.     bool operator() (int x1,int x2)
  9.     {
  10.         if(x1>x2)
  11.             return 1;
  12.         else
  13.             return 0;
  14.     }
  15. };
  16. priority_queue <int,vector<int>,less<int> > pq1;
  17. priority_queue <int,vector<int>,cmp1> pq2;
  18. int num[30005],m,n,u[30005];
  19. int main()
  20. {
  21.     int temp,now;
  22.     scanf("%d%d",&m,&n);
  23.     for(int i=1;i<=m;i++)
  24.         scanf("%d",num+i);
  25.     for(int i=1;i<=n;i++)
  26.         scanf("%d",u+i);
  27.     now=1;
  28.     for(int i=1;i<=n;i++)
  29.     {
  30.         while(now<=u[i])
  31.         {
  32.             if(!pq1.empty() && (temp=pq1.top(),temp>num[now]))
  33.             {
  34.                 pq1.pop();
  35.                 pq1.push(num[now]);
  36.                 pq2.push(temp);
  37.             }
  38.             else
  39.                 pq2.push(num[now]);
  40.             now++;
  41.         }
  42.         temp=pq2.top();
  43.         pq2.pop();
  44.         printf("%d\n",temp);
  45.         pq1.push(temp);
  46.     }
  47.     return 0;
  48. }

J Virtual Friends (HDU - 3172)

题意：

    有F(F<=100000)条信息，每条信息包含两个姓名，表示这两个人成为了朋友，朋友是双向而且传递的关系。姓名不超过20个字母(区分大小写)。问每一条信息之后，当前提及的这两个人所处的朋友网有多大。
    多组数据，每组数据有T个独立的样例，每个样例有F条信息(太坑了)。

题解：

    用并查集维护朋友网关系，每个点有一个权值表示以他为祖先的并查集的大小，合并并查集的同时对权值进行修改。
    因为输入的是姓名，采用string来输入，用map把字符串映射成序号，便于并查集的操作。map和set的内部原理都是红黑树，是一种平衡树，有兴趣的同学可以自己去了解一下。
    PS：因为是多组数据，注意清空map。string类的头文件是<string>而不是<cstring>，两者是不同的库。
    时间复杂度o(T*F*log(F))，空间复杂度o(F)。

代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<string>
  4. #include<map>
  5. using namespace std;
  6. map <string,int> mp;
  7. string a,b;
  8. int nums;
  9. int root[200005],num[200005];
  10. int findr(int now)
  11. {
  12.     if(root[now]==now)
  13.         return now;
  14.     else
  15.         return root[now]=findr(root[now]);
  16. }
  17. int main()
  18. {
  19.     int T,F,x,y;
  20.     while(~scanf("%d",&T))
  21.     {
  22.         while(T--)
  23.         {
  24.             scanf("%d",&F);
  25.             mp.clear();
  26.             nums=0;
  27.             while(F--)
  28.             {
  29.                 cin>>a>>b;
  30.                 if(mp[a]==0)
  31.                 {
  32.                     nums++;
  33.                     mp[a]=nums;
  34.                     root[nums]=nums;
  35.                     num[nums]=1;
  36.                 }
  37.                 if(mp[b]==0)
  38.                 {
  39.                     nums++;
  40.                     mp[b]=nums;
  41.                     root[nums]=nums;
  42.                     num[nums]=1;
  43.                 }
  44.                 x=findr(mp[a]);
  45.                 y=findr(mp[b]);
  46.                 if(x!=y)
  47.                 {
  48.                     root[y]=x;
  49.                     num[x]+=num[y];
  50.                 }
  51.                 printf("%d\n",num[x]);
  52.             }
  53.         }
  54.     }
  55.     return 0;
  56. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注