[关闭]
@xingxing 2016-12-08T22:49:49.000000Z 字数 7574 阅读 926

第一次作业

题解

[题目][A]

Design Tutorial: Learn from Math

题目大意：
给定一个n(12<=n<=10^6),输出符合条件的两个合数x,y，要求：x+y=n。

解题思路：
要满足x+y=n，即一个数x大于等于n/2，一个数y小于等于n/2，列举x和y，然后分别对x，y判断是否为合数。
时间复杂度O(n√n),空间复杂度(1)。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. using namespace std;
  6. int solve(int m)
  7. {
  8.     int i;
  9.     for(i = 2;i <= (int)sqrt(m);i++)
  10.     {
  11.         if(m % i == 0)
  12.         {
  13.             return 1;
  14.         }
  15.     }
  16.     return 0;
  17. }
  18. int main()
  19. {
  20.     int n;
  21.     int i;
  22.     while(scanf("%d",&n) != EOF)
  23.     {
  24.         for(i = n/2;i > 1;i--)
  25.         {
  26.             if(solve(i) && solve(n-i))
  27.             {
  28.                 printf("%d %d\n",i,n-i);
  29.                 break;
  30.             }
  31.         }
  32.     }
  33.     return 0;
  34. }

[题目][B]

Design Tutorial: Learn from Life

题目大意：
给出乘客数n和电梯一次性最大载客量k(1<=n,k<=2000)，以及n个乘客到达的目标楼层fi，(2<=f[i]<=2000)，电梯用1s上一层楼，人数载量与电梯运行时间无关。初始时，人们都在第一层，求出最少时间能把所有人都运完，并且电梯又回到一楼。

解题思路：
电梯初始时在一楼，最后也要回到一楼，即每次运完乘客都要回到一楼继续运。而无论如何，最高楼层的人是要通过电梯过去的，所以当前要用的最少时间要以最高楼层的人到达的楼数来决定。所以尽可能把高楼层的乘客运完，即对目标楼层数按降序排序，从大到小，每次不超过k的限度运。
时间复杂度O(n),空间复杂度O(1)。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. using namespace std;
  6. int f[2016];
  8. int main()
  9. {
  10.     int n,k;
  11.     int i;
  12.     int ans;
  13.     while(scanf("%d %d",&n,&k) != EOF)
  14.     {
  15.         ans = 0;
  16.         for(i = 0;i < n;i++)
  17.         {
  18.             scanf("%d",&f[i]);
  19.         }
  20.         sort(f,f+n);
  21.         if(n >= k)
  22.         {
  23.             for(i = n-1; i >= 0 && i+1 >= k;i -= k)
  24.             {
  25.                 ans += 2*(f[i] - 1);
  26.             }
  27.             if(i+1 < k && i >= 0)
  28.             {
  29.                 ans += (f[i]-1)*2;
  30.             }
  31.         }
  32.         else
  33.         {
  34.             ans += 2*(f[n-1]-1);
  35.         }
  36.         printf("%d\n",ans);
  37.     }
  38.     return 0;
  39. }

[题目][C]

Design Tutorial: Make It Nondeterministic

题目大意：
给出n个人(1<=n<=10^5)的名和姓，其中每个人的姓fi和名si由只含小写字母的字符串组成(1<=|fi|,|si|<=50)，并且这2n个姓、名互不相同。接着给出排列好的n个数据pi(1<=pi<=n)。判断这n个人的姓或名能否按字典序以所给出的数据列排序。

