题目链接
题意：
给出n和q表示有一棵深度为n的完全二叉树
叶子节点中有恰好一个点是出口
主角从根往下走，但不知道出口在哪里，但主角会获得q个提示
q个提示 格式：deep[l,r]ok
意思为深度为deep时，出口 ok为1时：可能在 / ok为0时：一定不在 [l,r] 区间
目标：
若根据这q个提示能找到出口则输出叶子节点下标
有多个可能的出口则输出datanotsufficient
若给出的提示互相矛盾输出 Game cheatde
思路：
①首先把所有提示的区间都映射到叶子节点上（即深度为n的那一层）;
②先把一定不在的问题转成2个一定存在的提示，比方说最大深度为4，某次询问告诉你出口一定不在[10，13]，
那么出口就可能在[8,9]和[14,15];
③那么显然每个提示里都包含了出口，所以我们查询一下哪个点是被q个区间覆盖了，，则这个点就是出口。
代码如下：
#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include<map>using namespace std;typedef long long ll; ll L[55], R[55];int n, q, deep, ok;map<ll, int >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; //深度为i层的左右端点 }scanf("%d%d", &n, &q);if(q == 0){if (n == 1)puts("1");else puts("Data not sufficient!");return 0;}for(int i = 0; i < q; i++){ll l, r;scanf("%d%I64d%I64d%d", &deep, &l ,&r, &ok);while(deep < n){l <<= 1, r = r << 1|1;deep ++;}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; //cnt表示出口的个数，ans表示出口 for(map<ll, int>::iterator i = mp.begin(); i != mp.end(); i++){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 printf("%I64d\n", ans);return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
如果你不出去走走，你就会以为这就是世界。
