程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> codeforces 558D Guess Your Way Out! II 規律

codeforces 558D Guess Your Way Out! II 規律

編輯:C++入門知識

codeforces 558D Guess Your Way Out! II 規律


 

題意:

給出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];
mapmp;
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;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved