[关闭]
@Asuna 2017-03-29T20:51:32.000000Z 字数 8329 阅读 790

2016寒假集训队第二次作业

题解

Problem A:敌兵布阵

题意：一个队列，要求满足能单点加减和区间和查询。

题解：裸线段树，update改变单点值即可。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<algorithm>
  6. using namespace std;
  7. struct node
  8. {
  9.     int l,r,sum,mid;
  10. }f[1000005];
  11. int a[100000],ans,t,n,d=1,x,y;
  12. char s[16];
  13. void uproot(int n)
  14. {
  15.     f[n].sum=f[2*n].sum+f[2*n+1].sum;
  16. }
  17. void built(int l,int r,int n)
  18. {
  19.     f[n].mid=(l+r)/2;
  20.     f[n].r=r;
  21.     f[n].l=l;
  22.     f[n].sum=0;
  23.     if (l==r)
  24.     {
  25.         f[n].sum=a[l];
  26.         return ;
  27.     }
  28.     built(l,f[n].mid,2*n);
  29.     built(f[n].mid+1,r,2*n+1);
  30.     uproot(n);
  31. }
  33. void update(int c,int q,int val)
  34. {
  35.     if (f[c].l==q && f[c].r==q)
  36.     {
  37.         f[c].sum+=val;
  38.         return ;
  39.     }
  40.     if (q<=f[c].mid) update(2*c,q,val);
  41.     else update(2*c+1,q,val);
  42.     uproot(c);
  43. }
  45. void query(int c,int a,int b)
  46. {
  47.     //cout<<c<<endl;
  48.    // cout<<f[c].l<<" "<<f[c].r<<endl;
  49.    // cout<<"  "<<a<<" "<<b<<endl;
  50.     if (f[c].l>=a && f[c].r<=b)
  51.     {
  52.      //   cout<<"!!!"<<endl;
  53.         ans+=f[c].sum;
  54.         //cout<<ans<<endl;
  55.         return ;
  56.         //cout<<"?????"<<endl;
  57.     }
  58.     if (b<=f[c].mid) query(2*c,a,b);
  59.     else if (a>f[c].mid) query(2*c+1,a,b);
  60.     else
  61.     {
  62.         query(2*c,a,f[c].mid);
  63.         query(2*c+1,f[c].mid+1,b);
  64.     }
  65. }
  67. int main()
  68. {
  69.     ios::sync_with_stdio(false);
  70.     cin>>t;
  71.     while (t--)
  72.     {
  73.         cin>>n;
  74.         for (int i=1; i<=n; i++)
  75.             cin>>a[i];
  76.         built(1,n,1);
  77.         printf("Case %d:\n",d++);
  78.         //cout<<"Case "<<d++<<":"<<endl;
  79.         while (cin>>s)
  80.         {
  81.             //cout<<s<<endl;
  82.             if (s[0]=='E') break;
  83.             cin>>x>>y;
  84.             ans=0;
  85.             if (s[0]=='A') update(1,x,y);
  86.             else if(s[0]=='S') update(1,x,-y);
  87.             else if(s[0]=='Q')
  88.             {
  89.                 query(1,x,y);
  90.                 //cout<<ans<<endl;
  91.                 printf("%d\n",ans);
  92.             }
  93.         }
  94.     }
  95.     return 0;
  96. }

Problem B：Color the ball

题意：一个队列，要求完成区间+1和单点查询。

