第一次集训队作业

题解

ProblemA: Design Tutorial: Learn from Math

题意：把一个数拆分为两个合数

题解：枚举并且得到的i和n－i分别check是否是合数，模拟即可。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
bool check(int n) 
{
    for (int i=2; i*i<=n; i++)
        if(n%i==0) return true;
    return false;
}
int main() 
{
    cin>>n;
    for(int i=4; i<=n/2; i++)
    {
        if(check(i) && check(n-i)) 
        {
            cout<<i<<" "<<n-i<<endl;
            break;
        }
    }
    return 0;
}

ProblemB:Design Tutorial: Learn from Life

题意：有n个人要到不同楼层去，但电梯只能装下K个人，不计上下的时间，问最少需要多少时间所有人可以达到自己的楼层。

题解：贪心，先将最高层的人运输完成，再运输下一层的人。

参考代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
int a[2002],ans,n,k;
int main()
{
    cin>>n>>k;
    for(int i=1; i<=n; i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=n; i>=1; i-=k)
    {
        ans+=2*(a[i]-1);
    }
    cout<<ans<<endl;
    return 0;
}

ProbelmC:Design Tutorial: Make It Nondeterministic

题意：每一个人都有frist name 和 last name。 从每一个人的名字中任意选择first name 或者 last name 作为这个人的编号，通过对编号的排序，得到每一个人的最终顺序，比较中的序列能否得到给定输出的序列一致。

题解：对输入的每个人的名字字符串排序。看看每个人排序后的number是不是和给出的相同。

参考代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;
string s1[100005],s2[100005],st;
int p[100005],n,x;
int main()
{
    cin>>n;
    for (int i=1; i<=n; i++)
        cin>>s1[i]>>s2[i];
    for (int i=1; i<=n; i++)
        cin>>p[i];
    for(int i=1; i<=n; i++)
    {
        x=p[i];
        if (s1[x]>s2[x]) swap(s1[x],s2[x]);
        if (st<s1[x]) st=s1[x];
        else if (st<s2[x]) st=s2[x];
        else
        {
            cout<<"NO"<<endl;
            return 0;
        }
    }
    cout<<"YES "<<endl;
    return 0;
}

ProblemD:留坑

ProblemE:MUH and Sticks

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

题解：判断棍子的长度，考虑是否有四根一样长的棍子，然后再判断剩下的棍子长度情况。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[105],l,sum1,sum2;
int main()
{
    for (int i=1; i<=6; i++)
    {
        cin>>l;
        a[l]++;
        if (a[l]==4) sum1=1;
        if (a[l]==6) sum2=1;
    }
    //cout<<sum1<<" "<<sum2<<endl;
    for (int i=1; i<10; i++)
        if (a[i]==2) sum2=1;
    if (sum1 && sum2) cout<<"Elephant"<<endl;
    else if (sum1 && !sum2) cout<<"Bear"<<endl;
    else cout<<"Alien"<<endl;
    return 0;
}

ProblemF:MUH and Important Things

题意：n个问题，每个问题都有对应的难度，求至少三个不同的序列使得做题的难度是非递减的。

题解：找到一个序列，然后组合。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
struct node
{
    int x,rank;
}a[10005];
int n,sum=1,t,j;
bool bo;
bool cmp(node a,node b)
{
    return a.x<b.x;
}
int main()
{
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i].x;
        a[i].rank=i;
    }
    sort(a+1,a+n+1,cmp);
    t=1;
    for (int i=2; i<=n; i++)
    {
        if (a[i].x==a[i-1].x) t++;
        else
        {
            sum*=t;
            t=1;
        }
        if (sum>=3)
        {
            bo=1;
            break;
        }
    }
    sum*=t;
    if (sum>=3) bo=1;
    if (!bo) cout<<"NO"<<endl;
    else
    {
        cout<<"YES"<<endl;
        for (int i=1; i<=n; i++) cout<<a[i].rank<<" ";
        cout<<endl;
        for (j=2; j<=n; j++)
            if (a[j].x==a[j-1].x)
            {
                swap(a[j],a[j-1]);
                break;
            }
        for (int i=1; i<=n; i++) cout<<a[i].rank<<" ";
        cout<<endl;
        for (int i=1; i<=n; i++)
            if(a[i].x==a[i-1].x && i!=j)
            {
                swap(a[i],a[i-1]);
                break;
            }
        for (int i=1; i<=n; i++) cout<<a[i].rank<<" ";
        cout<<endl;
    }
    return 0;
}

