[关闭]
@Asuna 2017-04-22T22:10:02.000000Z 字数 4888 阅读 907

CQUPT 训练题题解 2017/4/10

题解

Problem A:Binary Simulation

题意：一串01序列，两种操作，一种是从i到j取反，一种是问第i个是0还是1.

题解：线段树区间更新，单点查询。把需要翻转的区间标记，记录这个区间的翻转次数，然后向下传标记，查询时只需看看这个点翻转奇数次还是偶数次。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. int tre[400010],lazy[400010],t,n,len,icase;
  6. char op[2],s[100010];
  7. void pushdown(int rt)
  8. {
  9.     //cout<<rt<<endl;
  10.     if (lazy[rt]!=0)
  11.     {
  12.         tre[rt*2]+=lazy[rt];
  13.         tre[rt*2+1]+=lazy[rt];
  14.         lazy[rt*2]+=lazy[rt];
  15.         lazy[rt*2+1]+=lazy[rt];
  16.         lazy[rt]=0;
  17.     }
  18.     return ;
  19. }
  21. void update(int L,int R,int l,int r,int rt)
  22. {
  23.     //cout<<rt<<endl;
  24.     if (L<=l && r<=R)
  25.     {
  26.         tre[rt]++;
  27.         lazy[rt]++;
  28.         return ;
  29.     }
  30.     int mid=(l+r)/2;
  31.     pushdown(rt);
  32.     if (L<=mid) update(L,R,l,mid,rt*2);
  33.     if (mid<R) update(L,R,mid+1,r,rt*2+1);
  34. }
  36. int query(int L,int R,int l,int r,int rt)
  37. {
  38.     //cout<<rt<<endl;
  39.     if (L==l && r==R)
  40.     {
  41.        // cout<<tre[rt]<<endl;
  42.         return tre[rt];
  43.     }
  44.     //cout<<L<<" "<<R<<" "<<tre[rt]<<endl;
  45.     int mid=(l+r)/2,ans=0;
  46.     pushdown(rt);
  47.     if (L<=mid) return query(L,R,l,mid,rt*2);
  48.     if (R>mid) return query(L,R,mid+1,r,rt*2+1);
  49.     return ans;
  50. }
  52. int main()
  53. {
  54.     scanf("%d",&t);
  55.     while (t--)
  56.     {
  57.         scanf("%s%d",s+1,&n);
  58.         len=strlen(s+1);
  59.         printf("Case %d:\n",++icase);
  60.         memset(tre,0,sizeof(tre));
  61.         memset(lazy,0,sizeof(lazy));
  62.         while (n--)
  63.         {
  64.             scanf("%s",op);
  65.             if (op[0]=='I')
  66.             {
  67.                 int l,r;
  68.                 scanf("%d%d",&l,&r);
  69.                 update(l,r,1,len,1);
  70.             }
  71.             else
  72.             {
  73.                 int x,ans;
  74.                 scanf("%d",&x);
  75.                 ans=query(x,x,1,len,1);
  76.                 //cout<<ans<<" "<<s[x]<<endl;
  77.                 if (ans%2!=0)
  78.                 {
  79.                     if (s[x]=='0') printf("%d\n",1);
  80.                     else printf("%d\n",0);
  81.                 }
  82.                 else
  83.                 {
  84.                     if (s[x]=='0') printf("%d\n",0);
  85.                     else printf("%d\n",1);
  86.                 }
  87.             }
  88.         }
  89.     }
  90.     return 0;
  91. }

Problem B:Points in Segments

题意：题意很简单，给n个有序的数，这些数分布在一个坐标轴上。给q次查找，询问在区间x,y中有多少个数据。

