D. Guess Your Way Out! II

Problem's Link:

Mean:

一棵满二叉树，树中某个叶子节点是出口，目的是寻找这个出口。再给定Q个询问的结果，每个结果告诉我们在第i层中(l,r)覆盖的叶结点是否包含出口。

analyse:

基本思路：多个区间求交集。

具体实现：

对于每一个询问，把它转化到最底层。并且把不在(l,r)区间的询问改为在(最左边，l-1)和(r+1,最右边)的形式，这样一来全部都变成了在(l,r)区间的描述。

区间统计：

对左右区间起点和终点组成的集合进行排序。然后找到答案存在的区间，如果区间长度=1，答案唯一；长度>1，答案不唯一;长度=0，无解。

Trick:会爆int。

Time complexity: O(n)

Source code:

/** this code is made by crazyacking* Verdict: Accepted* Submission Date: 2015-07-16-11.55* Time: 0MS* Memory: 137KB*/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #define LL long long#define ULL unsigned long longusing namespace std;LL L[51], R[51];int main(){ ios_base::sync_with_stdio( false ); cin.tie( 0 ); L[1] = 1, R[1] = 1; for( int i = 2; i <= 50; ++i ) L[i] = L[i - 1] << 1, R[i] = ( L[i] << 1 ) - 1; int h, q; cin >> h >> q; if( q == 0 ) { if( h == 1 ) puts( "1" ); else puts( "Data not sufficient!" ); return 0; } map
                  
                    mp; for( int i = 0; i < q; ++i ) { LL level, left, right, type, gap; cin >> level >> left >> right >> type; gap = h - level; while( gap ) { gap--; left <<= 1; right = ( ( right + 1 ) << 1 ) - 1; } if( type ) { mp[left]++; mp[right + 1]--; } else { mp[L[h]]++; mp[left]--; mp[right + 1]++; mp[R[h] + 1]--; } } LL ans, sum = 0, ans_gap = 0, mid_pre = -1; map
                   
                    :: iterator it = mp.begin(); for( ; it != mp.end(); ++it ) { sum += ( it->second ); if( mid_pre != -1 ) { ans_gap += ( it->first ) - mid_pre; ans = mid_pre; } if( sum == q ) mid_pre = ( it->first ); else mid_pre = -1; } if( ans_gap == 1 ) cout << ans << endl; else if( ans_gap > 1 ) puts( "Data not sufficient!\n" ); else puts( "Game cheated!\n" ); return 0;}/**/

转载于:https://www.cnblogs.com/crazyacking/p/4652310.html

你可能感兴趣的文章