第一次作业

题解

A Design Tutorial: Learn from Math

题目大意：

给你一个大于12的数n，让你将它分解为两个合数，使两个合数之和为n

解题思路：

任意一个大于12的偶数可分解为一个4和另一个合数，当为奇数时则一定可以分解一个偶合数和一个奇合数，从4开始每次+2，直至剩下的奇数为合数

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=1e6+5;
int prime[maxn],vis[maxn];
void getprime(){
    memset(vis,0,sizeof(vis));
    for(int i=2;i<maxn;i++){
        if(!vis[i]){
            for(int j=2*i;j<maxn;j+=i)
                vis[j]=1;
        }
    }
}
int main(){
    getprime();
    int n;
    cin>>n;
    int i=4;
    while(i<n){
        if(vis[n-i]){
            printf("%d %d\n",i,n-i);
            break;
        }
        i+=2;
    }
    return 0;
}

B Design Tutorial: Learn from Life

题目大意：

有1<=n<=2000个人，电梯的最大载客量1<=k<=2000，现有n个人前往各自想去的楼层，求电梯把所有的人送往相应的楼层且回到第一层所需的最短时间（初始时所有人都在第一层）

解题思路：

先将所有人运到所要去的最低楼层，再将剩下的所有人运往下一个最低楼层，以此类推，直到把最后的人送去要去的最低楼层，最后返回第一层，这样的方案时间最少。

AC代码：

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,k,a[2005],t,ans=0;
int main(){
    memset(a,0,sizeof(a));
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>t;
        a[t]++;
    }
    int j=1;
    for(int i=2;i<2001;i++){
        if(a[i]){
            ans+=(2*(i-j))*(n/k);
            if(n%k)
                ans+=2*(i-j);   //如果不能整除，则再运一次
            n-=a[i];
            j=i;

        }
    }
    cout<<ans<<endl;
    return 0;
}

C Design Tutorial: Make It Nondeterministic

题目大意：

给你1<=n<=10^5个人的名字，每个人都可以使用它的姓或者名，再给定一个顺序，问你是否能够实现这种排序
（字典序）

解题思路：

每个人在满足字典序大于等于前一个人的字典序的情况下都尽可能的去字典序较小的名字，如果其中有任意一个不满足这样的条件则直接跳出（不能成功），如果执行完毕则说明可以实现（ps：注意不是名字首字母的字典序，而是整个名字的字典序）

AC代码：

 #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
struct node{
    string f,l;
}a[100005];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].f>>a[i].l;
    int flag=1;
    int t;
    cin>>t;
    string tp1=min(a[t].f,a[t].l);
    for(int i=2;i<=n;i++){
        cin>>t;
        string tp2=a[t].f,tp3=a[t].l;
        if(tp2>=tp1&&tp3>=tp1)
            tp1=min(tp2,tp3);
        else if(tp2>=tp1&&tp3<tp1)
            tp1=tp2;
        else if(tp2<tp1&&tp3>=tp1)
            tp1=tp3;
        else {
            flag=0;
            break;
        }
    }
    if(flag)
        cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

E - MUH and Sticks

题目大意;

有6根小棍，用来组成熊或者大象，他们的脚都是用4根等长的小棍来组成，而熊的身子大于熊的头，而大象的身子和头是等长的（头，身和脚之间没有任何联系），问你6根小棍到底能组成熊，还是大象?如不能组成则输出”Alien“

解题思路：

只有6根，找到每种长度的数量，大象要么6根全部相等，要么有4根相等，其他两根相等；而要么有5根相等，要么四根相等，并且另外两根不等。

AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <string>
using namespace std;
int a[100];
bool cmp(int x,int y){
    return x>y;
}
int main(){
    int n;
    memset(a,0,sizeof(a));
    for(int i=1;i<=6;i++){
        cin>>n;
        a[n]++;
    }
    sort(a,a+100,cmp);
    if((a[0]==4&&a[1]==2)||a[0]==6)
        cout<<"Elephant"<<endl;
    else if((a[0]==4&&a[1]==1&&a[2]==1)||(a[0]==5&&a[1]==1))
        cout<<"Bear"<<endl;
    else cout<<"Alien"<<endl;
    return 0;

F - MUH and Important Things

题目大意：

有1<=n<=2000个tast，给出他们每个难度，他们的难易程度有些不一样，想先做难度小的，但难度相同的之间也有顺序，例如：1，3,3,1先做1还是先做4，是两种方案，问你是否能够实现3种方案。

解题思路：

开始以为是全排列，但题目只需要3个。所以，只要有1组3个及其以上tast的难度相等，例如1,1，1,2,3，那么满足条件。如果有2组及其以上2个tast难度相同，例如：1,1，2,2，3,4也满足条件。所以，就转变为找相同难度的组数，每组数目。如满足条件则交换相同的任意两个，则是两种方案。

AC代码：

  #include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <cmath>
using namespace std;
struct node{
        int m;
        int num;
}a[2005];
bool cmp(node x,node y){
        return x.m<y.m;
}
int vis[2005];
int main(){
        int n,t=0,flag1=0,flag2=0;
        memset(vis,0,sizeof(vis));
        cin>>n;
        for(int i=1;i<=n;i++){
                cin>>a[i].m;
                vis[a[i].m]++;
                if(vis[a[i].m]>2)
                        flag1=1;//找到有没有3个及其以上相同的难度的题
                else if(vis[a[i].m]==2){
                        t++;
                        if(t>=2)//如果有两组或者多组的2个难度的题
                                flag2=1;
                }
                a[i].num=i;
        }
        if(flag1==0&&flag2==0)
                cout<<"NO"<<endl;
        else{
                        cout<<"YES"<<endl;
                sort(a+1,a+n+1,cmp);
                for(int i=1;i<n;i++)
                        cout<<a[i].num<<" ";
                cout<<a[n].num<<endl;
                int time=1;
                for(int i=1;i<=n;i++){//每有两个相同的就可以得到两个序列
                        if(time==3) break;
                        else if(vis[a[i].m]==2){
                                vis[a[i].m]=0;
                                for(int j=1;j<i;j++)
                                        cout<<a[j].num<<" ";
                              cout<<a[i+1].num<<" "<<a[i].num;
                              if(i+1==n)
                                cout<<endl;
                              else cout<<" ";
                                for(int j=i+2;j<n;j++)
                                        cout<<a[j].num<<" ";
                                if(i+1<n) cout<<a[n].num<<endl;
                                time++;
                        }
                        else if(vis[a[i].m]>2)
                        {//如果有3个及其以上的则直接可以找到3个
                                for(int j=1;j<i;j++)
                                        cout<<a[j].num<< " ";
                                cout<<a[i+1].num<<" "<<a[i].num<< " ";
                                for(int j=i+2;j<n;j++)
                                        cout<<a[j].num<<" ";
                                cout<<a[n].num<<endl;
                                time++;
                                if(time==3）//ps:如果前面找出了两个，这里就只需找到一个即可
                                    break;
                                  for(int j=1;j<i;j++)
                                        cout<<a[j].num<< " ";
                                cout<<a[i+2].num<<" "<<a[i].num<< " "<<a[i+1].num;
                                if(i+2==n)
                                    cout<<endl;
                                else cout<<" ";
                                for(int j=i+3;j<n;j++)
                                        cout<<a[j].num<<" ";
                                if(i+2<n) cout<<a[n].num<<endl;
                                break;
                        }
                }
        }
        return 0;
}

G - MUH and House of Cards

题目大意：

用1<=n<=10^12根木棒，让你搭楼，问你用这些木棒可以搭多少种楼层的大楼。

解题思路：

搭每种楼层的大楼，必须数量先大于这种楼层最少需要的数目，并且每层的需要木棍的数目都是3的倍数+2，凭借这两个条件则可以判断。如果数目大于等于这种楼层最少需要的数目，并且总数减去每层减去2根后还是3的倍数，则说明可以拼出这种楼层。

AC代码：

  #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
long long dp[1000005],ans=0,n;
int main(){
    cin>>n;
    dp[1]=2;
    for(int i=2;i<=1000000;i++)
        dp[i]=dp[i-1]+2*i+i-1;
    for(int i=1;dp[i]<=n;i++){
        if((n-i*2)%3==0)
            ans++;
    }
    cout<<ans<<endl;
}

I - George and Accommodation

题目大意：

有1<=n<=100个房间，每个房间都可以住一定的人数，而且一些房间已经住了一些人了，问有多少房间还可以住下两个人。

解题思路：

遍历一次即可，每次判断可住人数减去已住人数是否大于等于2。

AC代码：

   #include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int main(){
    int n,ans=0,a,b;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        if(b-a>=2)
            ans++;
    }
    cout<<ans<<endl;
    return 0;
}

