[关闭]
@PaulGuan 2016-12-08T14:06:06.000000Z 字数 6738 阅读 909

CQUPT Training Nov28th - Dec3rd

banner.jpg-269kB

算法 题解

A - Design Tutorial: Learn from Math

题目大意

给出一个数n(12<=n<=10^6)， 求两个数x和y的其中一个值，要求x和y是合数且x+y=n。

思路

筛法预处理小于n的素数，然后穷举寻找即可。

代码

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.     bool vis[1000005];
  5. int main(void)
  6. {
  7.     memset(vis,false,sizeof(vis));
  8.     int n;
  9.     cin>>n;
  10.     int i,j;
  11.     for(i=2;i<=1000000;i++)
  12.         if(!vis[i])
  13.             for(j=i*2;j<=1000000;j+=i)
  14.                 vis[j]=true;
  15.     for(i=4;i<=1000000;i++)
  16.     {
  17.         if(!vis[i])
  18.             continue;
  19.         if(vis[n-i])
  20.         {
  21.             cout<<i<<" "<<n-i<<endl;
  22.             break;
  23.         }
  24.     }
  25.     return 0;
  26. }

B - Design Tutorial: Learn from Life

题目大意

有n个人，给出每个人期望到达的楼层和一个电梯的容量k(1 ≤ n, k ≤ 2000)，电梯每经过一层耗时一个单位，其余事项均不耗时，求电梯运完所有人的最小耗时。

思路

电梯每一次运输的耗时只和将要到达最高楼层相关。贪心，用计数方法记录每个人到达的楼层数，然后从大到小选择即可。

代码

  1. #include <iostream>
  2. using namespace std;
  3.     int flag[2005]={0};
  4. int main(void)
  5. {
  6.     int n,k;
  7.     cin>>n>>k;
  8.     int i;
  9.     for(i=0;i<n;i++)
  10.     {
  11.         int a;
  12.         cin>>a;
  13.         flag[a]++;
  14.     }
  15.     int v=k,ans=0;
  16.     for(i=2000;i>=2;i--)
  17.     {
  18.         while(flag[i])
  19.         {
  20.             if(v==k)
  21.             {
  22.                 if(flag[i]>=v)
  23.                 {
  24.                     flag[i]-=v;
  25.                     v=0;
  26.                 }
  27.                 else
  28.                 {
  29.                     v-=flag[i];
  30.                     flag[i]=0;
  31.                 }
  32.                 ans+=(i-1)<<1;
  33.             }
  34.             else
  35.             {
  36.                 if(flag[i]>=v)
  37.                 {
  38.                     flag[i]-=v;
  39.                     v=0;
  40.                 }
  41.                 else
  42.                 {
  43.                     v-=flag[i];
  44.                     flag[i]=0;
  45.                 }
  46.                 if(!v)
  47.                     v=k;
  48.                 continue;
  49.             }
  50.             if(!v)
  51.                 v=k;
  52.         }
  53.     }
  54.     cout<<ans<<endl;
  55.     return 0;
  56. }

C - Design Tutorial: Make It Nondeterministic

题目大意

有n个人，给出每个人的姓和名，每个人用姓或者名参与一次字典序排序，给出一个排序顺序，问能否按照给出的顺序成功对这n个人进行字典序从小到大排序。

思路

贪心，每个人都在比上一个人大的字符串中选择最小的一个。
对于每个人，选取姓和名中在满足比给出顺序的上一个人选出的字符串的字典序大的情况下，字典序较小的一个。如果到某个人选不出来，则无法按给出顺序排序。

