CQUPT Training Nov28th - Dec3rd：

A - Design Tutorial: Learn from Math：
题意：
给出一个数，找出两个合数使他们的和为这个数
思路：
由于数据范围为10的六次方，所以先打出1到10的6次方的合数表，然后再把n分为2份，用判断组成的两份是否均为合数即可。
代码：

#include <stdio.h>
char prime[2000005];
int main(void)
{
    int n;
    for (int i = 2;i < 2000005;i++)
        prime[i] = 1;
    for (int i = 2;i * i < 2000005;i++)
        for (int j = 2;j * i <2000005;j++)
    {
        if (prime[i]) prime[i*j] = 0;
    }
    scanf("%d",&n);
    if (n % 2 == 0)
    {
        int right = n / 2;
        int left = n / 2;
        while (prime[left] == 1 || prime[right] == 1)
        {
            right++;
            left--;
        }
        printf("%d %d\n",left,right);
    }
    else
    {
        int left = n / 2;
        int right = n - n / 2;
        while (prime[left] == 1 || prime[right] == 1)
        {
            right++;
            left--;
        }
        printf("%d %d\n",right,left);
    }
    return 0;
}

B:Design Tutorial: Learn from Life

题意：
有若干个人要坐电梯，他们的目标楼层不一定相同。电梯有最大容量。电梯每次达到最大目标楼层后要返回第一层。问将所有的人送到目标楼层之后返回第一层所用的最短时间。
思路：
首先将目标楼层按降序进行排列，则每次都能够保证可以将花费时间最多的那一部分人送到目标楼层。按照贪心的思想，这样所花费的时间是最少的。
代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int a[2010];
bool cmp(int a,int b)
{
    return a > b;
}
int main(void)
{
    int n,k;
    long long ans = 0;
    int flag = 0;
    cin>>n>>k;
    for (int i = 0;i < n;i++)
        cin>>a[i];
    sort(a,a+n,cmp);
    for (int i = 0;i < n;i++)
    {
        if (i % k == 0)
        {
            ans += (a[i] - 1) * 2;
            flag = i;
        }
    }
    if (flag + k >= n)
        printf("%I64d\n",ans);
    else
    {
        ans += (a[flag + k] - 1) * 2;
        printf("%I64d\n",ans);
    }
    return 0;
}

C:Design Tutorial: Make It Nondeterministic
题意：
输入若干人的名字，名和姓，问是否存在一个序列包含每一个人的两个名字中的一个使得名字的字典序排列与输入的人的序列严格对应。
思路：
贪心。对于一个人来说，首先取他的字典序小的名字作为标准与下一个人的字典序较小的名字进行比较，若小于，则取下一个人的字典序小的名字做标准，否则就取字典序较大的。对于相邻的人，一直进行此种比较。直到发现不满足条件或者比较完毕。
代码：

#include <bits/stdc++.h>
using namespace std;
pair<string,string> p[100005];
int a[100005];
int main(void)
{
    int n;
    bool ans = true;
    cin>>n;
    for (int i = 1;i <= n;i++)
        cin>>p[i].first>>p[i].second;
    for (int i = 1;i <= n;i++)
        cin>>a[i];
    string t;
    if (p[a[1]].first > p[a[1]].second)
        t = p[a[1]].second;
    else
        t = p[a[1]].first;
    for (int i = 2;i <= n;i++)
    {
        if (p[a[i]].first > p[a[i]].second)
        {
            if (t < p[a[i]].second)
                t = p[a[i]].second;
            else if (t < p[a[i]].first)
                t = p[a[i]].first;
            else
                ans = false;
        }
        else
        {
            if (t < p[a[i]].first)
                t = p[a[i]].first;
            else if (t < p[a[i]].second)
                t = p[a[i]].second;
            else
                ans = false;
        }
    }
    if (ans)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}

E:MUH and Sticks
题意：
给出6根长棍，判断由这6根长棍组成的是大象，熊，还是外星人。
满足大象的条件是四根相同，其余两根也相同。
满足熊的条件是四根相同，剩下的两根不同。
外星人就是不满足以上的条件。
思路：
用几个判断解决，但是要考虑5根相同，6根相同的特殊情况。
代码：