解题思路：
贪心。要尽可能满足所给出数据列的字典序，排在前面的人，应该选较小的名或姓作为它的handle。即，选择p1姓或名的最小字典序的，作为h1（p1的handle），然后每次判断一下后一个pi+1较大的字符串是否大于pi的字符串，尽可能选择pi+1较小的字符串作为hi+1，把满足要求的可能性扩大到最大。当某一时刻，hi比pi+1最小的字符串还大时，此时不能得到与数据列相吻合的字典序。
时间复杂度O(n),空间复杂度O(1)。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. using namespace std;
  6. const int maxx = 123456;
  7. typedef struct name
  8. {
  9.     char f[60],s[60];
  10.     int flag;
  11. }person;
  12. person a[maxx];
  14. int main()
  15. {
  16.     //freopen("in.txt","r",stdin);
  17.     int n;
  18.     int i;
  19.     int num;
  20.     char temp[60];
  21.     int flag1 = 0;
  23.     scanf("%d",&n);
  24.     for(i = 0;i < n;i++)
  25.     {
  26.         getchar();
  27.         scanf("%s",a[i].f);
  28.         getchar();
  29.         scanf("%s",a[i].s);
  30.         if(strcmp(a[i].f,a[i].s) >= 0) a[i].flag = 1;
  31.         else a[i].flag = 0;
  32.     }
  33.     for(i = 0;i < n;i++)
  34.     {
  35.         scanf("%d",&num);
  36.         if(i == 0 && a[num-1].flag == 1)
  37.         {
  38.             strcpy(temp,a[num-1].s);
  39.         }
  40.         else if(i == 0 && a[num-1].flag == 0)
  41.             strcpy(temp,a[num-1].f);
  42.         if(i != 0)
  43.         {
  44.             if(a[num-1].flag == 1)
  45.             {
  46.                 if(strcmp(temp,a[num-1].f) >= 0)
  47.                     flag1 = 1;
  48.                 else
  49.                 {
  50.                     if(strcmp(temp,a[num-1].s) >= 0)
  51.                         strcpy(temp,a[num-1].f);
  52.                     else strcpy(temp,a[num-1].s);
  53.                 }
  54.             }
  55.             else
  56.             {
  57.                 if(strcmp(temp,a[num-1].s) >= 0) flag1 = 1;
  58.                 else
  59.                 {
  60.                     if(strcmp(temp,a[num-1].f) >= 0)
  61.                         strcpy(temp,a[num-1].s);
  62.                     else strcpy(temp,a[num-1].f);
  63.                 }
  64.             }
  65.         }
  66.     }
  67.     if(flag1 == 1) printf("NO\n");
  68.     else printf("YES\n");
  69.     return 0;
  70. }

[题目][E]

MUH and Sticks

题目大意：
给出6个数li(1<=li<=9)，判断满足以下哪个条件：
（1）其中4个数相同，另外2个数一大一小，这两个数和另外的4个数没有绝对的大小关系时，输出Bear；
（2）4个数相同，另外2个数相等，这两个数和另外的4个数没有绝对的大小关系，此时输出Elephant；
（3）其余情况输出Alien.

解题思路：
因为6个数中，只有一组4个数相同，不会再有其他4个数相同的情况，所以先选出相同的四个数，再来判断剩下的2个数之间的关系。两个数只有两种关系，要么相等，要么不等，即在有4个数相同的前提下，分别为1和2的情况。当无法选出4个相同数时，此时为情况3。把i数字读入后，将个数计入ai。
时间复杂度O(1)，空间复杂度O(1)。

AC代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cstring>
  5. using namespace std;
  7. int a[20];
  9. int main()
  10. {
  11.     int i;
  12.     int len;
  13.     int flag1,flag2;
  15.     flag1 = 0,flag2 = 0;
  16.     for(i = 0;i < 6;i++)
  17.     {
  18.         scanf("%d",&len);
  19.         a[len]++;
  20.     }
  21.     for(i = 1; i <= 9; i++)
  22.     {
  23.         if(a[i] == 4)
  24.         {
  25.             flag1 = 1;
  26.         }
  27.         if(a[i] == 2)
  28.         {
  29.             flag2 = 1;
  30.         }
  31.         if(a[i] == 6)
  32.         {
  33.             flag1 = 1;
  34.             flag2 = 1;
  35.         }
  36.         if(a[i] == 5)
  37.         {
  38.             flag1 = 1;
  39.             flag2 = 0;
  40.         }
  41.     }
  42.     if(flag1 && flag2)
  43.        printf("Elephant\n");
  44.     else if(flag1 && flag2 == 0)
  45.        printf("Bear\n");
  46.     else printf("Alien\n");
  47.     return 0;
  48. }

