第一次作业：

题解：

A题：Design Tutorial: Learn from Math

题意：给你一个数n，你要找到两个复数加起来等于这个n，就是x+y=n；
12 ≤n.。
我的思路：是把n分成两部分，去判断这两部分是否是复数，就行了。

#include <bits/stdc++.h>
using namespace std;
int Search(int a,int b);
int main()
{
    int n,a,b;
    scanf("%d",&n);
    if(n%2==0)
    {
        a=n/2;
        b=n/2;
    }
    else
    {
        a=n/2;
        b=a+1;
    }
    while(1)
    {
    int p=Search(a,b);
    if(p)
    {
        printf("%d %d\n",a,b);
        break;
    }
    else
    {
        a--;
        b++;
        if(a<=2||b>=n)
            return 0;
    }
    }
    return 0;
}
int Search(int a,int b)
{
    int fa=0;
    int fb=0;
    for(int i=2;i<=a/2;i++)
    {
        if(a%i==0)
        {
            fa=1;
            break;
        }
    }
    for(int j=2;j<=b/2;j++)
    {
        if(b%j==0)
        {
            fb=1;
            break;
        }
    }
    if(fa&&fb)
        return 1;
    else
        return 0;
}

B题；Design Tutorial: Learn from Life

题意；有一群人坐电梯，电梯最多能坐k个人，有n个人。叫你计算出电梯最少要经过的楼数。
我的思路是：从头到尾要先把去楼层高的人先走，在回来拉楼层低的人，直到拉完。先排个序，然后直接拉。

#include <bits/stdc++.h>
using namespace std;
int cmp(int a,int b);
int a[2005];
int main()
{
    int q=0,n,k,ans=0;
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a,a+n,cmp);
    while(q<(n/k+1)&&a[q*k]!=0)
    {
        ans=ans+2*(a[q*k]-1);
        q++;
    }
    printf("%d\n",ans);
    return 0;
}
int cmp(int a,int b)
{
    return a>b;
}

-

C题：Design Tutorial: Make It Nondeterministic

题意：给你N个人的名字，每个人的名字是由两部分组成，就是姓和名，每个人可以用姓或则名带代替自己。
下面会给你一组编号，问你是否可以把这些人排序成给你的编号的顺序。可以就YES，不可以就NO。
解题思路；我把所有人的姓名分成了两个名字，但是它们还是指向一个人的。这里用了一个结构体，里面有名字，和编号，编号就是这个名字的主人，然后放在一起排序。排序完成后，就去里面找有没有给出的那一组排序编号。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
struct Person
{
    char name[55];
    int vex;
};
Person p[200086];
int b[100005];
bool cmp(const Person a,const Person b);
int main()
{
    int n,x=1,flag=0,counter=0,y=0,u=0,o=1;
    scanf("%d",&n);
    for(int i=0;i<2*n;i++)
    {
        scanf("%s",p[i].name);
       // cout<<p[i].name<<endl;
        getchar();
    }
    for(int j=0;j<2*n;j+=2)
    {
        scanf("%d",&b[y++]);
        p[j].vex=o;
        p[j+1].vex=o;
        o++;
    }
    sort(p,p+2*n,cmp);
    for(int i=0;i<2*n;i++)
    {
        if(p[i].vex==b[u])
        {
            u++;
            counter++;
        }
        if(counter==n)
        {
            flag=1;
            break;
        }
    }
    if(flag)
        printf("YES\n");
    else
        printf("NO\n");
    return 0;
}
bool cmp(const Person a,const Person b)
{
    return strcmp(a.name,b.name)<0;
}

E题：MUH and Sticks
思路：直接暴力判断。我这里设置的是两个flag标记，输出的时候就根据这个来输出就行了。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int cmp(int a,int b);
int a[15];
int main()
{
    int flag=0,n=0,flag2=0,l,p=6;
    while(p--)
    {
        scanf("%d",&l);
        a[l]++;
        if(a[l]==4)
            flag=1;
        if(a[l]==1)
            n++;
    }

    if(flag==1)
    {
        sort(a,a+15,cmp);
        for(int i=0;i<n;i++)
        {
            if(a[i]>=4)
                a[i]=a[i]-4;
        }
        for(int i=0;i<n;i++)
        {
            if(a[i]==2)
                flag2=1;
        }
        if(flag2)
            printf("Elephant\n");
        else
            printf("Bear\n");
    }
    else
        printf("Alien\n");
    return 0;
}
int cmp(int a,int b)
{
    return a>b;
}

