[关闭]
@morehigh 2016-12-12T15:08:59.000000Z 字数 6372 阅读 953

1.第一次作业 CQUPT Training Nov28th - Dec3rd 题解

题解：
A Design Tutorial: Learn from Math

题目大意：

  1. 给定一个n（12<=n<=10^6)，求出符合以下要求的x和y：
  2.         1.x+y=n
  3.         2.x和y都是合数

解题思路：

  1. 用筛法的思想找出所有的合数并标记，然后判断x与y是不是合数，是的话就输出。

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<cmath>
  7. using namespace std;
  8. const int MAXN=1000010;
  9. bool notprime[MAXN];
  10. void getprim()
  11. {
  12.     memset(notprime,false,sizeof(notprime));
  13.     notprime[0]=notprime[1]=0;
  14.     for(int i=2;i<MAXN;i++)
  15.     {
  16.         if(!notprime[i])
  17.         {
  18.             if(i>MAXN/i)
  19.             continue;
  20.             for(int j=i*i;j<MAXN;j+=i)
  21.             notprime[j]=true;
  22.         }
  23.     }
  24. }
  25. int main()
  26. {
  27.     int n;
  28.     getprim();
  29.     while(scanf("%d",&n)!=EOF)
  30.     {
  31.         int m=4;
  32.         while(m<=(n/2))
  33.         {
  34.             if(notprime[m]&&notprime[n-m])
  35.             {
  36.                 cout<<m<<" "<<n-m<<endl;
  37.                 break;
  38.             }
  39.             m++;
  40.         }
  42.     } 
  43.     return 0;
  44. }

**Design Tutorial: Learn from Life **
题意：

  1. 有一个电梯，每一个人都想乘电梯到达自己想要到达的楼层！
  2. 从a层到b层的时间是|a-b|， 乘客上下电梯的时间忽略不计！问最少
  3. 需要多少的时间..

解题思路：

  1. 把输入的数组从大到小排序，楼层高的人上去之后自然楼层低的人能送到，然后计算时间输出就可以了。

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<cmath>
  7. using namespace std;
  8. int f[2010];
  9. bool cmp(int x,int y)
  10. {
  11.     return x>y;
  12. }
  13. int main()
  14. {
  15.     int n,k;
  16.     while(scanf("%d%d",&n,&k)!=EOF)
  17.     {
  18.         for(int i=1;i<=n;i++)
  19.         scanf("%d",&f[i]);
  20.         sort(f+1,f+n+1,cmp);
  21.         int ans=0;
  22.         for(int i=1;i<=n;i++)
  23.         {
  24.             if(i%k==1||k==1)
  25.             ans+=(f[i]-1)*2;
  26.         }
  27.         cout<<ans<<endl;
  28.     }
  29.     return 0;
  30. }

**Design Tutorial: Make It Nondeterministic **
题意：

  1. 每个人可以选择first name 或者 last name     当自己的账号，现在给出最终的字典序排位，问能不能实现

解题思路：

  1. 将first name 与last name 进行比较，如果字典序first name 大与last name的话就交换两个字符串，first name存小的字典序，按照给出的顺序进行比较，如果如果前面的人
  2. first name 大于后面人的last name ，则为NO。

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #define N 101234
  7. using namespace std;
  9. string fir[100860],las[100860];
  10. string tmp;
  11. int main()
  12. {
  13.     int n,m;
  14.     cin>>n;
  15.     for(int i=1;i<=n;i++)
  16.     {
  17.         cin>>fir[i]>>las[i];
  18.     }
  19.     tmp=" ";
  20.     bool flag=true;
  21.     for(int i=1;i<=n;i++)
  22.     {
  23.         cin>>m;
  24.         if(fir[m]>las[m])
  25.         {
  26.             swap(fir[m],las[m]);
  27.         /// flag=true;
  28.         }
  29.         if(tmp<=fir[m])
  30.         {
  31.             tmp=fir[m];
  32.         }else if(tmp<=las[m])
  33.         {
  34.             tmp=las[m];
  35.         }else
  36.         {
  37.             flag=false;
  38.             break;
  39.         }
  40.     }
  41.     if(flag)
  42.     cout<<"YES"<<endl;
  43.     else
  44.     cout<<"NO"<<endl;
  45.     return 0;
  46. }

**MUH and Sticks **
题目大意：

  1. 给出6种长度的木棍，问能根据长度拼成哪种动物的形状。其中由脚、头和身体构成。脚为4个一样的长度，如果头和身体长度一样为大象，不一样为熊。否则为异形。

解题思路：

  1.  将不同长度的木棍进行计数，然后判断满足存在长度是四根或者四根以上，并且存在两根不相同，就是熊。存在长度大于等于四根，存在两根相同的话，就是大象，否则异形。

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<cmath>
  7. using namespace std;
  8. int len[20],num[20];
  9. int main()
  10. {
  11.     int l;
  12.     memset(num,0,sizeof(num));
  13.     for(int i=0;i<6;i++)
  14.     {
  15.         scanf("%d",&len[i]);
  16.         l=len[i];
  17.         num[l]++;
  18.     }
  19.     int numh=0,numb=0,numl=0,ss=1;
  20.     for(int i=1;i<=9;i++)
  21.     {
  22.         if(num[i]==1)
  23.         numb++;
  24.         if(num[i]==2)
  25.         numh++;
  26.         if(num[i]>=4)
  27.         {
  28.             numl=4;
  29.             ss=num[i]-4;
  30.         }
  31.     }
  32.     if((numb==2&&numl==4)||(numb==1&&ss==1&&numh==0))
  33.     cout<<"Bear"<<endl;
  34.     else if((numh==1&&numl==4)||(ss==2&&numb==0&&numh==0))
  35.     cout<<"Elephant"<<endl;
  36.     else
  37.     cout<<"Alien"<<endl;
  38.     return 0;
  39. }
  40.  ```
  41. **MUH and Important Things **
  43.    题目大意：

有 n 个 tasks，编号依次为 1 ～ n，每个 task 都有一定的难度值来评估。例如，第 i 个 task 的难度值为 hi。现在的任务是把 n 个 task 全部完成，难度值越小的task越先完成。有3个人，都希望自己完成所有task的输出序列是与众不同的，问是否存在至少3条完成所有task的不同序列，没有的话输出“NO”，否则输出“YES”并输出3条不同的完成序列。

  1.   解题思路：

排序后，判断是否有重复的地方，然后就是依次交换

  1. ```c++
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<algorithm>
  6. #include<cmath>
  8. using namespace std;
  9. int num[2015];
  10. struct Node
  11. {
  12.     int h,w;
  13. }h[2015];
  14. bool cmp(Node x,Node y)
  15. {
  16.     return x.h<y.h;
  17. }
  18. int main()
  19. {
  20.     int n;
  21.     while(scanf("%d",&n)!=EOF)
  22.     {
  23.         memset(num,0,sizeof(num));
  24.         for(int i=1;i<=n;i++)
  25.         {
  26.             scanf("%d",&h[i].h);
  27.             h[i].w=i;
  28.             int nn=h[i].h;
  29.             num[nn]++;
  30.         }
  31.         int ans=1;
  32.         for(int i=1;i<=n;i++)
  33.         {
  34.             int nn=h[i].h;
  35.             //cout<<num[nn]<<endl;
  36.             ans=ans*num[nn];
  37.             if(ans>=3)
  38.             break;
  39.             num[nn]=1;
  40.         }
  41.         if(ans>=3)
  42.         printf("YES\n");
  43.         else
  44.         printf("NO\n");
  45.         sort(h+1,h+n+1,cmp);
  46.         if(ans>=3){
  47.         for(int i=1;i<=n;i++)
  48.         cout<<h[i].w<<" ";
  49.         cout<<endl;
  50.         int pp=1;
  51.         for(int i=1;i<=n;i++)
  52.         {
  53.             if(h[i].h==h[i+1].h)
  54.             {
  55.                 pp=i+1;
  56.                 int temp;
  57.                 temp=h[i].w;
  58.                 h[i].w=h[i+1].w;
  59.                 h[i+1].w=temp;
  60.                 break;
  61.             }
  62.         }
  63.         for(int i=1;i<=n;i++)
  64.         cout<<h[i].w<<" ";
  65.         cout<<endl;
  66.         for(int i=pp;i<=n;i++)
  67.         {
  68.             if(h[i].h==h[i+1].h)
  69.             {
  70.                 pp=i+1;
  71.                 int temp;
  72.                 temp=h[i].w;
  73.                 h[i].w=h[i+1].w;
  74.                 h[i+1].w=temp;
  75.                 break;
  76.             }
  77.         }
  78.         for(int i=1;i<=n;i++)
  79.         cout<<h[i].w<<" ";
  80.         cout<<endl;
  81.     }
  82.     }
  83.     return 0;
  84. }

**MUH and House of Cards **
题目大意：

  1. 求n根火柴搭建房屋的层数有多少种

解题思路：

  1. 要使n层火柴全部搭满，推出公式是（3*n+1）*n/2,每次判断一层是否满足条件，剩下的木棒数取余3是否为0，满足条件方案数就加一。

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<cmath>
  7. using namespace std;
  8. int main()
  9. {
  10.     long long n;
  11.     long long num=0;
  12.     cin>>n;
  13.     for(long long i=1;(3*i+1)*i/2<=n;i++)
  14.     {
  15.         if((n-(3*i+1)*i/2)%3==0)
  16.         num++;
  17.     }
  18.     cout<<num<<endl;
  19.     return 0;
  20. }

George and Accommodation
题意：

  1. 大致意思为求出能同时入住George和Alex的房间有多少间。

解题思路：

  1. 直接判断是否还能容下2个人

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cmath>
  5. #define N 101234
  7. using namespace std;
  8. int main()
  9. {
  10.     int a,b,n;
  11.     while(scanf("%d",&n)!=EOF)
  12.     {
  13.         int ans=0;
  14.         for(int i=0;i<n;i++){
  15.         cin>>a>>b;
  16.         if(b-a>=2)
  17.         ans++;
  18.     }
  19.         cout<<ans<<endl;
  20.     }
  21.     return 0;
  22. }

**Fedor and New Game **
题意：

  1. 给定n，m，k，n种士兵，m个部队，兵种不同数量小于等于k的为友军。然后给出m+1行，前m行表示需要判定的部队，第m+1行Fedor的部队。

解题思路：

  1. 直接取异或，找出不同种类的士兵数目，判断是否小于等于k。

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. int a[1025];
  7. int main()
  8. {
  9.     int n,m,k;
  10.     scanf("%d%d%d",&n,&m,&k);
  11.     for(int i=0;i<=m;i++)
  12.     scanf("%d",&a[i]);
  13.     int ss,num,fri=0;
  14.     for(int j=0;j<m;j++)
  15.     {
  16.         ss=a[m]^a[j];
  17.         num=0;
  18.         int mn=1;
  19.         for(int i=1;i<=n;i++)
  20.         {
  21.             if(mn&ss)
  22.             num++;
  23.             mn*=2;
  24.             if(num>k)
  25.             {
  26.                 break;
  27.             }
  28.         }
  29.         if(num<=k)fri++;
  30.     }
  31.     cout<<fri<<endl;
  32.     return 0;
  33. }

**Cheap Travel **
题意：

  1. 坐n次地铁，m张票卖b元，单张a元，问最小花费。

解题思路：

  1. 开始用贪心算法，比较m张便宜还是单张买便宜，如果买m张便宜的话，又要考虑是否m张和单张的一起买会跟便宜。

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<cmath>
  6. using namespace std;
  7. int main()
  8. {
  9.     int n,m,a,b;
  10.     cin>>n>>m>>a>>b;
  11.     double ave=(b*1.0)/m;
  12.     double c=a*1.0;
  13.     int x,y;
  14.     if(ave<c)
  15.     {
  16.         x=n/m;
  17.         y=n%m;
  18.         if(y*a<b)
  19.         cout<<x*b+y*a<<endl;
  20.         else
  21.         cout<<x*b+b;
  22.     }else
  23.     {
  24.         cout<<n*a<<endl;
  25.     }
  26.     return 0;
  27. }

**Wonder Room **
题意：

  1. a*b大小的房间要容纳n个人，每个人至少需要大小为6的空间，改变房间大小，使n个同学都能住进房间，改变后的房间尽可能小

解题思路：

  1. 先求出n个人所需空间的大小，然后枚举房间的长和宽，是得长>a,宽>b，找出最小的长和宽。

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<cmath>
  6. #define N 1e18+1e9
  7. using namespace std;
  8. int main()
  9. {
  10.     long long n,a,b;
  11.     cin>>n>>a>>b;
  12.     long long sun=6*n,ans=N;
  13.     long long s;
  14.     int flag=0;
  15.     if(a>b)
  16.     {
  17.         s=a;
  18.         a=b;
  19.         b=s;
  20.         flag=1;
  21.     }
  22.     long long aa,bb;
  23.     for(long long i=1;i<=sun;i++)   
  24.     {
  25.         long long x=i,y=(sun-1)/i+1;
  26.         if(x>y)break;
  27.         x=max(x,a);
  28.         y=max(y,b);
  29.     //  cout<<x<<" "<<y<<endl;
  30.         if(x*y<=ans)
  31.         {
  32.             ans=x*y;
  33.             aa=x;
  34.             bb=y;
  35.         }
  36.     }
  37.     if(flag)
  38.     {
  39.         s=aa;
  40.         aa=bb;
  41.         bb=s;
  42.     }
  43.     cout<<ans<<endl;
  44.     cout<<aa<<" "<<bb<<endl;
  45.     return 0;
  46. }

**Number of Ways **
题意：

  1. 将一列数分成连续的三份，每一份进行求和，使三份求得的和相等，问有把一组数分成三份有多少种方式。

解题思路：

  1. 将这一组数进行求和，除以3，定义一个sum数组保存前i项的和，然后对这组数进行遍历。第一个分割点是总和/3,第二个分割点是（2/3*总和），求出分割点的个数进行组合。

ac代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. #include<cmath>
  6. #define N 500010
  8. using namespace std;
  9. long long sum[N];
  10. int main()
  11. {
  12.     int n;
  13.     int a;
  14.     while(scanf("%d",&n)!=EOF)
  15.     {
  16.         memset(sum,0,sizeof(sum));
  17.         for(int i=1;i<=n;i++)
  18.         {
  19.             scanf("%d",&a);
  20.             sum[i]=sum[i-1]+a;
  21.         }
  22.         long long summ=sum[n];
  23.         long long ans1=0,ans2=0;
  24.         if(summ%3)
  25.         cout<<"0"<<endl;
  26.         else
  27.         {
  28.             summ=summ/3;
  29.             for(int i=1;i<n;i++)
  30.             {
  31.                 if(summ*2==sum[i])
  32.                 ans2+=ans1;
  33.                 if(summ==sum[i])
  34.                 ans1++; 
  35.             }
  36.             cout<<ans2<<endl;
  37.         }
  38.     }
  39.     return 0;
  40. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注