[题目][F]

题目大意：
给出n(1<=n<=2000)个任务的难度hi(1<=hi<=2000).将n个任务按难度排序输出，当有相同难度的任务时，可以交换序号从而产生难度相同，而序列不同的几种方案。输出其中3种方案的序列，若没有3个则输出NO。

解题思路：
因为要输出3组不同的序列，即可以只考虑（1）同一个难度有3个及以上的数量；或者（2）2个相同难度的任务组数为2的，有2组及以上。把难度i的任务存入a[i]数组中，并保存总共的该难度的任务数量以及对应的序号。然后遍历这个结构体数组，看是否有3个及以上的难度任务，和2组以上2个某个难度的任务。如果符合情况1，则将大于或等于3的难度值的序号，取其中三个，排列输出三种，其余该难度下多的直接输出，其他的序号直接输出。整体输出保持不递减的顺序，同时注意输出空格的格式，如果为输出的第一个数，则数字前没有空格，否则每个数字前都有一个空格。如果符合情况2，则将其他n-2个难度值的任务序号，按难度值递增输出，当到达记录的两组难度值时，进行以下处理，将前一个难度值的2个任务序号排序，现在既有2组，然后后一个难度值的任务序号，只要在第三组改变一下顺序，就总共有3组输出。
时间复杂度O(n)，空间复杂度O(1)。

