[关闭]
@morehigh 2017-04-19T15:00:08.000000Z 字数 4676 阅读 1160

CQUPT 训练题 2017/4/10

未分类

A - Binary Simulation
题意：

  1. 给出T个测试样例，每个样例包含一个长度为n的二进制数，q个查询，
  2. 其中 “I i j”表示反转从第i到第j的数，0变1，1变0
  3. “Q i”查询第i个数是0还是1，并输出此数

解题思路：

  1. 记录每个数反转的次数，如果反转的次数为奇数次，则这个数取反，如果是偶数次，这个数就是原来那个数，没有发生变化。用线段树来维护区间反转的次数，其中用到lazy数组优化时间复杂度。

代码：

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

B - Points in Segments
题意：

  1. T个测试样例，每个测试样例包含n (1 ≤ n ≤ 105)个数字，q(1 ≤ q ≤ 50000)个查询，查询这n个数中大于等于a小于等于b的个数

解题思路：

  1. 二分查找，用到upper_bound(a,a+n,r)-a，lower_bound(a,a+n,l)-a。

代码：

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  7. int a[100086];
  8. int main()
  9. {
  10.     int t,n,q;
  11.     scanf("%d",&t);
  12.     for(int cas=1;cas<=t;cas++)
  13.     {
  14.         scanf("%d%d",&n,&q);
  15.         for(int i=0;i<n;i++)
  16.          scanf("%d",&a[i]);
  17.          printf("Case %d:\n",cas);
  18.         while(q--)
  19.         {
  20.             int l,r;
  21.             scanf("%d%d",&l,&r);
  22.             int x=upper_bound(a,a+n,r)-a;
  23.             int y=lower_bound(a,a+n,l)-a;
  24.         printf("%d\n",x-y);
  25.         }
  26.     }
  27.     return 0;
  28. }

C - Calm Down
题意：

  1. 半径为R的大圆里，存在n个半径为r小圆，求半径最大为多少？

解题思路：

  1. 根据大圆与小圆半径之间的关系，连接大圆圆心与小圆圆心，做过大圆圆心与小圆的切线，则切线与连线夹角为pi/n,根据公式可得hh=sin(pi/n)，r/(R+r)=hh;

代码：

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

D - Neighbor House
题意：

  1. 给n座房子染色，每座房子可以染成三种颜色“R G B”，染每种颜色需要一定的费用，求将这座房子染完颜色后所需要的最小花费。

解题思路：

  1. 动态规划，由于相邻的两个房子不能是同一种颜色，状态转移方程：
  2.             dp[i][0]=min(dp[i-1][1],dp[i-1][2])+r[i];
  3.             dp[i][1]=min(dp[i-1][0],dp[i-1][2])+g[i];
  4.             dp[i][2]=min(dp[i-1][1],dp[i-1][0])+b[i];

代码：

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

E - Array Queries
题意：

  1. 有n(1 ≤ N ≤ 105)个数，q(1 ≤ q ≤ 50000)个查询，查询从i到j区间最小值

解题思路：

  1. 线段树模版

代码：

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  7. const int inf=0x3f3f3f3f;
  8. const int N=100086;
  9. int tre[N<<2],a[N];
  10. void build(int l,int r,int rt)
  11. {
  12.     if(l==r)
  13.     {
  14.         tre[rt]=a[l];
  15.     //  cout<<tre[rt]<<" "<<l<<endl;
  16.         return ;
  17.     }
  18.     int m=(l+r)>>1;
  19.     build(l,m,rt<<1);
  20.     build(m+1,r,rt<<1|1);
  21.     tre[rt]=min(tre[rt<<1],tre[rt<<1|1]);
  22. }
  23. int query(int l,int r,int x,int y,int rt)
  24. {
  25.     if(x<=l&&y>=r)
  26.     {
  27.         return tre[rt];
  28.     }
  29.     int m=(l+r)>>1;
  30.     int ans=inf;
  31.     if(x<=m)
  32.     ans=min(query(l,m,x,y,rt<<1),ans);
  33.     if(y>m)
  34.     ans=min(ans,query(m+1,r,x,y,rt<<1|1));
  35.     return ans;
  36. }
  37. int main()
  38. {
  39.     int t,cas=1,n,q;
  40.     scanf("%d",&t);
  41.     while(t--)
  42.     {
  43.         scanf("%d%d",&n,&q);
  44.         for(int i=1;i<=n;i++)
  45.          scanf("%d",&a[i]);
  46.         build(1,n,1);
  48.         printf("Case %d:\n",cas++);
  49.         while(q--)
  50.         {
  51.             int x,y;
  52.             scanf("%d%d",&x,&y);
  53.             int ans=query(1,n,x,y,1);
  54.             printf("%d\n",ans);
  55.         }
  56.     }
  57.     return 0;
  58. }

F - Farthest Nodes in a Tree
题意：

  1. 树上有n个点，u v w (0 ≤ u, v < n, u ≠ v, 1 ≤ w ≤ 10000) 表示从u点到v点的距离为w,求出树上最远的两个点之间的距离为多少

解题思路：

  1. 树的直径
  2. 先搜索一遍找到最远的那个点，然后把这个点当作根节点，再找到离这个点最远的点，此时得到的最远的距离就是树上的最大距离

代码：

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <algorithm>
  6. using namespace std;
  7. struct Node
  8. {
  9.     int to,w;
  10.     int next;
  11. }edge[60005];
  12. int head[30005],cnt;
  13. int vis[30005];
  14. int max1,pos;
  15. void add(int u,int v,int w)
  16. {
  17.     edge[cnt].to=v;
  18.     edge[cnt].w=w;
  19.     edge[cnt].next=head[u];
  20.     head[u]=cnt++;
  21. }
  22. void dfs(int u,int la,int dis)
  23. {
  24.     int hh=0;
  25.     for(int i=head[u];i!=-1;i=edge[i].next)
  26.     {
  27.         int v=edge[i].to;
  28.         int w=edge[i].w;
  29.          if(la==v) continue;
  30.         //  vis[v]=1;
  31.             hh++;
  32.             dfs(v,u,dis+w);
  34.     }
  35.     if(hh==0&&max1<dis)
  36.     {
  37.         max1=dis;
  38.         pos=u;
  39.     }
  40.     return ;
  41. }
  42. int main()
  43. {
  44.     int t,cas=1;
  45.     int u,v,w;
  46.     scanf("%d",&t);
  47.     while(t--)
  48.     {
  49.         int n;
  50.         scanf("%d",&n);
  51.         memset(head,-1,sizeof(head));
  52.         cnt=0;
  53.         for(int i=0;i<n-1;i++)
  54.         {
  55.             scanf("%d%d%d",&u,&v,&w);
  56.             add(u,v,w);
  57.             add(v,u,w);
  58.         }
  59.         max1=0;
  60.         dfs(0,-1,0);
  61.     //  cout<<max1<<endl;
  62.         max1=0;
  63.         dfs(pos,-1,0);
  64.         printf("Case %d: %d\n",cas++,max1);
  65.     }
  66.     return 0;
  67. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注