题解：可以用线段树的段更新点询问，每次把a,b全部+1，最后全部查询一遍就行了。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. struct node
  5. {
  6.     int l,r,cnt;
  7. }p[1000010];
  8. int mid,n,a,b;
  10. void build(int l,int r,int rt)
  11. {
  12.     p[rt].l=l;
  13.     p[rt].r=r;
  14.     p[rt].cnt=0;
  15.     if (l==r) return;
  16.     int mid=(l+r)/2;
  17.     build(l,mid,rt*2);
  18.     build(mid+1,r,rt*2+1);
  19. }
  21. void update(int l,int r,int rt)
  22. {
  23.     if (l==p[rt].l && r==p[rt].r)
  24.     {
  25.         p[rt].cnt++;
  26.         return;
  27.     }
  28.     int mid=(p[rt].l+p[rt].r)/2;
  29.     if (r<=mid) update(l,r,rt*2);
  30.     else if (l>mid) update(l,r,rt*2+1);
  31.     else
  32.     {
  33.         update(l,mid,rt*2);
  34.         update(mid+1,r,rt*2+1);
  35.     }
  36. }
  38. int query(int i,int rt)
  39. {
  40.     if (p[rt].l==p[rt].r) return p[rt].cnt;
  41.     if (p[rt].cnt)
  42.     {
  43.         p[rt*2].cnt+=p[rt].cnt;
  44.         p[rt*2+1].cnt+=p[rt].cnt;
  45.         p[rt].cnt=0;
  46.     }
  47.     mid=(p[rt].l+p[rt].r)/2;
  48.     if (i<=mid)
  49.         return query(i,rt*2);
  50.     else
  51.         return query(i,rt*2+1);
  52. }
  54. int main()
  55. {
  56.     while (cin>>n)
  57.     {
  58.         if (n==0) break;
  59.         build(1,n,1);
  60.         for (int i=1; i<=n; i++)
  61.         {
  62.             cin>>a>>b;
  63.             update(a,b,1);
  64.         }
  65.         for (int i=1; i<n; i++)
  66.             cout<<query(i,1)<<" ";
  67.         cout<<query(n,1)<<endl;
  68.     }
  69.     return 0;
  70. }

Problem C：Mayor's posters

题意：有n张海报，按给出的顺序依次贴在一面墙上，第i张海报的左右端点为li和ri，问最终能看到几张不同的海报。

题解：由于li和ri的范围太大（大的超出想象），于是看了js的题解之后才知道可以离散化解决，也就是通过压缩没数据的空出空间来缩小li和ri的范围，比如[1,2],[2,3],[1,5],[4,9],离散化就是先记录每个端点对应的区间，然后对每个端点排序，排序后为1,1,2,2,3,4,5,9。之后从1~9进行压缩，这里1,2,3,4,5都有数，因此无法压缩，只有9可以压缩成6，然后放回原先区间则离散化后的区间为[1,2],[2,3],[1,5],[4,6]。在离散化之后只需要用线段树从后往前贴，查询到某块区域被完全覆盖了就返回即可。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. int flag,n,t,ans;
  7. struct node
  8. {
  9.     int l,r;
  10.     bool vis;//判断是不是完全覆盖
  11. }tree[400010];
  13. struct point
  14. {
  15.     int id,x;
  16. }a[400010];
  18. int cmp1(point a,point b)
  19. {
  20.     return a.x<b.x;
  21. }
  23. int cmp2(point a,point b)
  24. {
  25.     if (a.id==b.id)
  26.         return a.x<b.x;
  27.     return a.id>b.id;
  28. }
  30. void PushUp(int rt)
  31. {
  32.     tree[rt].vis=tree[(rt*2)].vis && tree[(rt*2+1)].vis;
  33. }
  35. void build(int l,int r,int rt)
  36. {
  37.     tree[rt].l=l;
  38.     tree[rt].r=r;
  39.     tree[rt].vis=0;
  40.     if (tree[rt].l==tree[rt].r) return;
  41.     int mid=(l+r)/2;
  42.     build(l,mid,(rt*2));
  43.     build(mid+1,r,(rt*2+1));
  44. }
  46. void query(int l,int r,int rt)
  47. {
  48.     if (tree[rt].vis) return ;
  49.     if (tree[rt].l==l && tree[rt].r==r)
  50.     {
  51.         tree[rt].vis=1;
  52.         flag=1;
  53.         return ;
  54.     }
  55.     int mid=(tree[rt].l+tree[rt].r)/2;
  56.     if (r<=mid)
  57.         query(l,r,(rt*2));
  58.     else
  59.     if (l>=mid+1)
  60.         query(l,r,(rt*2+1));
  61.     else
  62.     {
  63.         query(l,mid,(rt*2));
  64.         query(mid+1,r,(rt*2+1));
  65.     }
  66.     PushUp(rt);
  67. }
  69. int main()
  70. {
  71.     cin>>t;
  72.     while (t--)
  73.     {
  74.         cin>>n;
  75.         for (int i=0; i<2*n; i+=2)
  76.         {
  77.             scanf("%d%d",&a[i].x,&a[i+1].x);
  78.             a[i].id=a[i+1].id=i;
  79.         }
  80.         sort(a,a+2*n,cmp1);
  81.         int tot=0,pre=0;
  82.         //离散
  83.         for(int i=0; i<2*n; i++)
  84.         {
  85.             if (a[i].x==pre) a[i].x=tot;
  86.             else
  87.             {
  88.                 pre=a[i].x;
  89.                 tot++;
  90.                 a[i].x=tot;
  91.             }
  92.         }
  93.         build(1,2*n,1);
  94.         sort(a,a+2*n,cmp2);     //排序，从后往前贴
  95.         ans=0;
  96.         for(int i=0;i<2*n;i+=2)
  97.         {
  98.             int l=a[i].x,r=a[i+1].x;
  99.             flag=0;
  100.             query(l,r,1);
  101.             if (flag) ans++;
  102.         }
  103.         cout<<ans<<endl;
  104.     }
  105.     return 0;
  106. }