题解：寻找这些点中对于每条线段的上下界即可。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. int t,p,q,a[100010],icase;
  6. int find(int x,int y)
  7. {
  8.     int l=0,r=p-1,ret1=-1;
  9.     while(l<=r)
  10.     {
  11.         int mid=(l+r)/2;
  12.         if(a[mid]>=x)
  13.         {
  14.             ret1=mid;
  15.             r=mid-1;
  16.         }
  17.         else l=mid+1;
  18.     }
  19.     l=0;
  20.     r=p-1;
  21.     int ret2=-1;
  22.     while(l<=r)
  23.     {
  24.         int mid=(l+r)/2;
  25.         if(a[mid]<=y)
  26.         {
  27.             ret2=mid;
  28.             l=mid+1;
  29.         }
  30.         else r=mid-1;
  31.     }
  32.     if (ret1==-1 || ret2==-1) return 0;
  33.     return ret2-ret1+1;
  34. }
  36. int main()
  37. {
  38.     scanf("%d",&t);
  39.     while(t--)
  40.     {
  41.         printf("Case %d:\n",++icase);
  42.         scanf("%d%d",&p,&q);
  43.         for (int i=0; i<p; i++) scanf("%d",&a[i]);
  44.         while (q--)
  45.         {
  46.             int x,y;
  47.             scanf("%d%d",&x,&y);
  48.             printf("%d\n",find(x,y));
  49.         }
  50.     }
  51.     return 0;
  52. }

Problem C:Calm Down

题意：给出大圆半径，以及其内的小圆个数，求小圆的半径。

题解：大圆中心A与小圆中心B相连，之后与2小圆交点相连，得到一个垂直三角形。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cmath>
  4. using namespace std;
  5. const double PI=acos(-1.0);
  6. int main()
  7. {
  8.     int cas,i,j=0,n;
  9.     double R,r;
  10.     scanf("%d",&cas);
  11.     while(cas--)
  12.     {
  13.         j++;
  14.         scanf("%lf %d",&R,&n);
  15.         printf("Case %d: ",j);
  16.         r=(R*sin(PI/(n*1.0)))/(1+sin(PI/(n*1.0)));
  17.         printf("%.10lf\n",r);
  18.     }
  19.     return 0;
  20. }

Problem D: Neighbor House

题意：有n个房子，每个房子都可以染红绿蓝三种颜色，并且给出了每个房子染每种颜色费用，相邻房子不能同色，求染完房子的最小费用。

题解：定义dp[i][j]为粉刷第i个房子用的颜色j。
转移方程：dp[i][j]=min(dp[i-1][(j+1)%3] , dp[i-1][(j+2)%3]);
一共有三种颜色{0,1,2}，任取一种颜色{j}，那么和颜色j不同的颜色就为{(j+1)%3,(j+2)%3};

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7. int dp[1010][3],R[1010],G[1010],B[1010],ans,t,icase;
  8. int main()
  9. {
  10.     scanf("%d",&t);
  11.     while (t--)
  12.     {
  13.         int n;
  14.         scanf("%d",&n);
  15.         for(int i=1; i<=n; i++)
  16.             scanf("%d %d %d",&R[i],&G[i],&B[i]);
  17.         memset(dp,0,sizeof(dp));
  18.         for(int i=1; i<=n; i++)
  19.         {
  20.             dp[i][0]=min(dp[i-1][1],dp[i-1][2])+R[i];
  21.             dp[i][1]=min(dp[i-1][0],dp[i-1][2])+G[i];
  22.             dp[i][2]=min(dp[i-1][0],dp[i-1][1])+B[i];
  23.         }
  24.         ans=min(dp[n][0],min(dp[n][1],dp[n][2]));
  25.         printf("Case %d: %d\n",++icase,ans);
  26.     }
  27.     return 0;
  28. }

Problem E：Array Queries

题意：给定一个数组，查询给定区间内的最小值。

