codeforces 497b// Tennis Game// Codeforces Round #283(Div. 1)

题意：网球有一方赢t球算一场，先赢s场的获胜。数列arr(长度为n)记录了每场的胜利者，问可能的t和s。

首先，合法的场景必须：

1两方赢的场数不一样多。

2赢多的一方最后一场必须赢。

3最后一场必须打满（即胜利者赢了t球）

首先要两个sum数组记录arr前i个元素中有多少个1，多少个2。先枚举t(从1-n)，当前位置从cur=1开始，要查cur到多少（记为pos1)，有t个1，到多少(pos2)，有t个2。这个在sum数组里用lower_bound查。让cur=（pos1,pos2中小的那个）继续循环。如果最后pos1,pos2都等于n+1,说明最后两者的数量都不足t个，是不合法的。

原本我用二分右端点+线段树查1和2数量的方法，这样比sum数组+lower_bound的方法多了一个log(一个是logn*logn，一个是logn)，结果第23个案例（n=100000)超时，我生成了一个十万的序列，结果用时3s,只比限制的2s多1s。可见这题连logn都要卡。换数组后变为200ms过。

乱码：

//#pragma comment(linker,"/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<vector>

#include<cmath>

#include<queue>

#include<stack>

#include<map>

#include<set>

#include<algorithm>

#include <stack>

#include <list>

using namespace std;

const int SZ=,INF=0x7FFFFFFF;

typedef long long lon;

const double EPS=1e-;

int psum[][SZ];

int main()

{

    //std::ios::sync_with_stdio(0);

    //freopen("d:\\1.txt","r",stdin);

    vector<pair<int,int>> res;

    int n;

    //cin>>n;

    scanf("%d",&n);

    vector<int> vct(n+);

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

    {

        //cin>>vct[i];

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

    }

    psum[][]=vct[]==;

    psum[][]=vct[]==;

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

    {

        psum[][i]=(vct[i]==)+(psum[][i-]);

        psum[][i]=(vct[i]==)+(psum[][i-]);

    }

    //for(int i=1;i<=n;++i)cout<<psum[2][i]<<endl;

    //cout<<qry(1,n,1,1,4)<<endl;

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

    {

        int cur=;

        bool fail=;

        int win1=,win2=,last=;

        for(;cur<=n;)

        {

            int lo=cur,hi=n+;

            int pos1,pos2;

            //for(;lo<hi;)

            //{

            //    int mid=(lo+hi)/2;

                pos1=lower_bound(psum[]+,psum[]+n+,psum[][cur-]+i)-(psum[]);

                pos2=lower_bound(psum[]+,psum[]+n+,psum[][cur-]+i)-(psum[]);

                //cout<<"m: "<<cur<<" "<<pos1<<" "<<pos2<<endl;

//                if(max(num1,num2)>=i)

//                {

//                    hi=mid;

//                }

//                else lo=mid+1;

            //}

            //num1=psum[1][lo]-psum[1][cur-1];

            //num2=(lo-cur+1-num1);

            if(pos1<pos2)++win1;

            else ++win2;

            last=(pos1<pos2?:);

            //if(i==2)cout<<"lo: "<<lo<<endl;

            if(pos1==pos2)

            {

                fail=;

                break;

            }

            cur=min(pos1,pos2)+;

        }

        if(win1==win2)fail=;

        if(win1>win2&&last!=)fail=;

        if(win2>win1&&last!=)fail=;

        //cout<<"i:"<<i<<" "<<win1<<" "<<win2<<endl;

        if(!fail)

        {

            res.push_back(make_pair(max(win1,win2),i));

        }

    }

//    int num1=count(vct.begin()+1,vct.end(),1);

//    int num2=count(vct.begin()+1,vct.end(),2);

//    if(num1!=num2)

//    {

//        int big=num1>num2?1:2;

//        if(big==vct[vct.size()-1])res.push_back(make_pair(max(num1,num2),1));

//    }

    sort(res.begin(),res.end());

    cout<<res.size()<<endl;

    for(int i=;i<res.size();++i)

    {

        printf("%d %d\n",res[i].first,res[i].second);

        //cout<<res[i].first<<" "<<res[i].second<<endl;

    }

    return ;

}

巴特西

codeforces 497b// Tennis Game// Codeforces Round #283(Div. 1)

最新文章

热门文章