#include <stdio.h>
int a[6];
int b[10];
int main(void)
{
    int flag1 = 0,flag2 = 0,flag3 = 0;
    for (int i = 0;i < 6;i++)
    {
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    for (int i = 0;i < 10;i++)
    {
        if (b[i] == 4)
        {
            flag1 = 1;
        }
        if (b[i] == 2)
            flag2 = 1;
        if (b[i] == 5)
        {
            flag1 = 1;
            flag2 = 0;
        }
        if (b[i] == 6)
        {
            flag1 = 1;
            flag2 = 1;
        }
    }
    if (flag1 && flag2)
        printf("Elephant\n");
    else if (flag1 && !flag2)
        printf("Bear\n");
    else
        printf("Alien\n");
    return 0;
}

F:MUH and Important Things

题意：
有n个任务，他们的难度是可以相同，可以不同的，动物必须按照难度的升序做任务，问是否有3个或3个以上的做任务的顺序。
思路：
只要有两个难度不同的任务数量都分别超过两个的，或者一个任务的数量超过3个，就满足条件。
代码：

#include <bits/stdc++.h>
using namespace std;
pair<int,int> p[2010];
int a[2010];
int main(void)
{
    int n;
    int sum = 0;
    bool ans = false;
    int k = 0,b[10] = {0,0};
    int j = 0;
    scanf("%d",&n);
    if (n == 1 || n == 2)
    {
        printf("NO\n");
        return 0;
    }
    for (int i = 1;i <= n;i++)
    {
        cin>>p[i].first;
        p[i].second = i;
    }
    sort(p+1,p+n+1);
    for (int i = 1;i <= n;i++)
        a[p[i].first]++;
    for (int i = 1;i <= 2000;i++)
    {
        if (a[i] >= 3) {ans = true;k = i;}
        else if (a[i] == 2)
        {
             if (sum >= 2)
                break;
             sum++;
             b[j++] = i;
        }
    }
    if (sum >= 2)
        ans = true;
    if (ans)
    {
        printf("YES\n");
        if (k)
        {
            int pos;
            for (int i = 1;i <= n - 1;i++)
                printf("%d ",p[i].second);
            printf("%d\n",p[n].second);
            for (int i = 1;i <= n;i++)
                if (p[i].first == k)
            {
                pos = i;
                break;
            }
            for (int i = 1;i < pos;i++)
                printf("%d ",p[i].second);
            printf("%d %d %d",p[pos+1].second,p[pos].second,p[pos+2].second);
            for (int i = pos+3;i <= n;i++)
                printf(" %d",p[i].second);
            printf("\n");
            for (int i = 1;i < pos;i++)
                printf("%d ",p[i].second);
            printf("%d %d %d",p[pos+2].second,p[pos].second,p[pos+1].second);
            for (int i = pos+3;i <= n;i++)
                printf(" %d",p[i].second);
            printf("\n");
        }
        else
        {
            int pos1,pos2;
            for (int i = 1;i <= n;i++)
                if (p[i].first == b[0])
            {
                pos1 = i;
                break;
            }
            for (int i = 1;i <= n;i++)
                if (p[i].first == b[1])
            {
                pos2 = i;
                break;
            }
            for (int i = 1;i <= n - 1;i++)
                printf("%d ",p[i].second);
            printf("%d\n",p[n].second);
            for (int i = 1;i < pos2;i++)
                printf("%d ",p[i].second);
            printf("%d %d",p[pos2+1].second,p[pos2].second);
            for (int i = pos2+2;i <= n;i++)
                printf(" %d",p[i].second);
            printf("\n");
            for (int i = 1;i < pos1;i++)
                printf("%d ",p[i].second);
            printf("%d %d",p[pos1+1].second,p[pos1].second);
            for (int i = pos1+2;i <= n;i++)
                printf(" %d",p[i].second);
            printf("\n");
        }
    }
    else
    {
        printf("NO\n");
    }
    return 0;
}

G:MUH and House of Cards
题意：
按照如图所示的方式搭建房子，给出n根棍子，问可以搭建的不同高度有多少种。
思路：
推一下公式，最节约的方式搭建的话，设高度为h，则需要的棍子为(3*h + 1) * h / 2；又因为每层的公式为3*n+2，所以说n-2h肯定为3的倍数，直接暴力枚举就可以了。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
    ll n;
    int ans = 0;
    scanf("%I64d",&n);
    for (ll h = 1;(3*h + 1) * h / 2 <= n;h++)
    {
        if ((n - 2*h) % 3 == 0)
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

I:George and Accommodation
题意：
给出若干间房里面已经住的人和房间的容量，问有多少房间可以同时住下两个人。
思路：可以略了
代码：

#include <cstdio>
int a[105];
int b[105];
int main(void)
{
    int n;
    int ans = 0;
    scanf("%d",&n);
    for (int i = 0;i < n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
        if (b[i] - a[i] >= 2)
            ans++;
    }
    printf("%d\n",ans);
}

J:Fedor and New Game
题意：
有m+1个数，如果说两个数的二进制数最多有k位不同，则他们就是朋友，问前m个人里面有多少人是第m+1人的朋友。
思路：
把每个数都转换成二进制数，再进行比较就行了。
代码：

#include <bits/stdc++.h>
using namespace std;
int a[2050];
int s[25];
void tos(int p[],int r)
{
    int cal = 0;
    while (r != 0)
    {
        p[cal++] = r % 2;
        r = r / 2;
    }
}
int main(void)
{
    int n,m,k;
    int ans = 0;
    scanf("%d%d%d",&n,&m,&k);
    for (int i = 1;i <= m+1;i++)
        scanf("%d",&a[i]);
    memset(s,-1,sizeof(s));
    tos(s,a[m+1]);
    for (int i = 1;i <= m;i++)
    {
        int temp[25];
        int t = 0;
        memset(temp,-1,sizeof(temp));
        tos(temp,a[i]);
        for (int j = 0;j < 25;j++)
        {
            if (s[j] == 1 && temp[j] == 0)
                t++;
            if (s[j] == 0 && temp[j] == 1)
                t++;
            if (s[j] == -1 && temp[j] == 1)
                t++;
            if (s[j] == 1 && temp[j] == -1)
                t++;
        }
        if (t <= k)
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

M:Cheap Travel
题意：
有两种火车票，一种是一趟a元，第二种是m趟b元。一个人需要乘坐火车n趟，问此人花的最少钱是多少。
思路：
算出第二种票一趟所花的钱，再进行比较即可。
代码：

#include <stdio.h>
#include <math.h>
const float dec = 1e-6;
int main(void)
{
    int n,m,a,b;
    int sum = 0;
    scanf("%d%d%d%d",&n,&m,&a,&b);
    float ev = (float)b / m;
    if (fabs(ev - a) < dec)
    {
        sum = a * n;
    }
    else if (ev - a > dec)
    {
        sum = a * n;
    }
    else if (a - ev > dec)
    {
        int t = n / m;
        int res = n % m;
        if (t * b + res * a <= (t + 1) * b)
            sum = t * b + res * a;
        else
            sum = (t + 1) * b;
    }
    printf("%d\n",sum);
    return 0;
}

N：Wonder Room
题意：
给出一间房的长和宽，有若干人要住进去，每人占的空间单位为6，如果房间不够大，就需要进行改造，问如果改造，则房间面积最小是多少，改造后的长和宽必须大于等于原来的。
思路：
枚举一边，就相当于求最大公约数的思路，这边的平方不能超过n*6，然后再求另一边就ok。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(void)
{
    ll n,a,b;
    ll ans = 1e18;
    ll p,q;
    scanf("%I64d%I64d%I64d",&n,&a,&b);
    n *= 6;
    if (a * b >= n)
        printf("%I64d\n%I64d %I64d\n",a*b,a,b);
    else
    {
        int t = 0;
        if (a > b)
        {
            ll c = a;
            a = b;
            b = c;
            t = 1;
        }
        for (ll i = a;i * i <= n;i++)
        {
            ll temp = n / i;
            if (i * temp < n) temp++;
            if (temp < b) continue;
            if (i * temp < ans)
            {
                ans = i * temp;
                p = i;
                q = temp;
            }
        }
        if (t)
        {
            int c = p;
            p = q;
            q = c;
        }
        printf("%I64d\n%I64d %I64d\n",ans,p,q);
    }
    return 0;
}

O:Number of Ways
题意：
给出n个数，找出有多少种方法使得可以将n个数分成连续的三部分，使得三部分的和相等。
思路：
从前往后找，找出和为1/3的，进行标记，为前缀数组。然后从后往前找，用前缀数组记录的位置进行寻找。
代码：

#include <bits/stdc++.h>
using namespace std;
int a[500006];
int pre[500006];
int main(void)
{
    int n;
    int j = 0;
    long long sum = 0;
    long long ans = 0;
    scanf("%d",&n);
    for (int i = 1;i <= n;i++)
        scanf("%d",&a[i]);
    for (int i = 1;i <= n;i++)
    {
        sum += a[i];
    }
    if (sum % 3 != 0)
        ans = 0;
    else
    {
        long long t = 0;
        for (int i = 1;i <= n;i++)
        {
            t += a[i];
            if (t == sum / 3)
                pre[j++] = i;
        }
        t = 0;
        for (int i = n;i >= 1;i--)
        {
            t += a[i];
            if (t == sum / 3)
            {
                int pos = lower_bound(pre,pre+j,i - 1) - pre;
                ans += pos;
            }
        }
    }
    printf("%I64d\n",ans);
    return 0;
}