AC 代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. using namespace std;
  5. typedef struct task
  6. {
  7.     int pa[2016];
  8.     int num;
  9. }diff;
  10. diff a[2016];
  11. int h3,h1,h2;
  13. int main()
  14. {
  15.     int n;
  16.     int i,j;
  17.     int temp;
  18.     int len;
  19.     int flag1,flag2;
  20.     int cnt;
  21.     int order,zu;
  23.     while(scanf("%d",&n) != EOF)
  24.     {
  25.         for(i = 1;i <= 2000;i++)
  26.         {
  27.             a[i].num = 0;
  28.         }
  29.         for(i = 1;i <= n;i++)
  30.         {
  31.             scanf("%d",&temp);
  32.             len = a[temp].num;
  33.             a[temp].pa[len] = i;
  34.             a[temp].num++;
  35.         }
  36.         flag1 = 0,flag2 = 0;
  37.         cnt = 0;
  38.         h1 = 0,h2 = 0;
  39.         for(i = 1;i <= 2000;i++)
  40.         {
  41.             if(a[i].num >= 3)
  42.             {
  43.                 flag1 = 1;
  44.                 h3 = i;
  45.                 break;
  46.             }
  47.             if(a[i].num == 2 && h1 == 0)
  48.             {
  49.                cnt++;
  50.                 h1 = i;
  51.             }
  52.             else if(a[i].num == 2 && h2 == 0)
  53.             {
  54.                 cnt++;
  55.                 h2 = i;
  56.             }
  57.             if(cnt == 2)
  58.             {
  59.                 flag2 = 1;
  60.                 break;
  61.             }
  62.         }
  63.         order = 0,zu = 0;
  64.         if(flag1)
  65.         {
  66.             printf("YES\n");
  67.             while(zu <= 2)
  68.             {
  69.                 order = 0;
  70.                 for(i = 1; i <= 2000; i++)
  71.                 {
  72.                     if(i == h3)
  73.                     {
  74.                         if(order == 0)
  75.                         {
  76.                             if(zu == 0)
  77.                             {
  78.                                 printf("%d %d %d",a[i].pa[0],a[i].pa[1],a[i].pa[2]);
  79.                             }
  80.                             if(zu == 1)
  81.                             {
  82.                                 printf("%d %d %d",a[i].pa[1],a[i].pa[0],a[i].pa[2]);
  83.                             }
  84.                             if(zu == 2)
  85.                             {
  86.                                 printf("%d %d %d",a[i].pa[0],a[i].pa[2],a[i].pa[1]);
  87.                             }
  88.                             order += 3;
  90.                             for(j = 3; j < a[i].num; j++)
  91.                             {
  92.                                 printf(" %d",a[i].pa[j]);
  93.                                 order++;
  94.                             }
  96.                         }
  97.                         else
  98.                         {
  99.                             if(zu == 0)
  100.                             {
  101.                                 printf(" %d %d %d",a[i].pa[0],a[i].pa[1],a[i].pa[2]);
  102.                             }
  103.                             if(zu == 1)
  104.                             {
  105.                                 printf(" %d %d %d",a[i].pa[1],a[i].pa[0],a[i].pa[2]);
  106.                             }
  107.                             if(zu == 2)
  108.                             {
  109.                                 printf(" %d %d %d",a[i].pa[0],a[i].pa[2],a[i].pa[1]);
  110.                             }
  111.                             order += 3;
  113.                             for(j = 3; j < a[i].num; j++)
  114.                             {
  115.                                 printf(" %d",a[i].pa[j]);
  116.                                 order++;
  117.                             }
  118.                         }
  119.                     }
  120.                     else
  121.                     {
  122.                         for(j = 0; j < a[i].num; j++)
  123.                         {
  124.                             if(order == 0)
  125.                             {
  126.                                 printf("%d",a[i].pa[j]);
  127.                                 order++;
  128.                             }
  129.                             else
  130.                             {
  131.                                 printf(" %d",a[i].pa[j]);
  132.                                 order++;
  133.                             }
  134.                         }
  135.                     }
  137.                 }
  138.                 zu++;
  139.                 printf("\n");
  140.             }
  141.         }
  142.         else if(flag2)
  143.         {
  144.             printf("YES\n");
  145.             while(zu <= 2)
  146.             {
  147.                 order = 0;
  148.                 for(i = 1; i <= 2000; i++)
  149.                 {
  150.                     if(i == h1)
  151.                     {
  152.                         if(order == 0)
  153.                         {
  154.                             if(zu == 0) printf("%d %d",a[i].pa[0],a[i].pa[1]);
  155.                             if(zu == 1) printf("%d %d",a[i].pa[0],a[i].pa[1]);
  156.                             if(zu == 2) printf("%d %d",a[i].pa[1],a[i].pa[0]);
  158.                             order += 2;
  159.                         }
  160.                         else
  161.                         {
  162.                             if(zu == 0) printf(" %d %d",a[i].pa[0],a[i].pa[1]);
  163.                             if(zu == 1) printf(" %d %d",a[i].pa[0],a[i].pa[1]);
  164.                             if(zu == 2) printf(" %d %d",a[i].pa[1],a[i].pa[0]);
  166.                             order += 2;
  167.                         }
  168.                     }
  169.                     else if(i == h2)
  170.                     {
  171.                         if(order == 0)
  172.                         {
  173.                             if(zu == 0) printf("%d %d",a[i].pa[0],a[i].pa[1]);
  174.                             if(zu == 1) printf("%d %d",a[i].pa[1],a[i].pa[0]);
  175.                             if(zu == 2) printf("%d %d",a[i].pa[1],a[i].pa[0]);
  177.                             order += 2;
  178.                         }
  179.                         else
  180.                         {
  181.                             if(zu == 0) printf(" %d %d",a[i].pa[0],a[i].pa[1]);
  182.                             if(zu == 1) printf(" %d %d",a[i].pa[1],a[i].pa[0]);
  183.                             if(zu == 2) printf(" %d %d",a[i].pa[1],a[i].pa[0]);
  185.                             order += 2;
  186.                         }
  187.                     }
  188.                     else
  189.                     {
  190.                         for(j = 0;j < a[i].num;j++)
  191.                         {
  192.                             if(order == 0)
  193.                             {
  194.                                 printf("%d",a[i].pa[j]);
  195.                                 order++;
  196.                             }
  197.                             else
  198.                             {
  199.                                 printf(" %d",a[i].pa[j]);
  200.                                 order++;
  201.                             }
  202.                         }
  203.                     }
  204.                 }
  205.                 zu++;
  206.                 printf("\n");
  207.             }
  208.         }
  209.         else printf("NO\n");
  210.     }
  211.     return 0;
  212. }

[题目][I]

George and Accommodation

