[关闭]
@meredith233 2017-06-01T21:20:20.000000Z 字数 4390 阅读 787

2017/5/8

homework

A - Hotel

题目大意：

有一家旅馆，有标号1~n个房间。现给定两种操作。1为给定一个人数，求能放下这个人数的开始位置（必须连续放置），且这个位置尽量小。2为将区间i到j清空（check out）。

解题思路：

线段树区间合并。通过sum记录区间内空房间数，lsum记录从某点向右有多少个空房间，rsum记录从某点向左有多少个空房间，vis记录某区间房间是否被占用（0表没有，1表有，-1表示没有操作）。

AC代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <queue>
  6. #define INF 0x3f3f3f
  7. #define MAX 50005
  8. using namespace std;
  9. int lsum[MAX*4],rsum[MAX*4],sum[MAX*4],vis[MAX*4];
  10. int n,m;
  11. void build(int num,int l,int r)
  12. {
  13.     vis[num]=-1;
  14.     lsum[num]=rsum[num]=sum[num]=r-l+1;
  15.     if(l==r)
  16.         return;
  17.     int mid=(l+r)>>1;
  18.     build(num<<1,l,mid);
  19.     build(num<<1|1,mid+1,r);
  20. }
  21. void pushdown(int num,int k)
  22. {
  23.     if(vis[num]!=-1)
  24.     {
  25.         vis[num<<1]=vis[num<<1|1]=vis[num];
  26.         lsum[num<<1]=rsum[num<<1]=sum[num<<1]=vis[num]?0:(k-(k>>1));
  27.         lsum[num<<1|1]=rsum[num<<1|1]=sum[num<<1|1]=vis[num]?0:k>>1;
  28.         vis[num]=-1;
  29.     }
  30. }
  31. void pushup(int num,int k)
  32. {
  33.     lsum[num]=lsum[num<<1];
  34.     rsum[num]=rsum[num<<1|1];
  35.     if(lsum[num]==(k-(k>>1)))
  36.         lsum[num]+=lsum[num<<1|1];
  37.     if(rsum[num]==k>>1)
  38.         rsum[num]+=rsum[num<<1];
  39.     sum[num]=max(rsum[num<<1]+lsum[num<<1|1],max(sum[num<<1],sum[num<<1|1]));
  40. }
  41. void update(int num,int l,int r,int x,int y,int z)
  42. {
  43.     if(x<=l&&y>=r)
  44.     {
  45.         lsum[num]=rsum[num]=sum[num]=z?0:(r-l+1);
  46.         vis[num]=z;
  47.         return;
  48.     }
  49.     pushdown(num,r-l+1);
  50.     int mid=(l+r)>>1;
  51.     if(x<=mid)
  52.         update(num<<1,l,mid,x,y,z);
  53.     if(y>mid)
  54.         update(num<<1|1,mid+1,r,x,y,z);
  55.     pushup(num,r-l+1);
  56. }
  57. int query(int num,int l,int r,int x)
  58. {
  59.     if(l==r)
  60.         return l;
  61.     pushdown(num,r-l+1);
  62.     int mid=(l+r)>>1;
  63.     if(sum[num<<1]>=x)
  64.         return query(num<<1,l,mid,x);
  65.     else if(rsum[num<<1]+lsum[num<<1|1]>=x)
  66.         return mid-rsum[num<<1]+1;
  67.     else
  68.         return query(num<<1|1,mid+1,r,x);
  69. }
  70. int main()
  71. {
  72.     while(~scanf("%d%d",&n,&m))
  73.     {
  74.         build(1,1,n);
  75.         while(m--)
  76.         {
  77.             int a,b,c;
  78.             scanf("%d",&a);
  79.             if(a==1)
  80.             {
  81.                 scanf("%d",&b);
  82.                 if(sum[1]<b)
  83.                     printf("0\n");
  84.                 else
  85.                 {
  86.                     int pos=query(1,1,n,b);
  87.                     printf("%d\n",pos);
  88.                     update(1,1,n,pos,pos+b-1,1);
  89.                 }
  90.             }
  91.             else if(a==2)
  92.             {
  93.                 scanf("%d%d",&b,&c);
  94.                 update(1,1,n,b,b+c-1,0);
  95.             }
  96.         }
  97.     }
  98.     return 0;
  99. }

B - A Corrupt Mayor's Performance Art

题目大意：

有一堵墙，有30种颜色标号1-30，墙的默认颜色为2号，现给定两种操作，一为给i到j区间涂上一种颜色，二位查询i到j区间共涂有多少种颜色。

解题思路：

线段树，通过位操作给定(1)<<(i)为颜色值保存，向上更新时进行按位或运算。更新时直接全部更新为涂上的颜色值即可。（初始化爆炸WA两发）