J - Fedor and New Game

题目大意：

有n, m, k (1 ≤ k ≤ n ≤ 20; 1 ≤ m ≤ 1000)，之后输入Xi，xi (1 ≤ xi ≤ 2n - 1),，如果任意两军队的二进制数不相同的个数不大于k，则两个军队为友军，问前m个军队中有多少个军队跟第m+1个军队为友军。

解题思路：

将前m个军队每个都与m+1个军队异或，如果异或结果中1的个数不大于k时，则说明这两个军队为友军。

AC代码：

  #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int a[1000000];
int main(){
        int n,k,m,ans=0;
        cin>>n>>m>>k;
        for(int i=1;i<=m+1;i++)
                cin>>a[i];
        for(int i=1;i<=m;i++){
                int t=0,cnt=1;
                int tp=a[i]^a[m+1];
                do{
                        if(cnt&tp)
                           t++;
                           cnt<<=1;
                }while(cnt<=tp);
                if(t<=k)
                ans++;
        }
        cout<<ans<<endl;
        return 0;
}

K - George and Job

题目大意：

现有三个数n, m and k (1 ≤ (m × k) ≤ n ≤ 5000). ，n表示有n个数，从n个数中选取k组连续且不重叠的m个数，问怎样取才能使其的和最大

解题思路：

首先这是一道dp题，dp[i][j]表示从前n个数中选取j组数出来，状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+tp)(tp表示前i个数中后m个数的和），意为：如果不取第i个数，则要从前i-1个数中选出j个，如果要取第i个那么前i个的后m个应该选取，则在前面的i-m个数中选取j-1组数，在这两种方案中取最大值。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=5005;
LL a[maxn],sum[maxn],dp[maxn][maxn],m,n,k,ans;
int main(){
    cin>>n>>m>>k;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for(int i=m;i<=n;i++){
        LL tp=sum[i]-sum[i-m];
        for(int j=1;j<=k;j++)
            dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+tp);  //如果去第i个字母。则从n-m中找出j-1个字符串（并求其最大值和取值）。如果不用第i个字母则在i-1个子母中找到j个串
        ans=max(ans,dp[i][k]);
    }
    cout<<ans<<endl;
}

**M - Cheap Travel **

题目大意：

Ann要坐地铁，她计划坐n次地铁，但购买m张票的价格和买一张的价格不一样，问怎样买票才能使买的钱最少。n,m,a,b分别表示计划乘坐n次，a表示一张票的价格，b表示m张票的价格。

解题思路：

先确定买m张票的单价是否比买一张票的价格低，如果买一张票价格低，则全部单买；否则尽可能多买m张票，如不能再买m张票时，则再买单票。ps：注意可以多买，如果全部买m张票，不单买，哪怕多买了也比买了m张票类型后再单买的价格便宜，那么选择多买。

AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int n,m,a,b;
    cin>>n>>m>>a>>b;
    double tp=(double)b/m;
    if(tp<a){
        int sum=0;
        if(n%m==0)
            cout<<b*(n/m)<<endl;
        else {
            int t1=b*(n/m);
            int t2=t1+b;
            t1+=a*(n%m);
            cout<<min(t1,t2)<<endl;
        }
    }
    else cout<<n*a<<endl;
    return 0;
}

**N - Wonder Room **

题目大意：

宿舍要扩建，住六人，要保证每人的平均面积至少为n，先给出 n, a and b (1 ≤ n, a, b ≤ 109) 分别表示每个学生至少需要面积，现在宿舍的长宽，为扩建后的最小面积为多少？此时的长宽为多少？

解题思路：

先考虑现在的房间面积是否满足，如果不满足的话，从宽开始遍历到sqrt(6*n),如果找到的i能整除6*n，判断此时的长，是否大于开始的长，如满足，就直接输出。如果不能整除，就将现在的面积与之前的最小面积比较，如果小就保存现在的长宽。

AC代码：

include

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
int main(){
    LL a,b,n,flag=0,ta,tb;
    scanf("%lld%lld%lld",&n,&a,&b);
    if(6*n<=a*b)
        cout<<a*b<<endl<<a<<" "<<b<<endl;
    else {
        LL tp1=min(a,b),tp2=max(a,b);
        LL Min=0x3f3f3f3f3f3f3f3f;
        for(LL i=tp1;i<=sqrt(6*n);i++){
            if(6*n%i==0&&6*n/i>=tp2){
                if(a<=b)
                    cout<<6*n<<endl<<min(i,6*n/i)<<" "<<max(6*n/i,i)<<endl;
                else cout<<6*n<<endl<<max(6*n/i,i)<<" "<<min(i,6*n/i)<<endl;
                flag=1;
                break;
            }
            else{
                if(Min>(6*n/i+1)*i&&(6*n/i+1)>=tp2){
                    ta=i;tb=6*n/i+1;
                    Min=(6*n/i+1)*i;
                }
            }
        }
        if(!flag){
            cout<<ta*tb<<endl;
            if(a<=b)
                cout<<min(ta,tb)<<" "<<max(ta,tb)<<endl;
            else cout<<max(ta,tb)<<" "<<min(tb,ta)<<endl;
        }
    }
    return 0;
}

**O - Number of Ways **

题目大意：

将n个数分为3段，使每段的和相等，问有多少种分发

解题思路：

先用sum【】数组保存每个数字到第一个数字的和。考虑总数能不能被3整除，如果能，遍历sum[i]找出总数/3的位置个数，没找到总数/3*2的位置，就加上前面找到总数/3位置的个数，（这样才不会重叠）。到最后得到的总数就是方案数，但这种做法，会忽略总数为0的请况，那么总数/3和总数/3*2就相等了。所以总数为0的情况则需要单独考虑。

AC代码：

  #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=5e5+5;
LL a[maxn],total,sum[maxn],cnt1,cnt2,n;
int main(){
    cin>>n;
    total=0,cnt1=0,cnt2=0;
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    if(sum[n]%3!=0)  cout<<0<<endl;
    else if(sum[n]==0){
        for(int i=1;i<=n;i++)
            if(!sum[i]) cnt1++;
        cout<<(cnt1-2)*(cnt1-2+1)/2<<endl;//总数为0的情况，先固定第一个位置在第一个则有n-2，固定在第二个为0的位置则有n-3个，以此类推，最后得到第一个位置在倒数第三个0位置，第二个位置在倒数第二个位置，得到方案数为1。
    }
    else {
        for(int i=1;i<=n;i++){
            if(sum[i]==double(sum[n]/3.0))
               cnt1++;
            else if(sum[i]==double(sum[n]/3.0*2))
                cnt2+=cnt1;//加上之前的总数/3的位置，避免重叠
        }
        cout<<cnt2<<endl;
    }
    return 0;
}