题目大意：
给出n(1<=n<=100)个房间的已住人数pi和房间容量qi(0<=pi<=qi<=100)，求qi-pi>=2个i的个数。

解题思路：
读入pi和qi，然后判断两者差值，若大于或等于2则结果加1.
时间复杂度O(n)，空间复杂度O(1)。

AC 代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. using namespace std;
  5. int main()
  6. {
  7.     int n;
  8.     int ans = 0;
  9.     int p,q;
  10.     scanf("%d",&n);
  11.     while(n--)
  12.     {
  13.         scanf("%d%d",&p,&q);
  14.         if(q-p >= 2) ans++;
  15.     }
  16.     printf("%d\n",ans);
  17.     return 0;
  18. }

[题目][J]

Fedor and New Game

题目大意：
有n个soldiers编号从0到n-1，m+1个player，编号从1到m+1.对于第m+1个player前的每个player的army数值xi进行判断，如果army的表达数xi与第m+1个player的二进制表达中"1"不同的地方不超过k那么第m+1个player的朋友数加1.(1<=k<=n<=20,1<=m<=1000,1<=xi<=2^n-1)

解题思路：
对前m个数的二进制"1"的位置与最后一个数的二进制"1"的位置进行判断，若位置不同数不超过k，则结果加1.把m+1个数转成二进制，然后把每一位数值保存在数组中，并且将数组中第一位拿来保存该数值转成二进制数后的位数。然后分别对前m个二进制位与最后一个数的二进制位进行比较，统计不同位的个数。
时间复杂度O(n)，空间复杂度O(1)。

AC 代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. using namespace std;
  6. int n,m,k;
  7. int a[1010][30];
  9. int main()
  10. {
  11.     int i,j;
  12.     int temp;
  13.     int ans = 0;
  14.     int cnt = 0;
  15.     scanf("%d%d%d",&n,&m,&k);
  16.     for(i = 0; i < m+1; i++)
  17.     {
  18.         scanf("%d",&temp);
  19.         j = 1;
  20.         while(temp != 0)
  21.         {
  22.             a[i][j] = temp % 2;
  23.             temp = temp / 2;
  24.             j++;
  25.         }
  26.         a[i][0] = j;
  27.     }
  28.     for(i = 0;i < m;i++)
  29.     {
  30.         cnt = 0;
  31.         for(j = 1;j <= a[i][0] && j <= a[m][0];j++)
  32.         {
  33.             if(a[i][j] != a[m][j]) cnt++;
  34.         }
  35.         if(j <= a[i][0])
  36.         {
  37.             for(;j <= a[i][0];j++)
  38.             {
  39.                 if(a[i][j] == 1) cnt++;
  40.             }
  41.         }
  42.         else
  43.         {
  44.             for(;j <= a[m][0];j++)
  45.             {
  46.                 if(a[m][j] == 1) cnt++;
  47.             }
  48.         }
  49.         if(cnt <= k) ans++;
  50.     }
  51.     printf("%d\n",ans);
  52.     return 0;
  53. }

[题目][M]

Cheap Travel

题目大意：
进行n次乘车，每次花a元，或者可以选择用b元一次性买好m次乘车的票。(1<=n,m,a,b<=1000)，求出要乘n次车最少花的钱。

解题思路：
判断b元m次车票的单价，与a进行比较，选择叫便宜的方式。如果m次车票更好，那么买n/m张m次车票，然后再看剩下的车票用a元票买便宜还是m次车票便宜。
时间复杂度O(1)，空间复杂度O(1)。

AC 代码：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. using namespace std;
  5. int main()
  6. {
  7.     int n,m,a,b;
  8.     int num;
  9.     double x;
  10.     int sum = 0;
  11.     scanf("%d%d%d%d",&n,&m,&a,&b);
  12.     x = (double)b/m;
  13.     if(x < (double)a)
  14.     {
  15.         num = n / m;
  16.         sum = num * b;
  17.         sum += min(b,a*(n % m));
  18.     }
  19.     else sum = n*a;
  20.     printf("%d\n",sum);
  21.     return 0;
  22. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注