F题：MUH and Important Things
题目题意：给了你n个数，然后叫你判断能不能把他们非递减排序，而且你你能输出三种不同位置的非递减的顺序，能就YES不能就NO。
思路：我这里也是暴力，如果有三个数字相同，就可以，或者是两个不相同的数字有2个。都可以实现。我们要记录下个数有超过2的数字的位置，然后在输出的时候输出一个就交换他们的位置，再输出另一个。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
struct task
{
    int vex;
    int data;
};
task a[2050];
int flag[2005];
bool cmp(const task a,const task b);
int main()
{
    int n,p=0,j,q=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i].data);
        a[i].vex=i+1;
        flag[a[i].data]++;
        if(flag[a[i].data]==2)
        {
            p++;
        }
        if(flag[a[i].data]==3)
        {
            q++;
        }
    }
    if(p>=2||q>=1)
    {
        printf("YES\n");
    sort(a,a+n,cmp);
    for(int i=0;i<n;i++)
    {
        printf("%d",a[i].vex);
        if(i!=n-1)
            printf(" ");
        else
            printf("\n");
    }
    for(j=1;j<n;j++)
    {
        if(a[j].data==a[j-1].data)
        {
            break;
        }
    }
    swap(a[j-1],a[j]);
    for(int i=0;i<n;i++)
    {
        printf("%d",a[i].vex);
        if(i!=n-1)
            printf(" ");
        else
            printf("\n");
    }
    for(j+=1;j<n;j++)
    {
        if(a[j].data==a[j-1].data)
        {
            break;
        }
    }
    swap(a[j-1],a[j]);
     for(int i=0;i<n;i++)
    {
        printf("%d",a[i].vex);
        if(i!=n-1)
            printf(" ");
        else
            printf("\n");
    }
    }
    else
        printf("NO\n");
    return 0;
}
bool cmp(const task a,const task b)
{
    return a.data<b.data;
}

G题：MUH and House of Cards
题意：这道题是给你n个卡，叫你堆房子，题中给了你两种算是可以堆成房子的样子，问你你能堆好多种楼高的房子。
思路：这里的一层楼到下一层楼的卡片数都是增加了3*n+2个，然后是一个mod3的规律。就直接搞出来了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=0x3f3f3f3f3f3f3f3f;
//bool cmp(const task a,const task b);
int main()
{
    LL n;
    scanf("%lld",&n);
    int mod=n%3;
    if(mod==0)
    {
        mod=3;
    }
    else
    {
        if(mod==2)
            mod=1;
        else if(mod==1)
            mod=2;
    }
    LL counter=0;
    for(LL i=mod;;i+=3)
    {
        LL mark=(3*pow(i,2)+i)/2;
        if(mark<=n)
            counter++;
        else break;
    }
    printf("%lld\n",counter);
    return 0;
}
/*bool cmp(const task a,const task b)
{
    return a.data<b.data;
}*/

I题：George and Accommodation
题意：给你一堆房间，前一个数字是现在的人数，后一个数字数这个房间能住多少人，这里我们要住下George and Alex.
思路：两个人，所以后一个减去前一个数字>=2就行了。

#include <bits/stdc++.h>
using namespace std;
int Search(int a,int b);
int main()
{
    int n,q,p,counter=0;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&p,&q);
        if((q-p)>=2)
            counter++;
    }
    printf("%d\n",counter);
    return 0;
}

J题：Fedor and New Game
题意：总的说来就是把前m个的二进制和第m+1个比较，不同的数量小于K的就是朋友，就这样。
思路：直接暴力。
a & (1 << j ) 表示数a二进制的第j 位是什么。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int a[1010];
//bool cmp(const task a,const task b);
int main()
{
    int n,m,k,x,ans=0;
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&x);
    for(int i = 1; i <= m; i++)
    {
        int res=0;
        for(int j = 0; j < n; j++)
        {
            if((a[i]&(1<<j)) != (x&(1<<j)))
                res++;
        }
        if(res<=k)
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}
/*bool cmp(const task a,const task b)
{
    return a.data<b.data;
}*/

K题：George and Job
题意：就是给你一些限制，然后要去长度为多少的多少段区间，得到的值最大是多少。
思路：直接dp，dp[i][j];ij表示的是到第i个数字时去了j段的最大值，dp完了就行了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
bool cmp(int a,int b);
LL dp[5005][5005];
LL a[5005],sum[5005];

