[关闭]
@TryMyEdge 2017-04-22T21:23:45.000000Z 字数 6860 阅读 870

CQUPT 训练题 2017/4/10

题解

题目

A Binary Simulation

题目大意：

    有一个长度为n(1<=n<=100000)的二进制数，每一位的数字为0或者1，位编号从1到n。有q(1<=q<=50000)个操作，操作分两种：(1)给定i和j，从第i位到第j位数字取逻辑反(1变0，0变1)，(2)给定i，询问第i位上的数字当前状态是0还是1。
    T(T<=10)组数据。

解题思路：

    暴力模拟的最坏情况是每次都是修改所有的数的状态，那么复杂度是o(T*n*q)，boom！
    实际上我们会发现，只要知道这个位子上的数的初始状态和被修改了多少次，就能算出来这个数的当前状态是什么。于是问题就转化成了在有区间加法的情况下求某个点的值，可以用线段树也可以用树状数组，这里给出用线段树在区间加法下维护每个点值的解法。
    ps:输入长度n的二进制数要用字符串。初始建树的时候稍作修改，查询的时候就不需要再去看这个位置的初始状态是什么了，可以观察下我的build函数。
    时间复杂度o(T*q*log(n))，空间复杂度o(n)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. struct Node
  6. {
  7.     int l,r,mid,val;
  8. }tre[400005];
  9. char s[100005],c[6];
  10. void build(int x,int l,int r)
  11. {
  12.     tre[x].l=l;
  13.     tre[x].r=r;
  14.     tre[x].mid=(l+r)>>1;
  15.     if(tre[x].l!=tre[x].r)
  16.     {
  17.         tre[x].val=0;
  18.         build(x*2,l,tre[x].mid);
  19.         build(x*2+1,tre[x].mid+1,r);
  20.     }
  21.     else
  22.         tre[x].val=(s[l]=='1');
  23. }
  24. void add(int x,int l,int r)
  25. {
  26.     if(tre[x].l==l && tre[x].r==r)
  27.         tre[x].val++;
  28.     else
  29.     {
  30.         if(l<=tre[x].mid && r>tre[x].mid)
  31.         {
  32.             add(x*2,l,tre[x].mid);
  33.             add(x*2+1,tre[x].mid+1,r);
  34.         }
  35.         else
  36.         {
  37.             if(r<=tre[x].mid)
  38.                 add(x*2,l,r);
  39.             else
  40.                 add(x*2+1,l,r);
  41.         }
  42.     }
  43. }
  44. int ask(int x,int now)
  45. {
  46.     if(tre[x].l==tre[x].r)
  47.         return tre[x].val;
  48.     else
  49.     {
  50.         if(now<=tre[x].mid)
  51.             return tre[x].val+ask(x*2,now);
  52.         else
  53.             return tre[x].val+ask(x*2+1,now);
  54.     }
  55. }
  56. int main()
  57. {
  58.     int T,n,m,a,b;
  59.     scanf("%d",&T);
  60.     for(int t=1;t<=T;t++)
  61.     {
  62.         scanf("%s",s+1);
  63.         build(1,1,strlen(s+1));
  64.         scanf("%d",&m);
  65.         printf("Case %d:\n",t);
  66.         while(m--)
  67.         {
  68.             scanf("%s",c);
  69.             if(c[0]=='I')
  70.             {
  71.                 scanf("%d%d",&a,&b);
  72.                 add(1,a,b);
  73.             }
  74.             else
  75.             {
  76.                 scanf("%d",&a);
  77.                 printf("%d\n",ask(1,a)%2);
  78.             }
  79.         }
  80.     }
  81.     return 0;
  82. }

B Points in Segments

题目大意：

    给出n(1<=n<=100000)个点的坐标，坐标范围是[0，10^8]，然后有q(1<=q<=50000)个询问，对于每个询问输出询问的区间内(包括区间左右端点)出现了多少个点。
    T(T<=5)组数据。