代码

  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.     string name[2][100005];
  5.     int p[100005];
  6.     bool flag[100005];
  7. int main(void)
  8. {
  9.     int n;
  10.     cin>>n;
  11.     int i;
  12.     for(i=1;i<=n;i++)
  13.         cin>>name[0][i]>>name[1][i];
  14.     for(i=1;i<=n;i++)
  15.         cin>>p[i];
  16.     if(name[0][p[1]]<name[1][p[1]])
  17.         flag[p[1]]=0;
  18.     else
  19.         flag[p[1]]=1;
  20.     for(i=1;i<=n-1;i++)
  21.     {
  22.         string si=name[flag[p[i]]][p[i]];
  24.         bool ma;
  25.         string sma;
  26.         bool mi;
  27.         string smi;
  28.         if(name[0][p[i+1]]>=name[1][p[i+1]])
  29.         {
  30.             ma=0;
  31.             sma=name[0][p[i+1]];
  32.             mi=1;
  33.             smi=name[1][p[i+1]];
  34.         }
  35.         else
  36.         {
  37.             mi=0;
  38.             smi=name[0][p[i+1]];
  39.             ma=1;
  40.             sma=name[1][p[i+1]];
  41.         }
  42.         if(smi>si)
  43.         {
  44.             flag[p[i+1]]=mi;
  45.         }
  46.         else if(sma>si)
  47.         {
  48.             flag[p[i+1]]=ma;
  49.         }
  50.         else
  51.         {
  52.             cout<<"NO"<<endl;
  53.             return 0;
  54.         }
  55.     }
  56.     cout<<"YES"<<endl;
  57.     return 0;
  58. }

E - MUH and Sticks

题目大意

给出6个数，如果4个相等，2个不等，则是Beer，如果4个相等，两个相等，则是Elephant，其他情况则是Alien。

思路

判断6个数的相等情况即可。

代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5.     int arr[10]={0};
  6. int main(void)
  7. {
  8.     int i;
  9.     for(i=1;i<=6;i++)
  10.     {
  11.         int a;
  12.         cin>>a;
  13.         arr[a]++;
  14.     }
  15.     sort(arr,arr+10);
  16.     if(arr[9]<4)
  17.     {
  18.         cout<<"Alien"<<endl;
  19.         return 0;
  20.     }
  21.     arr[9]-=4;
  22.     sort(arr,arr+10);
  23.     if(arr[8]==0)
  24.         cout<<"Elephant"<<endl;
  25.     else
  26.         cout<<"Bear"<<endl;
  27.     return 0;
  28. }

F - MUH and Important Things

题目大意

有n个任务，给出每个任务的难度值（可能有相等的），要求在满足难度值从小到大排序的情况下，有至少3种不同的索引值排序方法，并输出其中3种排序。

思路

易见，如果有至少3个任务的难度值相同，或者至少两个不同的2个任务的难度值相同，则可以满足有至少3种不同的排序方法，输出排序时，可以用STL algorithm 中的next_permutation函数求下一个排列。

代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6.     vector <int> arr[2005];
  7.     vector <int> oput[3];
  8. int main(void)
  9. {
  10.     int n;
  11.     cin>>n;
  12.     int i,j,k;
  13.     for(i=1;i<=n;i++)
  14.     {
  15.         int a;
  16.         cin>>a;
  17.         arr[a].push_back(i);
  18.     }
  19.     int sum=0;
  20.     for(i=1;i<=2000;i++)
  21.     {
  22.         if(arr[i].size()>1)
  23.             sum+=arr[i].size();
  24.     }
  25.     if(sum<=2)
  26.     {
  27.         cout<<"NO"<<endl;
  28.         return 0;
  29.     }
  30.     cout<<"YES"<<endl;
  31.     int cnt=2;
  32.     for(i=1;i<=2000;i++)
  33.     {
  34.         if(arr[i].size()==0)
  35.             continue;
  36.         if(arr[i].size()==1)
  37.         {
  38.             oput[0].push_back(arr[i][0]);
  39.             oput[1].push_back(arr[i][0]);
  40.             oput[2].push_back(arr[i][0]);
  41.             continue;
  42.         }
  43.         for(k=0;k<arr[i].size();k++)
  44.         {
  45.             oput[0].push_back(arr[i][k]);
  46.         }
  47.         if(!(cnt%2))
  48.             next_permutation(arr[i].begin(),arr[i].end());
  49.         for(j=1;j<3;j++)
  50.         {
  51.             for(k=0;k<arr[i].size();k++)
  52.             {
  53.                 oput[j].push_back(arr[i][k]);
  54.             }
  55.             next_permutation(arr[i].begin(),arr[i].end());
  56.         }
  57.         cnt++;
  58.     }
  59.     for(i=0;i<3;i++)
  60.     {
  61.         for(j=0;j<oput[i].size();j++)
  62.         {
  63.             cout<<oput[i][j];
  64.             if(j!=oput[i].size()-1)
  65.                 cout<<" ";
  66.         }
  67.         cout<<endl;
  68.     }
  69.     return 0;
  70. }

G - MUH and House of Cards

题目大意

给出棍子的个数n，两个棍子组成一个屋子，两个屋子之间要有一个棍子作为天花板（如图右），问在棍子全部利用完的情况下，可以有不同高度的数量。

图左并不符合要求，而图右符合

思路

我们可以发现，每一层房子的棍子个数是2+3+3+...+3的数量，进一步分析，搭一层房子的棍子数k满足k mod 3 = 2 搭两层房子的棍子数满足 k mod 3 =1 搭三层满足 k mod 3 = 0 ……
同时我们也知道，要得到最高的层数，每一层的房子要最少，那么可以先找出有剩余的情况下，能达到的最高层数m。那么，ans就是在m及以内，所有符合上面取模条件的层数，我们可得公式：
    ans*3+(k mod 3)=m
    answer=[ans]
求解即可。

代码

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

I - George and Accommodation

题目大意

给出n个房间，求有多少个房间的剩余空间>=2.

思路

水题，判断即可。

代码

  1. #include <iostream>
  2. using namespace std;
  3. int main(void)
  4. {
  5.     int n,ans=0;
  6.     cin>>n;
  7.     int i;
  8.     for(i=0;i<n;i++)
  9.     {
  10.         int p,q;
  11.         cin>>p>>q;
  12.         if(q-p>=2)
  13.             ans++;
  14.     }
  15.     cout<<ans<<endl;
  16.     return 0;
  17. }

J - Fedor and New Game

题目大意

给出n种士兵和m+1个玩家，每个玩家有这n种士兵中的一些，用一个整数的二进制位表示是否拥有，如果前m个玩家和玩家m+1最多有k种不同，则是玩家m+1的朋友，问玩家m+1有多少朋友。

思路

对两个玩家的值进行异或，异或结果为1的二进制位则是不同的，判断即可。

代码

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.     int pler[1005];
  5. int one(int x)
  6. {
  7.     int ans=0;
  8.     while(x)
  9.     {
  10.         if(x%2)
  11.             ans++;
  12.         x>>=1;
  13.     }
  14.     return ans;
  15. }
  16. int main(void)
  17. {
  18.     int n,m,k,x_or,num,ans=0;
  19.     cin>>n>>m>>k;
  20.     int i,j;
  21.     for(i=0;i<=m;i++)
  22.         cin>>pler[i];
  23.     for(i=0;i<m;i++)
  24.     {
  25.         x_or=pler[i]^pler[m];
  26.         num=one(x_or);
  27.         if(num<=k)
  28.             ans++;
  29.     }
  30.     cout<<ans<<endl;
  31.     return 0;
  32. }

K - George and Job

题目大意

有n个数，在这n个数中选出k组不相交的数，每组有m个数，找到能将这些选中的数的和最大的办法，输出这种方式下这些数的和。

思路

应该用dp来做，但是本弱的dp的姿势水平还不够，还是用了相较于dp更为熟悉的记忆化搜索的办法，居然没有超时，实在是感人啊。
run函数的两个参数n和k代表在前n个数和在前n个数选出k组，dp数组保存这种情况下和的最大值。
现给出状态转移方程：
    f(n,k)=max{f(n-1,k),f(n-m，k-1)+p[n]-p[n-m]};
m是每组的数的个数，p数组是n个数的前缀和。

代码

  1. #include <iostream>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5.     long long p[5005];
  6.     long long dp[5005][5005];
  7.     int m;
  8. long long run(int n,int k)
  9. {
  10.     if(dp[n][k]!=-1)
  11.         return dp[n][k];
  12.     if(n<1)
  13.         return 0;
  14.     if(k==0)
  15.         return dp[n][k]=0;
  16.     long long t=-1;
  17.     if(n-m>=0)
  18.         t=run(n-m,k-1)+p[n]-p[n-m];
  19.     t=max(t,run(n-1,k));
  20.     return dp[n][k]=t;
  21. }
  22. int main(void)
  23. {
  24.     int n,k;
  25.     cin>>n>>m>>k;
  26.     memset(dp,-1,sizeof(dp));
  27.     int i;
  28.     for(i=1;i<=n;i++)
  29.     {
  30.         cin>>p[i];
  31.         p[i]+=p[i-1];
  32.     }
  33.     long long ans=run(n,k);
  34.     cout<<ans<<endl;
  35.     return 0;
  36. }

