[关闭]
@iamtts 2016-12-05T16:02:02.000000Z 字数 6550 阅读 1078

第一次作业题解

A - Design Tutorial: Learn from Math

题目大意：

给定一个数n，求这样一对数x，y，满足：
1.x，y都是合数
2.x+y=n

解题思路：

从合数4开始搜索x，判断y=n-x是否为合数，并且x也是合数，找到一组数就跳出，并输出。

AC代码：

  1. #include<stdio.h>
  2. int notprime(long long n)
  3. {
  4.     long long i;
  5.     for (i=2;i*i<=n;i++)
  6.         if (n%i==0) return 1;
  7.     return 0;
  8. }
  9. int main()
  10. {
  11.     long long n,i,temp;
  12.     scanf("%I64d",&n);
  13.     temp=n/2+1;
  14.     for (i=4;i<=temp;i++)
  15.         if (notprime(i))
  16.     {
  17.         if (notprime(n-i)) {
  18.             printf("%I64d %I64d",i,n-i);
  19.             break;
  20.         }
  21.     }
  22. }

B - Design Tutorial: Learn from Life

题目大意：

给定总人数，电梯最大容量，以及每个人的楼层数，电梯在每层之间移动消耗一个时间单位，要求输出运送完乘客的最少时间数

解题思路：

贪心算法，最优策略是让楼层高的乘客优先上电梯，有空位就捎带次最高楼层的，这样从2000层往前搜索，空楼层跳过，有人下的楼层进行电梯人数填充操作并且记录电梯内的最高楼层，一旦电梯满员就计算一次往返的时间，然后清空电梯。

AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int stair[2005],fi[2005];
  4. int main()
  5. {
  6.     int n,k,carrier=0,i,ans=0,record=0;
  7.     scanf("%d%d",&n,&k);
  8.     for (i=0;i<n;i++)
  9.     {
  10.         scanf("%d",&fi[i]);
  11.         stair[fi[i]-1]++;
  12.     }
  13.     for (i=1999;i>=0;stair[i]==0?i--:i+=0)
  14.     {
  15.         if (stair[i])
  16.         {
  17.             if (carrier==0) record=i;
  18.             if (carrier+stair[i]<=k)
  19.             {
  20.                 carrier+=stair[i];
  21.                 stair[i]=0;
  22.             }
  23.             else
  24.             {
  25.                 stair[i]-=k-carrier;
  26.                 carrier=k;
  27.             }
  28.         }
  29.         if (carrier==k || i==0)
  30.         {
  31.             ans+=record*2;
  32.             carrier=0;
  33.             record=0;
  34.         }
  35.     }
  36.     printf("%d",ans);
  38. }

C - Design Tutorial: Make It Nondeterministic

题目大意：

给定n个人，每个人有前名和后名，每个人按输入顺序编号，紧接着输入一串整数pi（每个人的编号），要求按pi的顺序，是否存在一列字符串满足：
1.每个字符串是pi号人的前名或后名
2.字符串按pi顺序依次递增

解题思路：

贪心算法，第一个人取最小名，第二个人如果最小名比它大，则第二个人的字符串确定为最小名，否则，确定为最大名，重复操作直到末尾或者无法继续递增。

AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int n,i,j=1;
  7.     int pi[100005];
  8.     string first[100005],last[100005],record;
  9.     cin>>n;
  10.     for (i=1;i<=n;i++)
  11.         cin>>first[i]>>last[i];
  12.     for (i=1;i<=n;i++)
  13.         cin>>pi[i];
  14.     record=last[pi[1]]<first[pi[1]]?last[pi[1]]:first[pi[1]];
  15.     for (i=2;i<=n;i++)
  16.     {
  17.         string temp1_min=last[pi[i]]<first[pi[i]]?last[pi[i]]:first[pi[i]];
  18.         string temp1_max=last[pi[i]]<first[pi[i]]?first[pi[i]]:last[pi[i]];
  19.     if (record<=temp1_min) {record=temp1_min;continue;}
  20.     else if (record<=temp1_max)
  21.         {
  22.             record=temp1_max;
  23.             continue;
  24.         }
  25.     else {j=0;break;}
  26.     }
  27.     if (j==1) cout<<"YES"<<endl;
  28.        else cout<<"NO"<<endl;
  30. }

E - MUH and Sticks

题目大意：

给定6个数，如果有4个一样的数，这四个数为腿长，那么一定是bear或者，elephant，否则为alien。如果剩下两个数相等则为bear，否则为elephant，因为elephant的鼻子长2333

解题思路：

将6个数排序，找到4个一样的，如果找不到为alien，找到四个一样的如果为elephant的话剩下三种情况（第一项等于第二项，第一项等于最后一项，最后一项等于倒数第二项），一一判别，否则为bear。

AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int a[6],b[6]={0},i,start=-1,end=-1,count=0;
  6.     for (i=0;i<6;i++)
  7.         scanf("%d",&a[i]);
  8.     sort(a,a+6);
  10.     for (i=0;i<5;i++)
  11.     {
  12.         if (a[i]==a[i+1] &&a[i+1]==a[i+2] && a[i+2]==a[i+3])
  13.         {
  14.             end=i+3;
  15.             count=3;
  16.         }
  17.         start=end-3;
  18.         if (start==0) {b[0]=a[4];b[1]=a[5];}
  19.         if (start==1) {b[0]=a[0];b[1]=a[5];}
  20.         if (start==2) {b[0]=a[0];b[1]=a[1];}
  21.     }
  22.     //for (i=0;i<6;i++)
  23.     //printf("%d",b[i]);
  24.     if (count!=3) printf("Alien");
  25.     else
  26.     {
  27.         sort(b,b+6);
  28.         if (b[4]==b[5]) printf("Elephant");
  29.         else  printf("Bear");
  30.     }
  32. }

F - MUH and Important Things

题目大意：
给定n个数，每个数有编号，要求从小到大排列这n个数，相等的数字可以按编号进行排列组合，如果总排列数大于3，输出YES，否则输出NO
解题思路：
先sort这些数，输出YES的情况至少满足：
1.有至少两组，每组至少两个相同的数
2.有至少一组，含有至少三个相同的数
否则，输出NO
如果满足YES的条件，则记录相同数经过排序后的下标，然后swap编号，得出三组后即可输出。
AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. bool compare(vector<int> a,vector<int> b)
  5. {
  6.     return a[0]<b[0];
  7. }
  8. int main()
  9. {
  10.     vector<vector<int> > num;
  11.     vector<int> mem,output1;
  12.     int n,i,j=0,a,count=0,record[2],temp[2];
  14.     cin>>n;
  16.     for (i=0;i<n;i++)
  17.     {
  18.         cin>>a;
  19.         mem.push_back(a);
  20.         mem.push_back(i);
  21.         num.push_back(mem);
  22.         mem.clear();
  23.     }
  25.     sort(num.begin(),num.end(),compare);
  27.     for (i=0;i<n-1;i++)
  28.     {
  29.         if (count==2) break;
  30.         if (num[i][0]==num[i+1][0])
  31.         {
  32.             count++;
  33.             record[count-1]=i;
  34.             temp[count-1]=num[i][0];
  35.         }
  36.     }
  38.     for (i=0;i<n;i++)
  39.         output1.push_back(num[i][1]+1);
  41.     if (count==2)
  42.     {
  43.         printf("YES\n");
  44.         for (int m=0;m<n;m++)
  45.             printf("%d ",output1[m]);
  46.         printf("\n");
  47.         //printf("%d %d %d %d\n",temp[0],temp[1],record[0],record[1]);
  48.         if (temp[0]==temp[1])
  49.         {
  50.             swap(output1[record[0]],output1[record[0]+1]);
  51.             for (int m=0;m<n;m++)
  52.                 printf("%d ",output1[m]);
  53.             printf("\n");
  54.             swap(output1[record[0]+1],output1[record[0]+2]);
  55.             for (int m=0;m<n;m++)
  56.                 printf("%d ",output1[m]);
  57.             printf("\n");
  58.         }
  59.         else
  60.         {
  61.             swap(output1[record[0]],output1[record[0]+1]);
  62.             for (int m=0;m<n;m++)
  63.                 printf("%d ",output1[m]);
  64.             printf("\n");
  65.             swap(output1[record[1]],output1[record[1]+1]);
  66.             for (int m=0;m<n;m++)
  67.                 printf("%d ",output1[m]);
  68.             printf("\n");
  69.         }
  70.     }
  72.     else printf("NO\n");
  74. }

G - MUH and House of Cards

题目大意：
输入纸牌数n，要求使用恰好n张纸牌搭建出纸牌屋，每个纸牌屋呈人字形，每两个纸牌屋屋顶之间需要纸牌连接，求最多可搭建出多少种不同层数的纸牌屋。
解题思路：
根据规律计算出n层完整三角形纸牌屋的表达式：
n*(3*n+1)/2，对于in=i*(3*i+1)/2
如果（n-in)%3=0，那么这就表示在n满足搭建n层，且多余部分可以随意堆砌，但不将其堆至i+1层。
AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     long long  n,count=0;
  7.     cin>>n;
  8.     for (long long i=1;i*(3*i+1)/2<=n;i++)
  9.         if ((n-i*(3*i+1)/2)%3==0) count++;
  10.     cout<<count;
  11. }

I - George and Accommodation

题目大意：
输入t组数据，每组包含房间已经入住人数m，以及容纳量n
如果m-2>=n则可入住房间+1
输出可入住房间量
解题思路：
如题目大意
AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int main()
  4. {
  5.     int p[105],q[105],n,i,count=0;
  6.     scanf("%d",&n);
  7.     for (i=0;i<n;i++)
  8.         {
  9.             scanf("%d%d",&p[i],&q[i]);
  10.             q[i]-=2;
  11.             if (q[i]>=p[i]) count++;
  12.         }
  13.     printf("%d",count);
  14. }

J - Fedor and New Game

