[关闭]
@sensitive-cs 2017-04-15T14:55:05.000000Z 字数 6228 阅读 798

2017.4.10训练题题解

题解

A - Binary Simulation
题意：
给出一个只包含0和1的字符串，有两种操作，第一是改变下标从i到j的数，让0变成1，1变成0，；第二种操作是查询下标为i的是0还是1.
思路：
线段树，每次翻转，就让所在区间改变的次数加1，不对数进行改变，最后根据改变次数的奇偶性判断是否改变。
代码：

  1. #include <string.h>
  2. #include <stdio.h>
  4. int a[100005];
  5. int add[400005];
  6. int sum[400005];
  7. char b[100005];
  9. void pushup(int rt)
  10. {
  11.     sum[rt] = sum[rt << 1] + sum[rt << 1|1];
  12. }
  14. void build(int l,int r,int rt)
  15. {
  16.     if (l == r)
  17.     {
  18.         sum[rt] = a[l];
  19.         return;
  20.     }
  22.     int m = (l+r) >> 1;
  24.     build(l,m,rt << 1);
  25.     build(m+1,r,rt << 1|1);
  27.     pushup(rt);
  28. }
  30. void pushdown(int rt,int ln,int rn)
  31. {
  32.     if (add[rt])
  33.     {
  34.         add[rt << 1] += add[rt];
  35.         add[rt << 1|1] += add[rt];
  37.         sum[rt << 1] += ln * add[rt];
  38.         sum[rt << 1|1] += rn *add[rt];
  40.         add[rt] = 0;
  41.     }
  42. }
  44. void update(int ll,int rr,int c,int l,int r,int rt)
  45. {
  46.     if (ll <= l && r <= rr)
  47.     {
  48.         sum[rt] += c*(r-l+1);
  49.         add[rt] += c;
  50.         return;
  51.     }
  53.     int m = (l+r) >> 1;
  55.     pushdown(rt,m-l+1,r-m);
  57.     if (ll <= m) update(ll,rr,c,l,m,rt << 1);
  58.     if (rr > m) update(ll,rr,c,m+1,r,rt << 1|1);
  60.     pushup(rt);
  61. }
  63. long long query(int ll,int rr,int l,int r,int rt)
  64. {
  65.     if (ll <= l && r <= rr)
  66.     {
  67.         return sum[rt];
  68.     }
  70.     int m = (l+r) >> 1;
  72.     pushdown(rt,m-l+1,r-m);
  74.     long long ans = 0;
  76.     if (ll <= m) ans += query(ll,rr,l,m,rt << 1);
  77.     if (rr > m) ans += query(ll,rr,m+1,r,rt << 1|1);
  79.     return ans;
  80. }
  82. int main()
  83. {
  84.     int t;
  86.     scanf ("%d",&t);
  88.     int cnt = 0;
  90.     while (t--)
  91.     {
  92.         memset(a,0,sizeof(a));
  93.         memset(add,0,sizeof(add));
  94.         memset(sum,0,sizeof(sum));
  96.         printf("Case %d:\n",++cnt);
  98.         int q = 0,sl = 0;
  100.         scanf("%s",b);
  102.         sl = strlen(b);
  104.         build(1,sl,1);
  106.         scanf("%d",&q);
  108.         for (int i = 0;i < q;i++)
  109.         {
  110.             char s[5];
  111.             int x,y;
  113.             scanf("%s",s);
  115.             if (s[0] == 'I')
  116.             {
  117.                 scanf("%d%d",&x,&y);
  119.                 update(x,y,1,1,sl,1);
  120.             }
  122.             if (s[0] == 'Q')
  123.             {
  124.                 scanf("%d",&x);
  126.                int ans =  query(x,x,1,sl,1);
  128.                if (ans % 2 == 0)
  129.                {
  130.                    printf("%c\n",b[x-1]);
  131.                }
  132.                else
  133.                {
  134.                    if (b[x-1] == '0') printf("1\n");
  135.                    else printf("0\n");
  136.                }
  137.             }
  138.         }
  141.     }
  143.     return 0;
  144. }