M - Cheap Travel

题目大意

某人要乘坐n次地铁，现有单次票和k次票若干，问怎么选择使其乘坐费用最小，输出最小费用。

思路

题本身不难，但是有很多特殊情况，比如n<k，还有很多在生活中不可能的情况，比如k次票的性价比不如单次票，或者k次票的价格比单次票还便宜，所以WA了几发。

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. int main(void)
  5. {
  6.     int n,m,a,b;
  7.     int cost=0;
  8.     cin>>n>>m>>a>>b;
  9.     double bi=(double)b/(double)m;
  10.     if(n>=m)
  11.         {
  12.         if(bi>(double)a)
  13.             cost=n*a;
  14.         else
  15.         {
  16.             cost+=(n/m)*b;
  17.             cost+=min((n%m)*a,b);
  18.         }
  19.     }
  20.     else
  21.         cost=min(b,n*a);
  22.     cout<<cost<<endl;
  23.     return 0;
  24. }

N - Wonder Room

题目大意

思路

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cmath>
  4. using namespace std;
  5. int main(void)
  6. {
  7.     long long n,a,b;
  8.     long long ans=100000000000000,ax,ay;
  9.     cin>>n>>a>>b;
  10.     n*=6;
  11.     if(a*b>=n)
  12.     {
  13.         cout<<a*b<<endl;
  14.         cout<<a<<" "<<b<<endl;
  15.         return 0;
  16.     }
  17.     long long m=(long long)sqrt((double)n);
  18.     long long i;
  19.     for(i=a;i<=m;i++)
  20.     {
  21.         long long y=n/i;
  22.         if(n%i)
  23.             y++;
  24.         y=max(y,b);
  25.         if(i*y==n)
  26.         {
  27.             cout<<i*y<<endl;
  28.             cout<<i<<" "<<y<<endl;
  29.             return 0;
  30.         }
  31.         if(i*y<ans)
  32.         {
  33.             ans=i*y;
  34.             ax=i;
  35.             ay=y;
  36.         }
  37.     }
  38.     for(i=b;i<=m;i++)
  39.     {
  40.         long long y=n/i;
  41.         if(n%i)
  42.             y++;
  43.         y=max(y,a);
  44.         if(i*y==n)
  45.         {
  46.             cout<<i*y<<endl;
  47.             cout<<y<<" "<<i<<endl;
  48.             return 0;
  49.         }
  50.         if(i*y<ans)
  51.         {
  52.             ans=i*y;
  53.             ax=y;
  54.             ay=i;//
  55.         }
  56.     }
  57.     cout<<ans<<endl;
  58.     cout<<ax<<" "<<ay<<endl;
  59.     return 0;
  60. }

O - Number of Ways

题目大意

给出n个整数，要求将这些数分成3份，每份的数的和相等。

思路

首先，我们可以求出这堆数/3的值，如果不能被整除，那肯定是没招的，你不可能把他们分成小数，如果可以被整除，那么通过其前缀和，找到前缀和为sum/3和(sum/3)*2的即可。

代码

  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4.     long long fir[500005];
  5. int main(void)
  6. {
  7.     int n;
  8.     long long ans1=0,ans2=0;
  9.     cin>>n;
  10.     int i;
  11.     for(i=1;i<=n;i++)
  12.     {
  13.         cin>>fir[i];
  14.         fir[i]+=fir[i-1];
  15.     }
  16.     if(fir[n]%3)
  17.     {
  18.         cout<<"0"<<endl;
  19.         return 0;
  20.     }
  21.     if(n<3)
  22.     {
  23.         cout<<"0"<<endl;
  24.         return 0;
  25.     }
  26.     long long aver=fir[n]/3;
  27.     for(i=1;i<n;i++)
  28.     {//cout<<fir[i]<<endl;
  29.         if(fir[i]==aver*2)
  30.             ans2+=ans1;
  31.         if(fir[i]==aver)
  32.             ans1++;
  33.     }
  34.     cout<<ans2<<endl;
  35.     return 0;
  36. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注