程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> CodeForces 520D Cubes

CodeForces 520D Cubes

編輯：關於C++

題意：

二維平面內有一個圖形由n（10^5）個標有0~n-1的方塊組成保證它是穩定的即每個方塊要麼落在地面上要麼下面（邊或點相交）有至少一個方塊支撐現在兩個人輪流拆這個圖形要求拆的過程中圖形仍穩定拆下的方塊上的數字會形成一個n進制的數先手想讓這個數最大後手想最小問最後這個數字是幾

思路：

簡單的貪心思路在不毀壞穩定性的前提下先手拿大數字後手拿小數字程序寫的暴力會n^2造成TLE

那麼我們維護一個有序隊列（set維護）這裡面裝著可以拆的數字每次從裡面拿走想要的數字

注意的是進入set的數字在拆之前仍要檢查可行性！因為最開始可能是_-_這種形狀那麼這3個都進入set 假設拆掉了右邊即變成了_-這樣那麼這時左邊就不能拆了即使它在set裡

每次拆完一個數字檢查它下面的3個位置這三個位置也許具有拆掉的可能了

PS：

使用STL要小心點一邊遍歷一遍刪除元素是很危險的！！！

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
#define N 100010
#define mod 1000000009
#define mp(x,y) (make_pair(x,y))

int n;
int x[N],y[N];
map,int> f;
set g;
LL ans;

bool yes(int tmp){
	int X,Y;
	X=x[tmp]+1;
	Y=y[tmp]+1;
	if(f.count(mp(X,Y))){
		if(!f.count(mp(X,Y-1))&&!f.count(mp(X+1,Y-1))){
			return false;
		}
	}
	X=x[tmp];
	Y=y[tmp]+1;
	if(f.count(mp(X,Y))){
		if(!f.count(mp(X-1,Y-1))&&!f.count(mp(X+1,Y-1))){
			return false;
		}
	}
	X=x[tmp]-1;
	Y=y[tmp]+1;
	if(f.count(mp(X,Y))){
		if(!f.count(mp(X-1,Y-1))&&!f.count(mp(X,Y-1))){
			return false;
		}
	}
	return true;
}

void add(int tmp){
	int X,Y;
	X=x[tmp]-1;
	Y=y[tmp]-1;
	if(f.count(mp(X,Y))){
		int u=f[mp(X,Y)];
		if(yes(u)) g.insert(u);
	}
	X=x[tmp];
	Y=y[tmp]-1;
	if(f.count(mp(X,Y))){
		int u=f[mp(X,Y)];
		if(yes(u)) g.insert(u);
	}
	X=x[tmp]+1;
	Y=y[tmp]-1;
	if(f.count(mp(X,Y))){
		int u=f[mp(X,Y)];
		if(yes(u)) g.insert(u);
	}
}

int main(){
	scanf("%d",&n);
	for(int i=0;i