Problem D:Tunnel Warfare

题意：一条线上有n个点从1~n。
D x是破坏x这个点。
Q x是表示查询以x所在的最长的连续的点的个数
R是恢复上一次破坏的点。

题解：设置一个lc记录区间左端点开始的最大连续个数，rc 记录区间右端点开始的最大的连续个数,sc表示该区间最大的连续点的个数。多维护一个栈来保存被破坏的点，以便于之后可能的修复。每次查询分别往左右子树找最大连续个数最后用max（lc，rc）来更新sc。

参考代码：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<stack>
  6. using namespace std;
  7. int lc[400005],rc[400005],sc[400005],n,m,x;
  8. char c;
  9. stack<int> a;
  10. void uppush(int s,int m)
  11. {
  12.     lc[s]=lc[s*2];
  13.     rc[s]=rc[s*2+1];
  14.     if (lc[s]==m-(m/2)) lc[s]+=lc[s*2+1];
  15.     if (rc[s]==m/2) rc[s]+=rc[s*2];
  16.     sc[s]=max(lc[s*2+1]+rc[s*2],max(sc[s*2],sc[s*2+1]));
  17. }
  19. void build(int l,int r,int s)
  20. {
  21.     lc[s]=rc[s]=sc[s]=r-l+1;
  22.     if (l==r) return ;
  23.     int mid=(l+r)/2;
  24.     build(l,mid,s*2);
  25.     build(mid+1,r,s*2+1);
  26. }
  28. void update(int p,int c,int l,int r,int s)
  29. {
  30.     if (l==r)
  31.     {
  32.         if (c)
  33.         {
  34.             lc[s]=rc[s]=sc[s]=1;
  35.             return ;
  36.         }
  37.         else
  38.         {
  39.             lc[s]=rc[s]=sc[s]=0;
  40.             return ;
  41.         }
  42.     }
  43.     int mid=(l+r)/2;
  44.     if (p<=mid) update(p,c,l,mid,s*2);
  45.     else update(p,c,mid+1,r,s*2+1);
  46.     uppush(s,r-l+1);
  47. }
  49. int query(int p,int l,int r,int s)
  50. {
  51.     if (l==r || sc[s]==0 || sc[s]==r-l+1)
  52.         return sc[s];
  53.     int mid=(l+r)/2;
  54.     if (p<=mid)
  55.     {
  56.         if (p>=mid-rc[s*2]+1)
  57.             return rc[s*2]+query(mid+1,mid+1,r,s*2+1);
  58.         else
  59.             return query(p,l,mid,s*2);
  60.     }
  61.     else
  62.     {
  63.         if (p<=mid+lc[s*2+1])
  64.             return lc[s*2+1]+query(mid,l,mid,s*2);
  65.         else return query(p,mid+1,r,s*2+1);
  66.     }
  67. }
  69. int main()
  70. {
  71.     while(cin>>n>>m)
  72.     {
  73.         build(1,n,1);
  74.         while (m--)
  75.         {
  76.             //getchar();
  77.             cin>>c;
  78.             if (c!='R')
  79.                 cin>>x;
  80.             if (c=='D')
  81.             {
  82.                 update(x,0,1,n,1);
  83.                 a.push(x);
  84.             }
  85.             if (c=='R')
  86.             {
  87.                 update(a.top(),1,1,n,1);
  88.                 a.pop();
  89.             }
  90.             if (c=='Q') cout<<query(x,1,n,1)<<endl;
  91.         }
  92.     }
  93.     return 0;
  94. }

