[关闭]
@meredith233 2017-04-14T16:07:52.000000Z 字数 4867 阅读 885

2017/4/10

homework

A - Binary Simulation

题目大意：

给定一个二进制数，给定两种操作。操作‘I’对给定区间[a,b]内的数进行取反操作。操作‘Q’查询第i个位置的数是0还是1.

解题思路：

用线段树的区间更新来记录每个位置取反的次数，而后查询时如果取反次数为奇数次则对该数取反。后输出。

AC代码：

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. #define PI acos(-1.0)
  7. #define MAX 100005
  8. using namespace std;
  9. int tre[MAX*4],laz[MAX*4];
  10. char ar[MAX];
  11. void pushdown(int num)
  12. {
  13.     if(laz[num]!=0)
  14.     {
  15.         tre[num*2]+=laz[num];
  16.         tre[num*2+1]+=laz[num];
  17.         laz[num*2]+=laz[num];
  18.         laz[num*2+1]+=laz[num];
  19.         laz[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.         laz[num]++;
  28.         return;
  29.     }
  30.     pushdown(num);
  31.     int mid=(l+r)/2;
  32.     if(x<=mid)
  33.         update(num*2,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 l,int r,int x)
  38. {
  39.     if(l==r)
  40.         return tre[num];
  41.     pushdown(num);
  42.     int mid=(l+r)/2;
  43.     if(x<=mid)
  44.         return query(num*2,l,mid,x);
  45.     else
  46.         return query(num*2+1,mid+1,r,x);
  47. }
  48. int main()
  49. {
  50.     //freopen("test.txt","r",stdin);
  51.     int t,cnt=0;
  52.     scanf("%d",&t);
  53.     while(t--)
  54.     {
  55.         memset(tre,0,sizeof(tre));
  56.         memset(laz,0,sizeof(laz));
  57.         scanf("%s",ar+1);
  58.         int n=strlen(ar+1);
  59.         int q;
  60.         printf("Case %d:\n",++cnt);
  61.         scanf("%d",&q);
  62.         while(q--)
  63.         {
  64.             char c;
  65.             int a,b;
  66.             scanf(" %c",&c);
  67.             if(c=='I')
  68.             {
  69.                 scanf("%d%d",&a,&b);
  70.                 update(1,1,n,a,b);
  71.             }
  72.             if(c=='Q')
  73.             {
  74.                 scanf("%d",&a);
  75.                 int x=query(1,1,n,a);
  76.                 int ans=ar[a]-'0';
  77.                 if(x%2==1)
  78.                     ans=!ans;
  79.                 printf("%d\n",ans);
  80.             }
  81.         }
  82.     }
  83.     return 0;
  84. }

B - Points in Segments

题目大意：

输入一串数字，然后输入a,b，查询大于等于a且小于等于b的数字有多少个。

解题思路：

二分查找，先对输入的数字串进行排序，后进行两次二分分别查询范围内最小值和最大值所在位置，输出即可。

AC代码：

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

C - Calm Down

题目大意：

给定一个大圆半径R，以及大圆内的小圆个数n，求小圆的半径r。

解题思路：

连接大圆圆心与相邻两个小圆圆心，可得其角度为2PI/n,而后连接大圆圆心与两小圆心中点，可得公式r=R*sin(PI/n)/(1+sin(PI/n))。在该题中，需要注意在r为整数时输出整数，否则保留10位小数。

AC代码：

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

D - Neighbor House

题目大意：

有n户人，要涂上红，绿，蓝三种颜色，且相邻两户颜色不能相同，给定每户涂每种颜色所需花费，求最小花费。

解题思路：

动态规划，每次求与上一户人家不同颜色时花费最小。

AC代码：

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <cstring>
  6. #define PI acos(-1.0)
  7. #define MAX 100005
  8. #define INF (1<<20)
  9. using namespace std;
  10. int ar[25][5],dp[25][5];
  11. int main()
  12. {
  13.     int t,cnt=0;
  14.     scanf("%d",&t);
  15.     while(t--)
  16.     {
  17.         memset(dp,0,sizeof(dp));
  18.         int n;
  19.         scanf("%d",&n);
  20.         for(int i=0;i<n;i++)
  21.             scanf("%d%d%d",&ar[i][0],&ar[i][1],&ar[i][2]);
  22.         for(int i=0;i<3;i++)
  23.             dp[0][i]=ar[0][i];
  24.         for(int i=1;i<n;i++)
  25.         {
  26.             for(int j=0;j<3;j++)
  27.             {
  28.                 if(j==0)
  29.                     dp[i][j]=ar[i][j]+min(dp[i-1][1],dp[i-1][2]);
  30.                 if(j==1)
  31.                     dp[i][j]=ar[i][j]+min(dp[i-1][0],dp[i-1][2]);
  32.                 if(j==2)
  33.                     dp[i][j]=ar[i][j]+min(dp[i-1][0],dp[i-1][1]);
  34.             }
  35.         }
  36.         int ans=INF;
  37.         for(int i=0;i<3;i++)
  38.             ans=min(ans,dp[n-1][i]);
  39.         printf("Case %d: %d\n",++cnt,ans);
  40.     }
  41.     return 0;
  42. }

E - Array Queries

题目大意：

给定n个数q个查询，求区间最小值。

解题思路：

线段树裸题，求区间最小值。

AC代码：

  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #define MAX 100000
  5. #define INF (1<<20)
  6. using namespace std;
  7. int tre[MAX*4];
  8. void build(int num,int l,int r)
  9. {
  10.     if(l==r)
  11.     {
  12.         scanf("%d",&tre[num]);
  13.         return;
  14.     }
  15.     int mid=(l+r)>>1;
  16.     build(num*2,l,mid);
  17.     build(num*2+1,mid+1,r);
  18.     tre[num]=min(tre[num*2],tre[num*2+1]);
  19. }
  20. int query(int num,int l,int r,int x,int y)
  21. {
  22.     if(x<=l&&y>=r)
  23.         return tre[num];
  24.     int mid=(l+r)>>1;
  25.     int ans=INF;
  26.     if(x<=mid)
  27.         ans=min(ans,query(num*2,l,mid,x,y));
  28.     if(y>mid)
  29.         ans=min(ans,query(num*2+1,mid+1,r,x,y));
  30.     return ans;
  31. }
  32. int main()
  33. {
  34.     int t,cnt=0;
  35.     scanf("%d",&t);
  36.     while(t--)
  37.     {
  38.         int n,q;
  39.         scanf("%d%d",&n,&q);
  40.         build(1,1,n);
  41.         printf("Case %d:\n",++cnt);
  42.         while(q--)
  43.         {
  44.             int a,b;
  45.             scanf("%d%d",&a,&b);
  46.             printf("%d\n",query(1,1,n,a,b));
  47.         }
  48.     }
  49.     return 0;
  50. }

F - Farthest Nodes in a Tree

题目大意：

给定一棵树，需要找出树上任意两点间的最长距离。

解题思路：

树的直径问题，先对任一点dfs求出直径的一个端点，后对这个端点求dfs，可得答案。

AC代码：

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