解题思路：

    用线段树和树状数组很容易解决的一道单点更新、区间求和的题目。问题在于坐标的范围太大，不仅10^8*log(10^8)的时间复杂度会超，甚至10^8的空间复杂度也是超的。
    我们发现，一个坐标如果既不出现在询问中也不是某个点的坐标，那么这个坐标存不存在实际上没区别。n个点加上每个询问两个端点，最多会出现n+q*2<=200000个坐标(其中还可能有重复的)。我们把那些没用的点删去，只留下这些有用的点，就可以把点的坐标范围缩小到200000。
    我们用到的方法就是离散化。在这道题里面，实际上就是建立一个双射，把每个坐标值和它是第几个有用的坐标值联系起来。
    ps：记得去重。
    时间复杂度o(T*q*log(n+q*2))，空间复杂度o(n+q*2)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. struct Node
  7. {
  8.     int l,r,mid,val;
  9. }tre[800005];
  10. int addnum[100005];
  11. int ql[50005],qr[50005];
  12. int nums[200005],nownums;
  13. int num[200005],nownum;
  14. void build(int x,int l,int r)
  15. {
  16.     tre[x].l=l;
  17.     tre[x].r=r;
  18.     tre[x].mid=(l+r)>>1;
  19.     tre[x].val=0;
  20.     if(tre[x].l!=tre[x].r)
  21.     {
  22.         build(x*2,l,tre[x].mid);
  23.         build(x*2+1,tre[x].mid+1,r);
  24.     }
  25. }
  26. void add(int x,int y)
  27. {
  28.     tre[x].val++;
  29.     if(tre[x].l!=tre[x].r)
  30.     {
  31.         if(y<=num[tre[x].mid])
  32.             add(x*2,y);
  33.         else
  34.             add(x*2+1,y);
  35.     }
  36. }
  37. int ask(int x,int l,int r)
  38. {
  39.     if(num[tre[x].l]==l && num[tre[x].r]==r)
  40.         return tre[x].val;
  41.     else
  42.     {
  43.         if(l<=num[tre[x].mid] && r>num[tre[x].mid])
  44.             return ask(x*2,l,num[tre[x].mid])+ask(x*2+1,num[tre[x].mid+1],r);
  45.         else
  46.         {
  47.             if(r<=num[tre[x].mid])
  48.                 return ask(x*2,l,r);
  49.             else
  50.                 return ask(x*2+1,l,r);
  51.         }
  52.     }
  53. }
  54. int main()
  55. {
  56.     int T,n,m;
  57.     scanf("%d",&T);
  58.     for(int t=1;t<=T;t++)
  59.     {
  60.         nownums=0;
  61.         scanf("%d%d",&n,&m);
  62.         for(int i=0;i<n;i++)
  63.         {
  64.             scanf("%d",addnum+i);
  65.             nums[nownums]=addnum[i];
  66.             nownums++;
  67.         }
  68.         for(int i=0;i<m;i++)
  69.         {
  70.             scanf("%d%d",ql+i,qr+i);
  71.             nums[nownums]=ql[i];
  72.             nownums++;
  73.             nums[nownums]=qr[i];
  74.             nownums++;
  75.         }
  76.         sort(nums,nums+nownums);
  77.         nownum=1;
  78.         num[1]=nums[0];
  79.         for(int i=1;i<nownums;i++)
  80.         {
  81.             if(nums[i]!=nums[i-1])
  82.             {
  83.                 nownum++;
  84.                 num[nownum]=nums[i];
  85.             }
  86.         }
  87.         build(1,1,nownum);
  88.         for(int i=0;i<n;i++)
  89.             add(1,addnum[i]);
  90.         printf("Case %d:\n",t);
  91.         for(int i=0;i<m;i++)
  92.             printf("%d\n",ask(1,ql[i],qr[i]));
  93.     }
  94.     return 0;
  95. }

C Calm Down

题目大意：

    看图猜题意.jpg
    把n(2<=n<=100)个一模一样的小圆(?)按照图里的方式放在半径为R(0<R<1000)的大圆里，问小圆的半径应该是多少。
    T(T<=125)组数据。

解题思路：

    二分什么的都是异端，这题推个公式就好了。

左轮

    sin(2π/2n)=r/(R-r)，解出来r=R*sin(2π/2n)/(1+sin(2π/2n))。
    时间复杂度o(T)，空间复杂度o(1)。

AC代码：

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

D Neighbor House

题目大意：

    有n(1<=n<=20)间房子排成一排，第一间房子和最后一间房子不相邻。每间房子刷成红、绿、蓝三种颜色有各自的代价。相邻两间房子不能刷成一个颜色，问最少要花多少钱。
    T(T<=100)组数据。

解题思路：

    因为相邻两间房子颜色不能一样，所以我们刷某一间房子的时候，只需要考虑他前面一间房子是什么颜色的，更之前的房子都不影响当前这一间的颜色。所以我们可以很容易采用dp的解法来做这道题。
    dp[i][j]表示到第i个房子为止全部合法粉刷，并且第i间房子的颜色为j的最小代价。num[i][j]表示把第i间房子刷成颜色j的代价。
    那么状态转移方程为：
    dp[i][0]=min(dp[i-1][1],dp[i-1][2])+num[i][0]
    dp[i][1]=min(dp[i-1][0],dp[i-1][2])+num[i][1]
    dp[i][2]=min(dp[i-1][1],dp[i-1][0])+num[i][2]
    ps：我的代码里没出现num数组~这道题其实n完全可以大点= =。
    时间复杂度o(T*n)，空间复杂度o(n)。

AC代码：

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

E Array Queries

题目大意：

    n(1<=n<=100000)个数，每个数的范围是[0，100000]。q(1<=q<=50000)个询问，询问某个区间内最小值是多少。
    T(T<=5)组数据。

