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

萌新集中营第一期

题解


题目

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. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注