Two progressions(CodeForces-125D)【鸽巢原理】

题意：将一列数划分为两个等差数列。

思路：首先，我要吹爆鸽巢原理！！！真的很强大的东西！！！

　　　　加入能完成题设操作，则前三个数中，必有至少两个数在同一序列，枚举三种情况（a1 a2,a2 a3,a1 a3分别为等差数列的前两项）。

　　　　注：枚举情况时，如果操作失败，则将已成功生成的等差数列末项划分到另一个数列试试。（稍作思考即可）

代码如下：

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

int n,arr[],book[];

bool judge(){

    int ps,gap;

    int t1=,t2;

    while(t1<=n&&book[t1]) t1++;

    t2=t1+;

    if(t1>n)

        return false;

    while(t2<=n&&book[t2]) t2++;

    if(t2>n)

        return true;

    gap=arr[t2]-arr[t1];

    ps=t2;

    for(int i=t2+;i<=n;i++)

        if(!book[i]){

        if(arr[i]-arr[ps]==gap)

            ps=i;

        else

            return false;

        }

    return true;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        scanf("%d",&arr[i]);

    if(n==)

        printf("%d\n%d",arr[],arr[]);

    else {

        int x[]={arr[]-arr[],arr[]-arr[],arr[]-arr[]};

        int flag=;

        for(int i=;i<;i++){

            int st=,tmp=arr[];

            memset(book,,sizeof(book));

            if(i==){

                book[]=book[]=;

                st=;

                tmp=arr[];

            }

            else if(i==)

                book[]=book[]=;

            else

                book[]=book[]=;

            for(int ii=st;ii<=n;ii++)

                if(arr[ii]==tmp+x[i]){

                    book[ii]=;

                    tmp=arr[ii];

                }

            if(judge()){

                flag=;

                break;

            }

            else {

                int p=n;

                while(!book[p])

                    p--;

                book[p]=;

                if(judge()){

                    flag=;

                    break;

                }

            }

        }

        if(flag){

            for(int i=;i<=n;i++)

                if(book[i])

                    printf("%d ",arr[i]);

            printf("\n");

            for(int i=;i<=n;i++)

                if(!book[i])

                    printf("%d ",arr[i]);

        }

        else printf("No solution");

    }

    return ;

}

By xxmlala

巴特西

Two progressions(CodeForces-125D)【鸽巢原理】

最新文章

热门文章