解题思路：

    裸的求区间最值，这很线段树.jpg
    时间复杂度o(T*q*log(n))，空间复杂度o(n)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. struct Node
  7. {
  8.     int l,r,mid,val;
  9. }tre[400005];
  10. int num[100005];
  11. int build(int x,int l,int r)
  12. {
  13.     tre[x].l=l;
  14.     tre[x].r=r;
  15.     tre[x].mid=(l+r)>>1;
  16.     if(tre[x].l!=tre[x].r)
  17.         return tre[x].val=min(build(x*2,l,tre[x].mid),build(x*2+1,tre[x].mid+1,r));
  18.     else
  19.         return tre[x].val=num[tre[x].mid];
  20. }
  21. int ask(int x,int l,int r)
  22. {
  23.     if(tre[x].l==l && tre[x].r==r)
  24.         return tre[x].val;
  25.     else
  26.     {
  27.         if(l<=tre[x].mid && r>tre[x].mid)
  28.             return min(ask(x*2,l,tre[x].mid),ask(x*2+1,tre[x].mid+1,r));
  29.         else
  30.         {
  31.             if(r<=tre[x].mid)
  32.                 return ask(x*2,l,r);
  33.             else
  34.                 return ask(x*2+1,l,r);
  35.         }
  36.     }
  37. }
  38. int main()
  39. {
  40.     int T,n,m,a,b;
  41.     scanf("%d",&T);
  42.     for(int t=1;t<=T;t++)
  43.     {
  44.         scanf("%d%d",&n,&m);
  45.         for(int i=1;i<=n;i++)
  46.             scanf("%d",num+i);
  47.         build(1,1,n);
  48.         printf("Case %d:\n",t);
  49.         while(m--)
  50.         {
  51.             scanf("%d%d",&a,&b);
  52.             printf("%d\n",ask(1,a,b));
  53.         }
  54.     }
  55.     return 0;
  56. }

F Farthest Nodes in a Tree

题目大意：

    给一个有n(2<=n<=30000)个点的无根树，问树上最远两点的距离。
    T(T<=10)组数据。

解题思路：

    有一个神奇的结论：从树上任意一点A出发，到达离A最远的点(可能有多个)中的一个记为B，那么从B出发，到达离B最远的点(可能有多个)中的一个记为C，那么B到C的距离就是树上最远两点的距离。
    很神奇吧~以下是证明：
    我们定义|P1P2|为点A到点B的距离，因为这是棵树，所以任意两点是连通的，并且距离是唯一的。
    树的一个性质：P1、P2、P3为树上任意三点，那么|P1P2|<=|P1P3|+|P3P2|。至于原理，自己去证~
    假设树上最远的距离是从点X到点Y，并且|XY|>|BC|，又因为A是距离B最远的点之一，所以|AX|<=|AB|。M是A到X和A到B这两条路径上的分叉点(这个点一定存在，因为至少A是这两条路径的共同点)，那么|AX|=|AM|+|MX|，|AB|=|AM|+|MB|，所以|MX|<=|MB|。根据树的性质，|XY|<=|XM|+|MY|<=|XM|+|MB|=|XB|。又因为C是距离B最远的距离之一，所以|BX|<=|BC|，所以|XY|<=|BC|，和假设矛盾，所以假设不成立，证明结束。
    根据这个神奇的结论，我们以任意一个点为起点A，找到最远点中的一个B，在从B出发，找到最远点中的一个C，那么BC的距离就是答案了。只需要两次DFS即可。
    时间复杂度o(T*n)，空间复杂度o(n)。

AC代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. struct Edge
  7. {
  8.     int v,dis;
  9. }e[60005];
  10. int nums;
  11. int root[30005],nex[60005];
  12. bool life[30005];
  13. int maxdis,flag;
  14. void dfs(int dis,int x)
  15. {
  16.     life[x]=1;
  17.     int temp=root[x];
  18.     if(dis>maxdis)
  19.     {
  20.         maxdis=dis;
  21.         flag=x;
  22.     }
  23.     while(temp)
  24.     {
  25.         if(!life[e[temp].v])
  26.             dfs(dis+e[temp].dis,e[temp].v);
  27.         temp=nex[temp];
  28.     }
  29. }
  30. int main()
  31. {
  32.     int T,n,a,b,w;
  33.     scanf("%d",&T);
  34.     for(int t=1;t<=T;t++)
  35.     {
  36.         scanf("%d",&n);
  37.         nums=0;
  38.         memset(root,0,sizeof(root));
  39.         for(int i=1;i<n;i++)
  40.         {
  41.             scanf("%d%d%d",&a,&b,&w);
  42.             nums++;
  43.             e[nums].v=b;
  44.             e[nums].dis=w;
  45.             nex[nums]=root[a];
  46.             root[a]=nums;
  47.             nums++;
  48.             e[nums].v=a;
  49.             e[nums].dis=w;
  50.             nex[nums]=root[b];
  51.             root[b]=nums;
  52.         }
  53.         maxdis=0;
  54.         memset(life,0,sizeof(life));
  55.         dfs(0,0);
  56.         maxdis=0;
  57.         memset(life,0,sizeof(life));
  58.         dfs(0,flag);
  59.         printf("Case %d: %d\n",t,maxdis);
  60.     }
  61.     return 0;
  62. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注