Problem E：A Simple Problem with Integers

题意：给定一个数列，有如下两个操作：
(1)C a b c，表示第a个到第b个数全部加上c
(2)Q a b，表示询问第a个数到b个数的和

题解：普通的区间修改和区间和询问。注意范围可能比int大，要用long long统计结果。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. int num[100005],t,n,x,y,z;
  7. long long sum[400005],a[400005];
  8. char c[2];
  9. void uproot(int s)
  10. {
  11.     sum[s]=sum[s*2]+sum[s*2+1];
  12. }
  14. void pushdown(int s,int l)
  15. {
  16.     if (a[s])
  17.     {
  18.         a[s*2]+=a[s];
  19.         a[s*2+1]+=a[s];
  20.         sum[s*2]+=a[s]*(l-(l/2));
  21.         sum[s*2+1]+=a[s]*(l/2);
  22.         a[s]=0;
  23.     }
  24. }
  26. void build(int s,int l,int r)
  27. {
  28.     if (l==r)
  29.     {
  30.         cin>>sum[s];
  31.         return ;
  32.     }
  33.     int mid=(l+r)/2;
  34.     build(s*2,l,mid);
  35.     build(s*2+1,mid+1,r);
  36.     uproot(s);
  37. }
  39. void update(int c,int x,int y,int l,int r,int s)
  40. {
  41.     if (l>=x && r<=y)
  42.     {
  43.         a[s]+=c;
  44.         sum[s]+=c*(r-l+1);
  45.         return ;
  46.     }
  47.     pushdown(s,r-l+1);
  48.     int mid=(l+r)/2;
  49.     if (x<=mid)
  50.         update(c,x,y,l,mid,s*2);
  51.     if (y>mid)
  52.         update(c,x,y,mid+1,r,s*2+1);
  53.     uproot(s);
  54. }
  56. long long query(int x,int y,int l,int r,int s)
  57. {
  58.     if (l>=x && r<=y)
  59.         return sum[s];
  60.     pushdown(s,r-l+1);
  61.     int mid=(l+r)>>1;
  62.     long long ans=0;
  63.     if(x<=mid)
  64.         ans+=query(x,y,l,mid,s*2);
  65.     if(y>mid)
  66.         ans+=query(x,y,mid+1,r,s*2+1);
  67.     return ans;
  68. }
  70. int main()
  71. {
  72.     std::ios::sync_with_stdio(false);
  73.     cin>>n>>t;
  74.     build(1,1,n);
  75.     while(t--)
  76.     {
  77.         cin>>c;
  78.         if (c[0]=='C')
  79.         {
  80.             cin>>x>>y>>z;
  81.             update(z,x,y,1,n,1);
  82.         }
  83.         else
  84.         {
  85.             cin>>x>>y;
  86.             cout<<query(x,y,1,n,1)<<endl;
  87.         }
  88.     }
  89.     return 0;
  90. }

Problem F:Sasha and Array

题意：给定一个数列，有如下两种操作：
(1)1 l r x，表示第l个到第r个数全部加上x
(2)2 l r，表示询问第l个数到r个数对应斐波那契的第ai项的和，输出mod10^9+7。