AC代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <queue>
  6. #define INF 0x3f3f3f
  7. #define MAX 1000005
  8. using namespace std;
  9. int tre[MAX*4];
  10. bool laz[MAX*4];
  11. int n,m;
  12. void build(int num,int l,int r)
  13. {
  14.     if(l==r)
  15.     {
  16.         tre[num]=4;
  17.         return;
  18.     }
  19.     int mid=(l+r)>>1;
  20.     build(num<<1,l,mid);
  21.     build(num<<1|1,mid+1,r);
  22.     tre[num]=tre[num<<1]|tre[num<<1|1];
  23. }
  24. void pushdown(int num)
  25. {
  26.     if(laz[num])
  27.     {
  28.         tre[num<<1]=tre[num];
  29.         tre[num<<1|1]=tre[num];
  30.         laz[num<<1]=true;
  31.         laz[num<<1|1]=true;
  32.         laz[num]=false;
  33.     }
  34. }
  35. void update(int num,int l,int r,int x,int y,int z)
  36. {
  37.     if(x<=l&&y>=r)
  38.     {
  39.         tre[num]=(1<<z);
  40.         laz[num]=true;
  41.         return;
  42.     }
  43.     pushdown(num);
  44.     int mid=(l+r)>>1;
  45.     if(x<=mid)
  46.         update(num*2,l,mid,x,y,z);
  47.     if(y>mid)
  48.         update(num*2+1,mid+1,r,x,y,z);
  49.     tre[num]=tre[num*2]|tre[num*2+1];
  50. }
  51. int query(int num,int l,int r,int x,int y)
  52. {
  53.     if(x<=l&&y>=r)
  54.     {
  55.         return tre[num];
  56.     }
  57.     pushdown(num);
  58.     int mid=(l+r)>>1;
  59.     int ans=0;
  60.     if(x<=mid)
  61.         ans|=query(num*2,l,mid,x,y);
  62.     if(y>mid)
  63.         ans|=query(num*2+1,mid+1,r,x,y);
  64.     return ans;
  65. }
  66. int main()
  67. {
  68.     while(~scanf("%d%d",&n,&m))
  69.     {
  70.         memset(laz,false,sizeof(laz));
  71.         if(n==m&&n==0)
  72.             break;
  73.         build(1,1,n);
  74.         while(m--)
  75.         {
  76.             char c;
  77.             scanf(" %c",&c);
  78.             if(c=='P')
  79.             {
  80.                 int a,b,c;
  81.                 scanf("%d%d%d",&a,&b,&c);
  82.                 update(1,1,n,a,b,c);
  83.             }
  84.             else if(c=='Q')
  85.             {
  86.                 int a,b;
  87.                 scanf("%d%d",&a,&b);
  88.                 int ans=query(1,1,n,a,b);
  89.                 int flag=0;
  90.                 for(int i=1; i<=30; i++)
  91.                 {
  92.                     if(ans>>(i)&1 && flag==0)
  93.                     {
  94.                         printf("%d",i);
  95.                         flag = 1;
  96.                     }
  97.                     else if(ans>>(i)&1)
  98.                         printf(" %d",i);
  99.                 }
  100.                 printf("\n");
  101.             }
  102.         }
  103.     }
  104.     return 0;
  105. }

C - Assignment

题目大意：

n名员工，每人有一个能力值ai。给定一个差值k，为一个连续区间内最大值与最小值之差的最大值，求有多少个区间满足这个情况。

解题思路：

st保存区间最大值与区间最小值。查询部分运用二分。枚举右端点i，如果当前区间满足，则这之间所有端点都可作为左端点，不满足时左端点l移动。

AC代码：

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <cstring>
  5. #include <queue>
  6. #include <cmath>
  7. #define INF 0x3f3f3f
  8. #define MAX 100005
  9. using namespace std;
  10. int ar[MAX];
  11. int n,m;
  12. int dp1[MAX][30];//max
  13. int dp2[MAX][30];//min
  14. void init()
  15. {
  16.     for(int i=0;i<=n;i++)
  17.     {
  18.         dp1[i][0]=ar[i];
  19.         dp2[i][0]=ar[i];
  20.     }
  21.     for(int j=1;(1<<j)<=n;j++)
  22.     {
  23.         for(int i=1;i+(1<<j)-1<=n;i++)
  24.         {
  25.             dp1[i][j]=max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
  26.             dp2[i][j]=min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);
  27.         }
  28.     }
  29. }
  30. int querymin(int l,int r)
  31. {
  32.     int k=(int)(log(double(r-l+1))/log((double)2));
  33.     return min(dp2[l][k],dp2[r-(1<<k)+1][k]);
  34. }
  35. int querymax(int l,int r)
  36. {
  37.     int k=(int)(log(double(r-l+1))/log((double)2));
  38.     return max(dp1[l][k],dp1[r-(1<<k)+1][k]);
  39. }
  40. int main()
  41. {
  42.     int t;
  43.     scanf("%d",&t);
  44.     while(t--)
  45.     {
  46.         scanf("%d%d",&n,&m);
  47.         for(int i=1;i<=n;i++)
  48.             scanf("%d",&ar[i]);
  49.         init();
  50.         long long sum=0;
  51.         int k=1;
  52.         for(int i=1;i<=n;i++)
  53.         {
  54.             int l=k,r=i;
  55.             while(l<=r)
  56.             {
  57.                 int mid=(l+r)>>1;
  58.                 int lo=querymin(mid,i);
  59.                 int ma=querymax(mid,i);
  60.                 int x=ma-lo;
  61.                 if(x>=m)
  62.                     l=mid+1;
  63.                 else if(x<m)
  64.                     r=mid-1;
  65.             }
  66.             k=l;
  67.             sum+=i-l+1;
  68.         }
  69.         printf("%lld\n",sum);
  70.     }
  71.     return 0;
  72. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注