Codeforces Round #312 (Div. 2) D. Guess Your Way Out! II 贪心排序

2024-05-14 11:58

本文主要是介绍Codeforces Round #312 (Div. 2) D. Guess Your Way Out! II 贪心排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

D. Guess Your Way Out! II
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Amr bought a new video game “Guess Your Way Out! II”. The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node.

Let’s index all the nodes of the tree such that

The root is number 1
Each internal node i (i ≤ 2h - 1 - 1) will have a left child with index = 2i and a right child with index = 2i + 1
The level of a node is defined as 1 for a root, or 1 + level of parent of the node otherwise. The vertices of the level h are called leaves. The exit to the maze is located at some leaf node n, the player doesn’t know where the exit is so he has to guess his way out!

In the new version of the game the player is allowed to ask questions on the format “Does the ancestor(exit, i) node number belong to the range [L, R]?”. Here ancestor(v, i) is the ancestor of a node v that located in the level i. The game will answer with “Yes” or “No” only. The game is designed such that it doesn’t always answer correctly, and sometimes it cheats to confuse the player!.

Amr asked a lot of questions and got confused by all these answers, so he asked you to help him. Given the questions and its answers, can you identify whether the game is telling contradictory information or not? If the information is not contradictory and the exit node can be determined uniquely, output its number. If the information is not contradictory, but the exit node isn’t defined uniquely, output that the number of questions is not sufficient. Otherwise output that the information is contradictory.

Input
The first line contains two integers h, q (1 ≤ h ≤ 50, 0 ≤ q ≤ 105), the height of the tree and the number of questions respectively.

The next q lines will contain four integers each i, L, R, ans (1 ≤ i ≤ h, 2i - 1 ≤ L ≤ R ≤ 2i - 1, ), representing a question as described in the statement with its answer (ans = 1 if the answer is “Yes” and ans = 0 if the answer is “No”).

Output
If the information provided by the game is contradictory output “Game cheated!” without the quotes.

Else if you can uniquely identify the exit to the maze output its index.

Otherwise output “Data not sufficient!” without the quotes.

Sample test(s)
input
3 1
3 4 6 0
output
7
input
4 3
4 10 14 1
3 6 6 0
2 3 3 1
output
14
input
4 2
3 4 6 1
4 12 15 1
output
Data not sufficient!
input
4 2
3 4 5 1
2 3 3 1
output
Game cheated!
Note
Node u is an ancestor of node v if and only if

u is the same node as v,
u is the parent of node v,
or u is an ancestor of the parent of node v.
In the first sample test there are 4 leaf nodes 4, 5, 6, 7. The first question says that the node isn’t in the range [4, 6] so the exit is node number 7.

In the second sample test there are 8 leaf nodes. After the first question the exit is in the range [10, 14]. After the second and the third questions only node number 14 is correct. Check the picture below to fully understand.
题意就是,给出h层的完全二叉树,从上到下从左到右标号1 - 2^n,要找出出口,出口在叶子结点处。再给q个区间,表示这个区间的子结点的叶子结点中有一个是出口,或都不是出口。
这里写图片描述
我们用区间s e表示其中可能是出口,那么如果给的区间是出口,只需要求交集就可以了。得到的结果仍然是一个区间。如果,给的区间,不是出口,那就是把这部分排除啦。这样就可以会出现多个集合了。如果,就这样不断扩展,有可能最张出现q^2个集区,复杂度就会达到n^2了,这样是不行的。考虑一种贪心方法,因为只有能去掉两端的结点,这样的区间才是有效的,如果是在中间,是对结果没有影响的,如图中,2 3 对0是有影响的,在没有2 3 的情况 1号线,是对结果没有影响的,所以我们只需要通过排序,使得 2 3这样的先遇上就可以,排序后,从前往后,再从后向前,就一定保证了 2 3这种在前面,而且,不会使得结果集扩大成多集一直是单集。总的复杂度就是排序复杂度o(q * log(q));

#define N 100050
#define M 100005
#define maxn 205
#define fi first
#define se second
#define MOD 1000000000000000007
int h,q,layer[N],flag[N],pn;
ll s,e,ss,ee,l[N],r[N];
pll p[N];
void get(int layer,ll l,ll r ){ss = l << (h - layer);ee = r;FI(h - layer) ee = ee * 2 + 1;
}
int main()
{while(S2(h,q)!=EOF){s = 1ll<<(h-1);e = (1ll<<h) - 1ll;bool isRight = true;pn = 0;FI(q){S(layer[i]);cin>>l[i];cin>>r[i];S(flag[i]);if(isRight){get(layer[i],l[i],r[i]);if(flag[i]){s = max(s,ss);e = min(e,ee);if(s > e) isRight = false;}else {p[pn++] = make_pair(ss,ee);}}}if(isRight){sort(p,p+pn);FI(pn){if(p[i].first <= s && p[i].second >= s)s = p[i].second + 1;}for(int i= pn-1;i>=0;i--){if(p[i].first <= e && p[i].second >=e)e = p[i].first - 1;}}if(s > e)printf("Game cheated!\n");else if(s == e) cout<<s<<endl;else printf("Data not sufficient!\n");}return 0;
}

这篇关于Codeforces Round #312 (Div. 2) D. Guess Your Way Out! II 贪心排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/988691

相关文章

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int