const LL INF=0x3f3f3f3f3f3f3f3f;
int main()
{
    LL n,m,k,ans=0,temp;
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    for(int i= m;i<=n;i++)
    {
        temp=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]+temp);
                ans=max(ans,dp[i][k]);
            }
        }
    }
    printf("%lld\n",ans);
    return 0;
}
bool cmp(int a,int b)
{
    return a>b;
}

M题：Cheap Travel
题意：我们需要买n张票，每张票价钱是a，我们也可以花b钱买m张票，要求钱最少；
思路：也是直接搜一遍，之一各种情况就行了，比如有一点，有时候我们可以买的票超过n张，反而比买n张的钱少。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
//bool cmp(const task a,const task b);
int main()
{
    int n,m,a,b,ans=0;
    scanf("%d%d%d%d",&n,&m,&a,&b);
    if((float)b/m<=a)
    {
        ans=((int)(n/m))*b;
        n=n%m;
        if(n)
        {

            ans+=min(n*a,b);
        }
    }
    else
    {
        ans+=n*a;
    }

    printf("%d\n",ans);
    return 0;
}
/*bool cmp(const task a,const task b)
{
    return a.data<b.data;
}*/

N题：Wonder Room
题意：这里有n个学生，每个学生至少得有6meter的房间，所以就是6*n的面积。我们可以扩大任何一边的长度，只能扩大，问你尽可能小的情况。
思路：我们这里也是暴力搜索，搜完，如果中途出现了刚好等于我们需要的6*n的情况，就输出，如果一直没出现，就搜完，然后不断更新最小值，在最后输出。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=0x3f3f3f3f3f3f3f3f;
int main()
{
    LL a1,b1,n,a,b,tmp,counter=0,ans=6000000000;
    bool flag=false;
    scanf("%I64d%I64d%I64d",&n,&a,&b);
    LL s=6*n;
    if(a*b>=s)
    {
        printf("%I64d\n",a*b);
        printf("%I64d %I64d\n",a,b);
        return 0;
    }
    else
    {
    if(b<a)
    {
        swap(a,b);
        flag=true;
    }
    for(LL i=a;i<s;i++)
    {
        counter++;
        tmp=s/i;
        if(tmp*i<s)
            tmp++;
        if(tmp<b)
            break;
        if(i*tmp<ans)
        {
            ans=i*tmp;
            //cout<<"###"<<ans<<endl;
            a1=i;
            b1=tmp;
            if(flag)
                swap(a1,b1);
        }
        else if(i*tmp==s)
        {
            printf("%I64d\n",i*tmp);
            if(flag) swap(i,tmp);
            printf("%I64d %I64d\n",i,tmp);
            return 0;
        }
        else if(i*tmp>ans&&counter>80000)
        {
            break;
        }
        else
            continue;
    }
    }
    printf("%I64d\n",a1*b1);
    printf("%I64d %I64d\n",a1,b1);
    return 0;
}

O题：Number of Ways
题意：题意是把一个数组分成3段，然后每段的值都得相等，有几种情况，输出。
思路：我把前n个数字和记录在了sun[n]里，然后把等于sum[n]/3的位置放在一个vector数组里面去，就是把所有sum[n]/3的位置记录下来，然后从后面去找值等于sum[n]/3的位置，刚才放进vector里面的比他小的就算一个，遍历完就行了。

#include <bits/stdc++.h>
#include <vector>
using namespace std;
typedef long long LL;
bool cmp(int a,int b);
const LL INF=0x3f3f3f3f3f3f3f3f;
LL sum[500005];
LL a[500005];
vector<LL>mark1;
int main()
{
    LL counter=0,n,tmp,p=0;
    scanf("%lld",&n);
    for(long i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
    }
    if(sum[n]%3||n<3)
    {
        printf("%d\n",0);
        return 0;
    }
    else
    {
        tmp=sum[n]/3;
        for(LL i=1;i<n;i++)
        {
            if(sum[i]==tmp)
                mark1.push_back(i);
        }
        //cout<<mark1.size()<<" "<<mark2.size()<<endl;
        for(int i=n;i>0;i--)
        {
            p+=a[i];
            if(p==tmp)
            counter+=lower_bound(mark1.begin(),mark1.end(),i-1)-mark1.begin();
        }
    }
    printf("%lld\n",counter);
    return 0;
}
bool cmp(int a,int b)
{
    return a>b;
}