B - Points in Segments
题意:
给出n个数，后面给出m个区间，对于每个区间，查询再次区间内的数有多少个。
思路：
线段树+离散化。需要注意的是离散化时需要对不连续的两个数之间加入一个在两数之间的数，这样才能保证不出错。第二是线段树初始化的时候区间长度加上2*10e5,这样保证了所有数据都在区间内；第三呢，对输入的区间进行特判，如果左端点大于最大数或者右端点小于最小数，那就输出0.
代码：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. #include <vector>
  5. using namespace std;
  7. const int len = 1e5 + 5;
  9. vector<int> v;
  10. int a[len];
  11. bool pos[len * 10];
  12. int ans = 0;
  13. struct ss
  14. {
  15.     int l,r;
  16.     int sum;
  17. }node[len * 10];
  19. void build(int rt,int l,int r)
  20. {
  21.     node[rt].l = l,node[rt].r = r;
  23.     if (l == r)
  24.     {
  25.         if (pos[l]) node[rt].sum = 1;
  26.         else node[rt].sum = 0;
  27.         return;
  28.     }
  30.     int mid = (l + r) >> 1;
  32.     build(rt << 1,l,mid);
  33.     build(rt << 1|1,mid+1,r);
  35.     node[rt].sum += (node[rt << 1].sum+node[rt << 1|1].sum);
  36. }
  38. void query(int rt,int L,int R)
  39. {
  40.     if (node[rt].l >= L && node[rt].r <= R)
  41.     {
  42.         ans += node[rt].sum;
  43.         return;
  44.     }
  46.     int mid = (node[rt].l + node[rt].r) >> 1;
  48.     if (L <= mid) query(rt << 1,L,R);
  49.     if (R > mid) query(rt << 1|1,L,R);
  50. }
  52. int main()
  53. {
  54.     int t,cnt = 0;
  56.     scanf("%d",&t);
  58.     while (t--)
  59.     {
  60.         memset(a,0,sizeof(a));
  61.         v.clear();
  62.         memset(pos,0,sizeof(pos));
  63.         memset(node,0,sizeof(node));
  65.         int n,q;
  67.         scanf("%d%d",&n,&q);
  69.         for (int i = 0;i < n;i++)
  70.         {
  71.             scanf("%d",&a[i]);
  73.             v.push_back(a[i]);
  74.         }
  76.         printf("Case %d:\n",++cnt);
  78.         sort(a,a+n);
  79.         sort(v.begin(),v.end());
  81.         int tt = v.size();
  82.         for (int i = 1;i < tt;i++)
  83.         {
  84.             if (v[i] - v[i-1] > 1) v.push_back(v[i] - 1);
  85.         }
  87.         int ls = v.size();
  89.         sort(v.begin(),v.end());
  91.         for (int i = 0;i < n;i++)
  92.         {
  93.             vector<int>::iterator it;
  95.             it  = lower_bound(v.begin(),v.end(),a[i]);
  97.             pos[it - v.begin()+1] = 1;
  98.         }
  100.         build(1,1,ls + 2*len);
  102.         for (int i = 0;i < q;i++)
  103.         {
  104.             int x,y;
  106.             scanf("%d%d",&x,&y);
  108.             if (x > a[n-1] || y < a[0])
  109.             {
  110.                 printf("%d\n",0);
  111.                 continue;
  112.             }
  114.             ans = 0;
  116.             vector<int>::iterator it;
  118.             x = lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
  119.             y = lower_bound(v.begin(),v.end(),y) - v.begin() + 1;
  121.             query(1,x,y);
  123.             printf("%d\n",ans);
  124.         }
  125.     }
  127.     return 0;
  128. }