题解：呃啊。。寒假的时候看到这题巨烦。。线段树+斐波那契简直恶心就没做。。现在想来应该是线段树+矩阵快速幂（别问我为什么想到矩阵。。因为它是斐波那契。。）总的来说就是维护一个经典的斐波那契矩阵（2*2的（1，0，0，1））。于是用线段树存储矩阵,每次更新加x就可以用乘以（1，0，0，1）^x代替

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<cmath>
  6. #include<algorithm>
  7. using namespace std;
  8. const long long mod=1e9+7;
  9. int n,m,op,a,b;
  10. long long x;
  11. struct Mat
  12. {
  13.     long long x[2][2];
  14.     void init()
  15.     {
  16.         x[0][0]=x[1][1]=1;
  17.         x[1][0]=x[0][1]=0;
  18.     }
  19.     Mat operator*(const Mat& m2)const
  20.     {
  21.         Mat m;
  22.         m.x[0][0]=m.x[0][1]=m.x[1][0]=m.x[1][1]=0;
  23.         for(int k=0;k<2;k++)
  24.             for(int i=0;i<2;i++)
  25.                 for(int j=0;j<2;j++)
  26.                     m.x[i][j]=(m.x[i][j]+x[i][k]*m2.x[k][j])%mod;
  27.         return m;
  28.     }
  29.     Mat operator+(const Mat& m2)const{
  30.         Mat m;
  31.         for(int i=0;i<2;i++)
  32.             for(int j=0;j<2;j++)
  33.                 m.x[i][j]=(x[i][j]+m2.x[i][j])%mod;
  34.         return m;
  35.     }
  36. };
  37. Mat sum[400010],add[400010];
  38. Mat pow(long long n)
  39. {
  40.     Mat m,ret;
  41.     m.x[0][0]=1;m.x[0][1]=1;
  42.     m.x[1][0]=1;m.x[1][1]=0;
  43.     ret.init();
  44.     while(n)
  45.     {
  46.         if (n&1) ret=ret*m;
  47.         m=m*m;
  48.         n>>=1;
  49.     }
  50.     return ret;
  51. }
  53. long long solve(long long n)
  54. {
  55.     Mat ret=pow(n);
  56.     return ret.x[0][0];
  57. }
  59. void uppush(int rt)
  60. {
  61.     sum[rt]=sum[rt*2]+sum[rt*2+1];
  62. }
  64. void build(int l,int r,int rt)
  65. {
  66.     sum[rt].init();
  67.     add[rt].init();
  68.     if(l==r)
  69.     {
  70.         long long x;
  71.         cin>>x;
  72.         sum[rt]=pow(x-1);
  73.         return;
  74.     }
  75.     int m=(l+r)/2;
  76.     build(l,m,rt*2);
  77.     build(m+1,r,rt*2+1);
  78.     uppush(rt);
  79. }
  81. void pushdown(int rt)
  82. {
  83.     sum[rt*2]=sum[rt*2]*add[rt];
  84.     sum[rt*2+1]=sum[rt*2+1]*add[rt];
  85.     add[rt*2]=add[rt*2]*add[rt];
  86.     add[rt*2+1]=add[rt*2+1]*add[rt];
  87.     add[rt].init();
  88. }
  90. void update(int L,int R,Mat c,int l,int r,int rt)
  91. {
  92.     if (L<=l && R>=r)
  93.     {
  94.         sum[rt]=sum[rt]*c;
  95.         add[rt]=add[rt]*c;
  96.         return;
  97.     }
  98.     pushdown(rt);
  99.     int m=(l+r)/2;
  100.     if(L<=m) update(L,R,c,l,m,rt*2);
  101.     if(R>m) update(L,R,c,m+1,r,rt*2+1);
  102.     uppush(rt);
  103. }
  105. long long query(int L,int R,int l,int r,int rt)
  106. {
  107.     if (L<=l && R>=r)
  108.     {
  109.         return sum[rt].x[0][0];
  110.     }
  111.     pushdown(rt);
  112.     int mid=(l+r)/2;
  113.     long long ret=0;
  114.     if (L<=mid) ret=(ret+query(L,R,l,mid,rt*2))%mod;
  115.     if (R>mid) ret=(ret+query(L,R,mid+1,r,rt*2+1))%mod;
  116.     uppush(rt);
  117.     return ret;
  118. }
  120. int main()
  121. {
  122.     while(cin>>n>>m)
  123.     {
  124.         build(1,n,1);
  125.         while(m--)
  126.         {
  127.             scanf("%d%d%d",&op,&a,&b);
  128.             if (op==1)
  129.             {
  130.                 cin>>x;
  131.                 Mat m=pow(x);
  132.                 update(a,b,m,1,n,1);
  133.             }
  134.             else cout<<query(a,b,1,n,1)<<endl;
  135.         }
  137.     }
  138.     return 0;
  139. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注