题目大意：
有n种军队，m+1个玩家，每个玩家对应一个数字，将数字转为二进制，将第m+1个玩家与其余玩家比较，如果二进制位不同位不超过k，那么可以添加好友，输出好友数。
解题思路：
用一个容器存储Fedor的二进制军队，然后将其余玩家的军队一一转成二进制与Fedor每一位进行比较，用计数器记录下可以成为friend的
玩家数目
AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int n,m,k,count=0;
  7.     vector<long long> army,bin;
  8.     cin>>n>>m>>k;
  9.     for(int i=0;i<=m;i++)
  10.     {
  11.         int temp;
  12.         cin>>temp;
  13.         army.push_back(temp);
  14.     }
  15.     for (int i=0;i<=n;i++)
  16.     {
  17.             bin.push_back(army[m]%2);
  18.             army[m]>>=1;
  19.     }
  20.     for (int i=0;i<m;i++)
  21.     {
  22.         int j=0;
  23.         for (int l=0;l<=n;l++)
  24.         {if (army[i]%2 != bin[l]) j++;
  25.         army[i]>>=1;}
  26.         if (j<=k) count++;
  27.     }
  28.     cout<<count;
  30. }

M - Cheap Travel

题目大意：
买票坐地铁，给定距离，有两种票：
第一种n元可以坐过n单位距离
第二种n元可以坐过m（m>=n）单位距离
求最小价格
解题思路：
计算第二种票的密度，即1元可以坐过的距离，如果大于1，则优先使用第二种票，如果不足就计算用第一种票补距离和用第二种票补距离加上之前买的票的最小值。
AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     int n,m,a,b,ans,density;
  7.     double temp1,temp2;
  8.     cin>>n>>m>>a>>b;
  9.     temp1=b;
  10.     temp2=m;
  11.     if ((temp1/temp2)<=a)
  12.     {
  13.         if (n%m==0) ans=n/m*b;
  14.         else
  15.         {
  16.             ans=min((n/m+1)*b,n/m*b+n%m*a);
  17.         }
  18.     }
  19.     else ans=n*a;
  20.     printf("%d",ans);
  22. }

N - Wonder Room

题目大意：
给定n，a，b，可以将a，b任意增大，输出a*b满足a*b>=6*n同时a*b最小
解题思路：
分两种情况：1·a*b>=s,这时不需要做任何处理，直接输出；2·a*b b1为n*6/a1，ans取a1*b1中最小值，直到a1>b1，这时情况会与前面重复，可以退出循环。最后输出答案前检查flag，如果前面交换过a与b的
值，要再交换回来。
AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. {
  6.     long long n,a,b,s,a1_r,b1_r,flag=0,ans=100000000000,temp,a1=0,b1=0,j=0;
  7.     cin>>n>>a>>b;
  8.     s=6*n;
  9.     if (a*b>=s)
  10.     {
  11.         cout<<a*b<<endl;
  12.         cout<<a<<" "<<b;
  13.     }
  14.     else
  15.     {
  16.         if (a>b) {swap(a,b);flag=1;}
  17.         for (long long i=1;i<=s;i++)
  18.         {
  19.             a1=i;
  20.             b1=(s+a1-1)/a1;
  21.             if (a1>b1) break;
  22.             a1=max(a1,a);
  23.             b1=max(b1,b);
  24.             if (a1*b1<ans)
  25.             {
  26.                 ans=a1*b1;
  27.                 a1_r=a1;
  28.                 b1_r=b1;
  29.             }
  30.         }
  31.         if (flag) swap(a1_r,b1_r);
  32.         cout<<ans<<endl;
  33.         cout<<a1_r<<" "<<b1_r;
  34.     }
  36. }

O - Number of Ways

题目大意：
给定一组数，要求将这组数分成和相同的三组，输出不同的种数。
解题思路：
如果总和不能整除三，那么输出0
否则储存下从左至右的和，再从右向左搜索和为总和2/3的记录点，遇到和为1/3的记录点则减一，输出和为1/3的点数和和为2/3的点数的乘积。
AC代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. long long s[1000000];
  5. int main()
  6. {
  7.     long long  n,count1=0,count2=0,sum=0,suml=0,summ=0,sumr=0,p;
  8.     vector<long long> num;
  9.     cin>>n;
  10.     for (long long i=0;i<n;i++)
  11.         {
  12.             long long temp;
  13.             cin>>temp;
  14.             num.push_back(temp);
  15.             sum+=temp;
  16.         }
  17.     if (sum%3 != 0) cout<<"0\n";
  18.     else
  19.     {
  20.         for (long long i=0;i<n;i++)
  21.             {s[i+1]=num[i]+s[i];
  22.             if (s[i+1]*3==sum) count1++;}
  23.         for (long long i=n;i>=1;i--)
  24.             {
  25.                 if (s[i]*3==sum) count1--;
  26.                 if (s[i]*3==sum*2 && i<n) count2+=count1;
  27.                 if (count1<=0) break;
  28.             }
  29.         cout<<count2;
  30.     }
  32. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注