C - Calm Down
题意：
给出大圆的半径和小圆的个数，求出小圆的最大半径，保证所有的小圆半径相同且所有的小圆相切。
思路：
所有相邻小圆的圆心相连构成一个正多边形，根据正多边形的内角和公式和三角函数以及长度关系可以推出大圆与小圆的半径的关系。数学题。
代码：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <math.h>
  5. int main()
  6. {
  7.     int t;
  9.     scanf("%d",&t);
  11.     int cnt = 0;
  13.     while (t--)
  14.     {
  15.         int n;
  16.         double r;
  18.         scanf("%lf%d",&r,&n);
  20.         double ans = 0;
  22.         const double pi = atan(1)*4;
  24.         if (n == 2)
  25.         {
  26.             ans = r / 2;
  27.         }
  28.         else
  29.         {
  30.             double s = (n-2) * 180.0 / n;
  31.             s = s * pi / 180 / 2;
  33.             ans = r * cos(s) / (1 + cos(s));
  34.         }
  36.         printf("Case %d: %.8f\n",++cnt,ans);
  37.     }
  39.     return 0;
  40. }

D - Neighbor House
题意：
给出n个房子，每个房子可涂3种颜色，涂每种颜色的价格不同，相邻两间房子的颜色不能相同，问最小的花费。
思路：
动态规划，转移方程 : dp[i][1] = min(dp[i-1][2]+a[i][1],dp[i-1][3]+a[i][1]),其他与此类似。
代码：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. using namespace std;
  6. int a[25][5];
  7. int dp[25][5];
  9. const int inf = 0x3f3f3f3f;
  11. int main()
  12. {
  13.     int t;
  14.     int cnt = 0;
  16.     scanf("%d",&t);
  18.     while (t--)
  19.     {
  20.         memset(a,0,sizeof(a));
  22.         int n;
  24.         scanf("%d",&n);
  26.         for (int i = 1;i <= n;i++)
  27.             for (int j = 1;j <= 3;j++)
  28.                 scanf("%d",&a[i][j]);
  30.         memset(dp,inf,sizeof(dp));
  32.         dp[1][1] = a[1][1];
  33.         dp[1][2] = a[1][2];
  34.         dp[1][3] = a[1][3];
  36.         for (int i = 2;i <= n;i++)
  37.         {
  38.             dp[i][1] = min(dp[i-1][2] + a[i][1],dp[i-1][3] + a[i][1]);
  39.             dp[i][2] = min(dp[i-1][1] + a[i][2],dp[i-1][3] + a[i][2]);
  40.             dp[i][3] = min(dp[i-1][2] + a[i][3],dp[i-1][1] + a[i][3]);
  41.         }
  43.         int minn = inf;
  45.         for (int i = 1;i <= 3;i++)
  46.             if (dp[n][i] < minn) minn = dp[n][i];
  48.         printf("Case %d: %d\n",++cnt,minn);
  49.     }
  51.     return 0;
  52. }

E - Array Queries
题意：
给出n个数，每次查询下标从i到j的最小值。
思路：
线段树，维护的是区间的最小值。
代码：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <algorithm>
  4. using namespace std;
  6. struct tt 
  7. {
  8.     int l,r;
  9.     int v;
  10. }node[100005 << 2];
  12. void build(int l,int r,int rt)
  13. {
  14.     node[rt].l = l,node[rt].r = r;
  16.     if (l == r)
  17.     {
  18.         scanf("%d",&node[rt].v);
  19.         return;
  20.     }
  22.     int mid = (l + r) >> 1;
  24.     build(l,mid,rt << 1);
  25.     build(mid + 1,r,rt << 1|1);
  27.     node[rt].v = min(node[rt << 1].v,node[rt << 1|1].v);
  28. }
  30. int query(int rt,int ll,int rr)
  31. {
  32.     if (node[rt].l >= ll && node[rt].r <= rr)
  33.     {
  34.         return node[rt].v;
  36.     }
  38.     int a1 = 1e7,a2 = 1e7;
  40.     int mid = (node[rt].l + node[rt].r) / 2;
  42.     if (ll <= mid) a1 = query(rt << 1,ll,rr);
  43.     if (rr > mid) a2 = query(rt << 1|1,ll,rr);
  45.     return min(a1,a2);
  46. }
  48. int main()
  49. {
  50.     int t;
  52.     scanf("%d",&t);
  54.     int cnt = 0;
  56.     while (t--)
  57.     {
  60.         memset(node,0,sizeof(node));
  62.         int n,q;
  64.         scanf("%d%d",&n,&q);
  66.         build(1,n,1);
  68.         printf("Case %d:\n",++cnt);
  70.         for (int i = 0;i < q;i++)
  71.         {
  72.             int x,y;
  74.             scanf("%d%d",&x,&y);
  76.             int ans = query(1,x,y);
  78.             printf("%d\n",ans);
  79.         }
  80.     }
  82.     return 0;
  83. }

