codeforces 497b// Tennis Game// Codeforces Round #283(Div. 1)-白红宇

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

阅读量：4682 次

发布时间：2019-06-09

本文共 1612 字，大约阅读时间需要 5 分钟。

题意：网球有一方赢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
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             #include
              
               #include
               
                #include 
                
                 #include 
                 
                  using namespace std;const int SZ=1000010,INF=0x7FFFFFFF;typedef long long lon;const double EPS=1e-9;int psum[3][SZ];int main(){ //std::ios::sync_with_stdio(0); //freopen("d:\\1.txt","r",stdin); vector
                  
                   
                    > res; int n; //cin>>n; scanf("%d",&n); vector
                    
                      vct(n+1); for(int i=1;i<=n;++i) { //cin>>vct[i]; scanf("%d",&vct[i]); } psum[1][1]=vct[1]==1; psum[2][1]=vct[1]==2; for(int i=2;i<=n;++i) { psum[1][i]=(vct[i]==1)+(psum[1][i-1]); psum[2][i]=(vct[i]==2)+(psum[2][i-1]); } //for(int i=1;i<=n;++i)cout<
                     
                      <
                      
                       =i)// {// hi=mid;// }// else lo=mid+1; //} //num1=psum[1][lo]-psum[1][cur-1]; //num2=(lo-cur+1-num1); if(pos1
                       
                        win2&&last!=1)fail=1; if(win2>win1&&last!=2)fail=1; //cout<<"i:"<
                        <<" "<
                         
                          <<" "<
                          
                           <
                           
                            num2?1:2;// if(big==vct[vct.size()-1])res.push_back(make_pair(max(num1,num2),1));// } sort(res.begin(),res.end()); cout<
                            
                             <

转载于:https://www.cnblogs.com/gaudar/p/9660692.html

你可能感兴趣的文章