题解：线段树求区间最值。。。可能学名叫RMQ？

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cmath>
  5. using namespace std;
  6. int tre[400010],t,n,m,icase;
  7. void build(int rt,int l,int r)
  8. {
  9.     if (l==r)
  10.     {
  11.         scanf("%d",&tre[rt]);
  12.         return;
  13.     }
  14.     int mid=(l+r)/2;
  15.     build(rt*2,l,mid);
  16.     build(rt*2+1,mid+1,r);
  17.     tre[rt]=min(tre[rt*2],tre[rt*2+1]);
  18. }
  20. int query(int rt,int l,int r,int L,int R)
  21. {
  22.     if(l>=L && r<=R)
  23.     {
  24.         return tre[rt];
  25.     }
  26.     int mid=(l+r)/2,ret=1000000000;
  27.     if (mid>=L)
  28.     {
  29.         ret=min(query(rt*2,l,mid,L,R),ret);
  30.     }
  31.     if (mid<R)
  32.     {
  33.         ret=min(query(rt*2+1,mid+1,r,L,R),ret);
  34.     }
  35.     return ret;
  36. }
  38. int main()
  39. {
  40.     scanf("%d",&t);
  41.     while (t--)
  42.     {
  43.         printf("Case %d:\n",++icase);
  44.         scanf("%d%d",&n,&m);
  45.         build(1,1,n);
  46.         while (m--)
  47.         {
  48.             int l,r;
  49.             scanf("%d%d",&l,&r);
  50.             printf("%d\n",query(1,1,n,l,r));
  51.         }
  52.     }
  53.     return 0;
  54. }

Problem F：Farthest Nodes in a Tree

题意：给出一棵树，n个顶点，n-1 条边，给出每条边的权值，问树上的任意两点的最大距离是多少。

题解：树上最长路？用“树的直径”做。先确定起点，随后从这个起点再次遍历整棵树，便能更新出整棵树上的最大距离了。用bfs遍历即可。
附上树的直径详解博客http://www.cnblogs.com/wuyiqi/archive/2012/04/08/2437424.html

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. #include<cstring>
  5. #include<algorithm>
  6. using namespace std;
  7. int edgenum,head[300010],sx,ans,dist[300010],vis[300010],t,icase,n;
  8. struct node
  9. {
  10.     int to,val,next;
  11. }edge[300010];
  13. void add(int u,int v,int w)
  14. {
  15.     node tp={v,w,head[u]};
  16.     edge[edgenum]=tp;
  17.     head[u]=edgenum++;
  18. }
  20. void bfs(int st)
  21. {
  22.     memset(dist,0,sizeof(dist));
  23.     memset(vis,0,sizeof(vis));
  24.     queue<int> q;
  25.     q.push(st);
  26.     dist[st]=0;
  27.     vis[st]=1;
  28.     ans=0;
  29.     while(!q.empty())
  30.     {
  31.         int u=q.front();
  32.         q.pop();
  33.         for(int i=head[u];i!=-1;i=edge[i].next)
  34.         {
  35.             int v=edge[i].to;
  36.             if(!vis[v])
  37.             {
  38.                 vis[v]=1;
  39.                 dist[v]=dist[u]+edge[i].val;
  40.                 if(ans<dist[v])
  41.                 {
  42.                     ans=dist[v];
  43.                     sx=v;
  44.                 }
  45.                 q.push(v);
  46.             }
  47.         }
  48.     }
  49. }
  50. int main()
  51. {
  52.     scanf("%d",&t);
  53.     while(t--)
  54.     {
  55.         edgenum=0;
  56.         memset(head,-1,sizeof(head));
  57.         scanf("%d",&n);
  58.         for(int i=0; i<n-1; i++)
  59.         {
  60.             int a,b,c;
  61.             scanf("%d%d%d",&a,&b,&c);
  62.             add(a,b,c);add(b,a,c);
  63.         }
  64.         bfs(0);
  65.         bfs(sx);
  66.         printf("Case %d: %d\n",++icase,ans);
  67.     }
  68.     return 0;
  69. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注