设为首页 加入收藏

TOP

codeforces 558D Guess Your Way Out! II 规律
2015-11-21 00:57:14 来源: 作者: 【大 中 小】 浏览:2次
Tags：codeforces 558D Guess Your Way Out 规律

?

题意：

给出n和q

?

表示有一棵深度为n的完全二叉树，叶子节点中有恰好一个点是出口 主角从根往下走，但不知道出口在哪里，但主角会获得q个提示。 ?? \像这样标号

q个提示 格式： deep [l, r] ok

?

?

表示 深度为deep 时， 出口（可能在） （一定不在）[l,r]区间
ok=1表示 是可能在 ok=0一定不在 目标：

?

?

若根据提示能找到出口则输出叶子节点下标，有多个可能的出口则输出data not sufficient，若给出的提示互相矛盾输出 Game cheatde
思路：

?

首先把所有提示的区间都映射到叶子节点上

先把一定不在的问题转成2个一定存在的提示。

那么显然每个提示里都包含了出口，所以我们查询一下哪个点是被q个区间覆盖了，则这个点就是出口。

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include
        #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; template 
               
                 inline bool rd(T &ret) { char c; int sgn; if (c = getchar(), c == EOF) return 0; while (c != '-' && (c<'0' || c>'9')) c = getchar(); sgn = (c == '-') ? -1 : 1; ret = (c == '-') ? 0 : (c - '0'); while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0'); ret *= sgn; return 1; } template 
                
                  inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if (x>9) pt(x / 10); putchar(x % 10 + '0'); } typedef long long ll; typedef pair
                 
                   pii; const int N = 500005; const int inf = 1e9 + 10; int n, q; ll L[55], R[55]; map
                  
                   mp; int main() { L[1] = R[1] = 1; for (int i = 2; i <= 50; i++)L[i] = L[i - 1] << 1, R[i] = R[i - 1] << 1 | 1; rd(n); rd(q); if (q == 0) { if (n == 1)puts(1); else puts(Data not sufficient!); return 0; } for (int i = 0, dep, ok; i < q; i++) { ll l, r; rd(dep); rd(l); rd(r); rd(ok); while (dep < n) { l <<= 1; r = r << 1 | 1; dep++; } if (ok)mp[l]++, mp[r + 1]--; else { mp[L[n]]++; mp[l]--; mp[r + 1]++; mp[R[n]+1]--; } } int sum = 0; ll pre = -1, cnt = 0, ans = 0; for (auto i : mp) { sum += i.second; if (pre != -1) { cnt += i.first - pre; ans = pre; } if (sum == q)pre = i.first; else pre = -1; } if (cnt == 0)puts(Game cheated!); else if (cnt > 1)puts(Data not sufficient!); else pt(ans); return 0; }


?

?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：自己写的c++双向链表 下一篇：CF 558A(Lala Land and Apple Tre..

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: