51nod 1484 猜数游戏 - dblank

51nod 1484 猜数游戏

现在有一款小游戏叫做“猜数游戏”。这个游戏的目的是从一个迷宫中找到一个出口。这个迷宫的形状是一棵高度为h的完全二叉树。玩家刚开始站在根部,出口是在某一个叶子结点上面。
现在我们来定义每一个结点的编号:
· 根部是1
· 某个内部结点的编号为 i (i ≤ 2h−1−1) 时,他的左儿子编号为2i,右儿子编号为2i+1。
根的深度定为1,其它结点的深度是他的父亲的深度+1。深度为h的结点是叶子。出口在某个叶子结点上,但是游戏玩家并不知道在哪个叶子,所以他现在要开始猜。
玩家每次会问ancestor(exit, i)属于[L,R]吗?这儿 ancestor(v, i) 表示结点v在第i层的那个祖先。然后游戏会给出"Yes"或"No"的回答。这个游戏的回答也不一定是完全合法的。有一些时候他会骗玩家。
现在有一些询问和回答,要求你从中判断一下,这个游戏有没有在说谎。如果游戏没有说谎,并且出口被推断出来,那么请输出出口,如果游戏没有说谎,但是出口不能被唯一判定出来,请输出“Data not sufficient!”。否则输出“Game cheated!”
结点u是结点v的祖先,当且仅当满足以下条件之一:
· u和v一样,
· u 是 v的父亲,
· u 是v的父亲的祖先。

样例解释:在这个例子中有 8个叶子结点。经过第一个询问之后,出口被确定在 [10, 14]区间内。经过第二个和第三个询问,只有14号符合条件。请结合图例进行理解。

Input
单组测试数据。
第一行有两个整数h, q (1 ≤ h ≤ 50, 1 ≤ q ≤ 10^5),表示树的高度和询问的数量。
接下来q行,每行包含 i, L, R, ans (1 ≤ i ≤ h, 2^(i - 1) ≤ L ≤ R ≤ 2^i - 1, ans∈{0,1}),表示询问出口在第i层的祖先属于L,R吗?ans=1表示YES,否则表示NO。
Output
如果游戏给出的信息是自相矛盾的,那么输出 Game cheated!。
如果可以唯一确定出口。那么输出出口的编号。
否则输出Data not sufficient!。
Input示例
4 3
4 10 14 1
3 6 6 0
2 3 3 1
Output示例
14

思路:我们可以直接把给出的区间全部投影到叶子节点区间,如果给出ans=1的区间,那答案就在这个区间里面,给出ans=0的区间,那么答案就在剩余区间里面,我们可以更新答案在的区间,那么答案一定被覆盖n次,我们统计有多少点被覆盖n次就好了。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#pragma comment(linker, "/STACK:102400000,102400000")
#define endl '\n'
#define debug puts("yes")
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 100000+ 10, Mod = 1000000007;
struct Quastion
{
    ll i, l, r, ans;
} q[N];
int h, n;
vector<pair<ll, ll> > v;
int main()
{
    scanf("%d%d", &h, &n);
    ll f = 1LL<<(h-1), e = (1LL<<(h)) - 1;
    map<ll, int> mp;
    for(int i = 1; i<=n; i++)
    {
        scanf("%I64d%I64d%I64d%I64d", &q[i].i, &q[i].l, &q[i].r, &q[i].ans);
        while(q[i].i < h)
        {
            q[i].l *= 2;
            q[i].r = q[i].r*2+1;
            q[i].i ++;
        }
        if(q[i].ans)
        {
            mp[q[i].l]++;
            mp[q[i].r+1]--;
        }
        else
        {
            mp[f]++;
            mp[q[i].l]--;
            mp[q[i].r+1]++;
            mp[e+1]--;
        }
    }
    map<ll, int>::iterator it;
    ll pre = -1, cnt = 0, ans = 0, sum;
    for (it = mp.begin(); it!=mp.end(); it++)
    {
        sum += it->second;
        if (pre != -1)
        {
            cnt += it->first - pre;
            ans = pre;
        }
        if (sum == n)pre = it->first;
        else pre = -1;
    }
    if(cnt == 1)
        printf("%I64d\n", ans);
    else if(cnt > 1)
        puts("Data not sufficient!");
    else puts("Game cheated!");
    return 0;
}

发表新评论