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

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


题解:
A Design Tutorial: Learn from Math

题目大意:

  1. 给定一个n12<=n<=10^6),求出符合以下要求的xy
  2. 1.x+y=n
  3. 2.xy都是合数

解题思路:

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

ac代码:

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

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

**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
  6. using namespace std;
  7. string fir[100860],las[100860];
  8. string tmp;
  9. int main()
  10. {
  11. int n,m;
  12. cin>>n;
  13. for(int i=1;i<=n;i++)
  14. {
  15. cin>>fir[i]>>las[i];
  16. }
  17. tmp=" ";
  18. bool flag=true;
  19. for(int i=1;i<=n;i++)
  20. {
  21. cin>>m;
  22. if(fir[m]>las[m])
  23. {
  24. swap(fir[m],las[m]);
  25. /// flag=true;
  26. }
  27. if(tmp<=fir[m])
  28. {
  29. tmp=fir[m];
  30. }else if(tmp<=las[m])
  31. {
  32. tmp=las[m];
  33. }else
  34. {
  35. flag=false;
  36. break;
  37. }
  38. }
  39. if(flag)
  40. cout<<"YES"<<endl;
  41. else
  42. cout<<"NO"<<endl;
  43. return 0;
  44. }

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

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

解题思路:

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

ac代码:

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

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

**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>
  6. using namespace std;
  7. int main()
  8. {
  9. long long n;
  10. long long num=0;
  11. cin>>n;
  12. for(long long i=1;(3*i+1)*i/2<=n;i++)
  13. {
  14. if((n-(3*i+1)*i/2)%3==0)
  15. num++;
  16. }
  17. cout<<num<<endl;
  18. return 0;
  19. }

George and Accommodation
题意:

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

解题思路:

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

ac代码:

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

**Fedor and New Game **
题意:

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

解题思路:

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