F - Farthest Nodes in a Tree
题意：
给出一棵树，找出任意两点间距离的最大值。
思路：
求一棵树的直径。结论：从任意一个点总能找到距离它最远的点，此点即是最长路的终点。
所以两次bfs，第一次bfs找到最长路终点，第二次算出终点到所有点的距离，最后找出最大值即可。
代码：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <vector>
  4. #include <map>
  5. #include <queue>
  6. using namespace std;
  8. int d[30005];
  9.  typedef pair<int,int> p;
  10.  map<p,int> mmp;
  11.  vector<int> g[30005];
  12.  bool vis[30005];
  14. int main()
  15. {
  16.     int t;
  18.     scanf("%d",&t);
  20.     int cnt = 0;
  22.     while (t--)
  23.     {
  24.         int n;
  25.         mmp.clear();
  26.         memset(g,0,sizeof(g));
  27.         memset(vis,0,sizeof(vis));
  29.         scanf("%d",&n);
  31.         for (int i = 0;i < n-1;i++)
  32.         {
  33.             int x,y,z;
  35.             scanf("%d%d%d",&x,&y,&z);
  37.             mmp[p(x,y)] = mmp[p(y,x)] = z;
  39.             g[x].push_back(y);
  40.             g[y].push_back(x);
  41.         }
  43.         memset(d,0,sizeof(d));
  45.         queue<int> s;
  46.         s.push(0);
  47.         vis[0] = 1;
  49.         while (!s.empty())
  50.         {
  51.             int c = s.front();s.pop();
  53.             for (int i = 0;i < g[c].size();i++)
  54.             {
  55.                 if (!vis[g[c][i]])
  56.                 {
  57.                     int k = g[c][i];
  58.                     d[k] = d[c] + mmp[p(c,k)];
  59.                     vis[k] = 1;
  60.                     s.push(k);
  61.                 }
  62.             }
  63.         }
  65.         int m;
  66.         int maxnn = 0;
  68.         for (int i = 0;i < n;i++)
  69.         {
  70.             if (maxnn < d[i])
  71.             {
  72.                 m = i;
  73.                 maxnn = d[i];
  74.             }
  75.         }
  77.         memset(vis,0,sizeof(vis));
  78.         memset(d,0,sizeof(d));
  80.         s.push(m);
  81.         vis[m] = 1;
  83.         while (!s.empty())
  84.         {
  85.             int c = s.front();s.pop();
  87.             for (int i = 0;i < g[c].size();i++)
  88.             {
  89.                 if (!vis[g[c][i]])
  90.                 {
  91.                     int k = g[c][i];
  92.                     d[k] = d[c] + mmp[p(c,k)];
  93.                     vis[k] = 1;
  94.                     s.push(k);
  95.                 }
  96.             }
  97.         }
  99.         maxnn = 0;
  101.         for (int i = 0;i < n;i++)
  102.         {
  103.             if (maxnn < d[i])
  104.             {
  105.                 m = i;
  106.                 maxnn = d[i];
  107.             }
  108.         }
  110.         printf("Case %d: %d\n",++cnt,maxnn);
  111.     }
  113.     return 0;
  114. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注