[TIOJ] 1839. [IOI 2013] 洞穴 Cave

題目連結:http://tioj.infor.org/problems/1839
經典的二分搜題,對於每個門都二分搜一次他的開關是哪一個,記錄下來並使他保持開著的狀況,如此便可以往下繼續走下去,一次檢驗出一個門,所以複雜度是$O(n^2 log n)$,不過該怎麼二分搜呢?不妨每次都反轉一串開關(已知道的就不要轉),看結果有沒有變成跟上一次不一樣(這裡的不一樣指的是說有沒有動到你要問的那個人),也就是說如果按下去發現原本只能通到i,但現在可以走到i+1之類的,那你剛剛必定按到i了,反之如果現在可以到達i+1你按完之後只能到i那,也是有按到的,所以依此性質就可以二分搜每個門對應到的開關是誰,同時也知道如何開關才好。
p.s沒看到多筆測資害我被梗了一下下ww
#include "lib1839.h"
#define N 5000

int MAP[N+5], OPENED[N+5];
inline void SWAP(int,int);

int main(){
	while(1){
		int n=Initialize();
		for(int i=0;i<n;++i) MAP[i]=-1;
		for(int i=0;i<n;++i){
			int sks = tryCombination(OPENED);if(sks==-1)sks=n;
			bool preSAME = (sks==i);
			int l=0, r=n;bool ff=(sks>i);
			while(r-l>1){
				int mid=(l+r)/2;
				SWAP(l,mid);
				int kawaii=tryCombination(OPENED);if(kawaii==-1)kawaii=n;
				bool curSAME = (kawaii==i);
				if(curSAME==preSAME) l=mid;
				else r=mid;
				ff=(kawaii>i);
				preSAME=curSAME;
			}
			MAP[l]=i;
			if(!ff) OPENED[l]=(OPENED[l]+1)&1;
		}
		answer(OPENED,MAP);
	}
	return 0;
}

inline void SWAP(int l,int r){
	for(int i=l;i<r;++i) if(MAP[i]==-1) OPENED[i]=(OPENED[i]+1)&1;
}

留言

這個網誌中的熱門文章

[TIOJ] 1902. 「殿仁.王,不認識,誰啊?」,然後他就死了……

[AtCoder] [經典競程 90 題] 024 - Select +/- One(★2)

[AtCoder] [經典競程 90 題] 022 - Cubic Cake(★2)