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

时间:2023-01-09 06:51:59

题意:网球有一方赢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 ;
}