ProblemG:MUH and House of Cards

题意：用n张牌问按照题目要求能摆几层。

题解：每层的牌数为3t+2，先对x=n%3，当x=1时，最少有两个2，即最少有两层，当x=2时，最少有一层，x=3时最少有两层，刚好是x=3-x，现在假设有k层，最少为（3*0+2）+（3*1+2）+（3*2+2）+.......+（3*（k-1）+2<=n,然后再对层数加3，直到不满足上面的条件。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,ans,sum,t;
int main()
{
    cin>>n;
    if (n%3==0)
    {
        t=3;
        n-=6;
    }
    else
    if (n%3==1)
    {
        t=2;
        n-=4;
    }
    else
    {
        t=1;
        n-=2;
    }
    while(n>=0)
    {
        sum=(t-1)*t/2;
        if (n/3>=sum) ans++;
        else break;
        n-=6;
        t+=3;
    }
    cout<<ans<<endl;
    return 0;
}

ProblemH:

ProblemI:

题意：两个人去工作，希望在同一个房间并同时被叫到，问有几个房间满足。

题解：定义两个变量，分别为当前房间的人数和房间的总容纳量， 相减就是可以容纳的，大于等于二就计数一次。

参考代码：

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

ProblemJ:Fedor and New Game

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

题解：直接取亦或，然后判断1的个数是否小于等于k。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1005],x,n,m,k,ans,t;
int main() 
{
    cin>>n>>m>>k;
    for (int i=1; i<=m; i++) cin>>a[i];
    cin>>x;
    for (int i=1; i<=m; i++) 
       {
        t=0;
        for (int j=0; j<n; j++)
            if (((1<<j)&a[i])!=((1<<j)&x)) t++;
        if (t<=k) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

ProblemK:

题意：给定一个长度为n的序列，从序列中选出k个不重叠且连续的m个数，要求和最大。

题解：dp[i][j]表示到第i个位置选了j个子序列。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long n,m,k,ans,t,a[10005],sum[10005],dp[5005][5005];
int main ()
{
    cin>>n>>m>>k;
    for (long long i=1; i<=n; i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for (long long i=m; i<=n; i++)
    {
        t=sum[i]-sum[i-m];
        for (long long j=1; j<=k; j++)
            dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+t);
        ans=max(ans,dp[i][k]);
    }
    cout<<ans<<endl;
    return 0;
}

ProblemL:

ProblemM:Cheap Travel

题意：坐n次地铁，m张票卖b元，单张a元，问最小花费。

题解：直接做吧。。。。。。

参考代码：

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

ProblemN:Wonder Room

题意：给定n，a，b，要求找到ai，bi，（ai≥a, bi≥b）并且ai∗bi≥6∗n，并且ai∗bi要尽量小。

题解：枚举ai，根据6n算出需要的bi。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
long long n,a,b,ans,a1,b1,x,y,a2,b2;
bool bo;
int main ()
{
    bo=false;
    cin>>n>>a>>b;
    n*=6;
    a2=a;
    b2=b;
    ans=0x3f3f3f3f3f3f3f3f;
    if (a2>b2)
    {
        swap(a2,b2);
        bo=true;
    }
    for (long long i=1; i<=n; i++)
    {
        x=i;
        y=(n-1)/i+1;
        if (x>y) break;
        x=max(x,a2);
        y=max(y,b2);
        if (x*y<ans)
        {
            ans=x*y;
            a1=x;
            b1=y;
        }
    }
    if (bo) swap(a1,b1);
    cout<<ans<<endl;
    cout<<a1<<" "<<b1<<endl;
    return 0;
}

ProblemO:Number of Ways

题意：给你一串数让你分成平均三分，问共有多少种分法。

题解：若平分分成若干种情况，应当整体考虑，对sum/3进行分析。它是区分3段的标准。所以当部分和tmp==sum/3,部分统计＋1。当tmp==sum*2/3，则全部统计ans+=部分统计。

参考代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long a,t,sum,b[500005],ans,n;
int main()
{
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>a;
        sum+=a;
        b[i]=sum;
    }
    for (int i=1; i<=n; i++)
    {
        if (i>1 && i<n && b[i]*3==b[n]*2)
            ans+=t;
        if (b[i]*3==b[n])
            t++;
    }
    cout<<ans<<endl;
}

ProblemP: