Posted inzerojudge

zerojudge i629. 序列操作問題

2023 年 8 月 14 日No Comments

題目請參考https://zerojudge.tw/ShowProblem?problemid=i629.

這題要做得快, 要仔細分析題目的四個操作, 能解決操作最慢的那個, 才會AC. 哪個操作最花時間呢?操作1到3都要排序, 排序很快的方法有很多, 不會隨著資料的增加而大幅增加排序時間,所以問題不大.

操作4看起來最花時間,如果所有數字都去做XOR,測資又一直在做操作4就GG了.而且做了XOR的數字順序一定大亂,每做一次操作4,就全部要重新排序,實在太花時間,所以要解決的重點就是操作4.

我們先來研究一下XOR到底在做什麼. 題目說k≤109,所以k是非負整數(unsigned int),沒有處理正負號的問題, XOR就是對每個位元做位元運算. 而且我們知道不管k是多少,任何數字XOR k兩次,就跟沒有發生什麼事情一樣,所以先別急著重新排序,只要把k記錄起來就好. XOR還有一個特性, XOR k1再XOR k2, 會等於XOR (k1 XOR k2 ),所以不管XOR幾個數字k, 都先把那些數字k XOR起來就可以了,這樣就省了很多重新排序時間了.

再仔細看看XOR後的數字,真的需要重新排序嗎? 用一個位元(bit)來看,如果XOR 1, 那這bit會反相, 0變成1,1變成0. 如果是XOR 0,那這bit不變. 所以XOR k時,就可以把k拆成每個bit來看,看看哪些是要反相就可以知道他真正代表0或是1了. 然後在做操作1到3時, 就根據紀錄的k值來得到每個bit真正的值來加入,刪除或排序.

由於對每個k要一個bit一個bit來看,所以對每個數字k都拆成bit來排序,我用二元樹來儲存每個bit,這樣刪除和插入都快. 從main來看就像下面這樣.

TREE tree;

int main() {

	   int q;
	   scanf("%d",&q);
	   while (q--) {
			  int op, k;
			  scanf("%d %d",&op,&k);
			  int ret;
			  switch(op){
					case 1://插入一個數字 k 到序列中
						tree.Add(k);
						break;
					case 2://刪除序列中的一個數字 k
						ret=tree.Delete(k);
						if(ret==-1){
							printf("HEHE\n");
						}
						break;
					case 3://輸出第 k 小數字
						ret=tree.Find(k);
						if(ret==-1){
							printf("QQ\n");
						}else{
							printf("%d\n",ret);
						}
						break;
					case 4://把序列中所有數字 xor k
						tree.XOR(k);
						break;
			  }
	   }
}
C++

組成樹的節點node, 用來儲存每個bit, 因為bit有1和0兩種值,如果這個bit有1就在left加入一個node,有0就在right加入一個node. node看起來像下面這樣. 順便一提那個SUM是為了加快操作3速度,SUM代表這個節點有紀錄幾個數字. 所以看ROOT.SUM就可以知道要不要印出QQ.

class NODE {
	public:
		NODE *Left;
		NODE *Right;
		int SUM;//紀錄幾個數字

		NODE(){
			Left=Right=NULL;
			SUM=0;
			}

		void Add(unsigned int k, unsigned int bit, unsigned int xor_v);
		int Delete(unsigned int k, unsigned int bit, unsigned int xor_v);
		int Find(unsigned int k, unsigned int bit, unsigned int xor_v,
				unsigned int v);
};
C++

樹就用node來做操作1到3. 操作4的XOR值則在tree裡記錄在XOR_V,要操作時再傳給node就好.只有一行搞定,變得非常簡單. ROOT是根結點, 代表k最左邊的那個bit, 所以從0x80000000開始,下一層的參數只要右移一個bit.

class TREE {
	public:
		int XOR_V;
		NODE ROOT;//根節點

		TREE(){
			XOR_V=0;
		}

		void Add(unsigned int k){
			ROOT.Add(k,0x80000000,XOR_V);
		}
		int Delete(unsigned int k){
			return ROOT.Delete(k,0x80000000,XOR_V);
		}
		int Find(unsigned int k){
			if(ROOT.SUM<k){
				return -1;
			}
			return ROOT.Find(k,0x80000000,XOR_V,0);
		}
		void XOR(unsigned int k){  //操作4
			XOR_V = XOR_V ^ k;
		}

};
C++

先從node的Add講起好了, 判斷k & bit來知道要處理的這個bit是1還是0, 判斷xor_v & bit才知道要把這個bit正常對待還是反相處理. 正常處理就是1要加在左邊,0就加在右邊的結點. 反向處理就顛倒.所以寫好正常處理的部分再改反相處理部分就好.

void NODE::Add(unsigned int k, unsigned int bit, unsigned int xor_v){

	SUM++;

	if(!bit){
		return;
	}

	if(k & bit){
		if(xor_v & bit){//反相處理
			if(!Right){
				Right=new NODE();
			}
			Right->Add(k, bit>>1, xor_v);
		}else{//正常處理
			if(!Left){
				Left=new NODE();
			}
			Left->Add(k, bit>>1, xor_v);
		}
	}else{
		if(xor_v & bit){//反相處理
			if(!Left){
				Left=new NODE();
			}
			Left->Add(k, bit>>1, xor_v);
		}else{//正常處理
			if(!Right){
				Right=new NODE();
			}
			Right->Add(k, bit>>1, xor_v);
		}
	}
}
C++

刪除操作和Add差不多.但是有可能要刪除的數字不存在,只要任一個bit沒找到結點,就回傳-1代表這數字不存在. 如果每個bit都有找到結點就回傳0, 順便把SUM減一,代表刪了一個數字. 當SUM歸零時,把指標清成NULL,下次刪除才不會誤判有這個數字.

int NODE::Delete(unsigned int k, unsigned int bit, unsigned int xor_v){
	if(!bit)
		return 0;

	if(k & bit){
		if(xor_v & bit){//反相處理
			if(Right){
				int ret=Right->Delete(k, bit>>1, xor_v);
				if(ret==0){ //found
					SUM--;
					if(SUM==0){
						Right=NULL;
					}
				}
				return ret;
			}else{
				return -1;  //unfound
			}
		}else{//正常處理
			if(Left){
				int ret=Left->Delete(k, bit>>1, xor_v);
				if(ret==0){ //found
					SUM--;
					if(SUM==0){
						Left=NULL;
					}
				}
				return ret;
			}else{
				return -1;  //unfound
			}
		}
	}else{
		if(xor_v & bit){//反相處理
			if(Left){
				int ret=Left->Delete(k, bit>>1, xor_v);
				if(ret==0){ //found
					SUM--;
					if(SUM==0){
						Left=NULL;
					}
				}
				return ret;
			}else{
				return -1;  //unfound
			}
		}else{//正常處理
			if(Right){
				int ret=Right->Delete(k, bit>>1, xor_v);
				if(ret==0){ //found
					SUM--;
					if(SUM==0){
						Right=NULL;
					}
				}
				return ret;
			}else{
				return -1;  //unfound
			}
		}
	}
	return 0;
}
C++

操作3尋找第k個數字是用SUM來計算. 因為數字排序是由小到大,所以正常處理時先檢查是不是在右邊結點.如果右邊的SUM不夠多, 那k就把右邊的SUM減掉, 去左邊找一定會找到. v是紀錄找到的每個bit,32個bit都湊齊後,就是要找的數字.

int NODE::Find(unsigned int k, unsigned int bit, unsigned int xor_v,
		unsigned int v)
{
	if(bit==0)
		return v;

	if(xor_v & bit){//反相處理
		if(Left){
			if(Left->SUM>=k){
				return Left->Find(k,bit>>1,xor_v, v);
			}else{
				k-=Left->SUM;
			}
		}
		if(Right){
			return Right->Find(k,bit>>1,xor_v, v|bit);
		}
		return v;//兩邊都已找完,回傳v
	}else{ //正常處理
		if(Right){
			if(Right->SUM>=k){
				return Right->Find(k,bit>>1,xor_v, v);
			}else{
				k-=Right->SUM;
			}
		}
		if(Left){
			return Left->Find(k,bit>>1,xor_v, v|bit);
		}
		return v;//兩邊都已找完,回傳v
	}
	return -1;
}
C++

全部AC約花0.3秒. 下面附上完整程式.

#include <stdio.h>
#include <iostream>
using namespace std;

class NODE {
	public:
		NODE *Left;
		NODE *Right;
		int SUM;//紀錄幾個數字

		NODE(){
			Left=Right=NULL;
			SUM=0;
			}

		void Add(unsigned int k, unsigned int bit, unsigned int xor_v);
		int Delete(unsigned int k, unsigned int bit, unsigned int xor_v);
		int Find(unsigned int k, unsigned int bit, unsigned int xor_v,
				unsigned int v);
};

void NODE::Add(unsigned int k, unsigned int bit, unsigned int xor_v){

	SUM++;

	if(!bit){
		return;
	}

	if(k & bit){
		if(xor_v & bit){//反相處理
			if(!Right){
				Right=new NODE();
			}
			Right->Add(k, bit>>1, xor_v);
		}else{//正常處理
			if(!Left){
				Left=new NODE();
			}
			Left->Add(k, bit>>1, xor_v);
		}
	}else{
		if(xor_v & bit){//反相處理
			if(!Left){
				Left=new NODE();
			}
			Left->Add(k, bit>>1, xor_v);
		}else{//正常處理
			if(!Right){
				Right=new NODE();
			}
			Right->Add(k, bit>>1, xor_v);
		}
	}
}

int NODE::Delete(unsigned int k, unsigned int bit, unsigned int xor_v){
	if(!bit)
		return 0;

	if(k & bit){
		if(xor_v & bit){//反相處理
			if(Right){
				int ret=Right->Delete(k, bit>>1, xor_v);
				if(ret==0){ //found
					SUM--;
					if(SUM==0){
						Right=NULL;
					}
				}
				return ret;
			}else{
				return -1;  //unfound
			}
		}else{//正常處理
			if(Left){
				int ret=Left->Delete(k, bit>>1, xor_v);
				if(ret==0){ //found
					SUM--;
					if(SUM==0){
						Left=NULL;
					}
				}
				return ret;
			}else{
				return -1;  //unfound
			}
		}
	}else{
		if(xor_v & bit){//反相處理
			if(Left){
				int ret=Left->Delete(k, bit>>1, xor_v);
				if(ret==0){ //found
					SUM--;
					if(SUM==0){
						Left=NULL;
					}
				}
				return ret;
			}else{
				return -1;  //unfound
			}
		}else{//正常處理
			if(Right){
				int ret=Right->Delete(k, bit>>1, xor_v);
				if(ret==0){ //found
					SUM--;
					if(SUM==0){
						Right=NULL;
					}
				}
				return ret;
			}else{
				return -1;  //unfound
			}
		}
	}
	return 0;
}

int NODE::Find(unsigned int k, unsigned int bit, unsigned int xor_v,
		unsigned int v)
{
	if(bit==0)
		return v;

	if(xor_v & bit){//反相處理
		if(Left){
			if(Left->SUM>=k){
				return Left->Find(k,bit>>1,xor_v, v);
			}else{
				k-=Left->SUM;
			}
		}
		if(Right){
			return Right->Find(k,bit>>1,xor_v, v|bit);
		}
		return v;//兩邊都已找完,回傳v
	}else{ //正常處理
		if(Right){
			if(Right->SUM>=k){
				return Right->Find(k,bit>>1,xor_v, v);
			}else{
				k-=Right->SUM;
			}
		}
		if(Left){
			return Left->Find(k,bit>>1,xor_v, v|bit);
		}
		return v;//兩邊都已找完,回傳v
	}
	return -1;
}


class TREE {
	public:
		int XOR_V;
		NODE ROOT;//根節點

		TREE(){
			XOR_V=0;
		}

		void Add(unsigned int k){
			ROOT.Add(k,0x80000000,XOR_V);
		}
		int Delete(unsigned int k){
			return ROOT.Delete(k,0x80000000,XOR_V);
		}
		int Find(unsigned int k){
			if(ROOT.SUM<k){
				return -1;
			}
			return ROOT.Find(k,0x80000000,XOR_V,0);
		}
		void XOR(unsigned int k){ //操作4
			XOR_V = XOR_V ^ k;
		}

};

TREE tree;

int main() {

	   int q;
	   scanf("%d",&q);
	   while (q--) {
			  int op, k;
			  scanf("%d %d",&op,&k);
			  int ret;
			  switch(op){
					case 1://插入一個數字 k 到序列中
						tree.Add(k);
						break;
					case 2://刪除序列中的一個數字 k
						ret=tree.Delete(k);
						if(ret==-1){
							printf("HEHE\n");
						}
						break;
					case 3://輸出第 k 小數字
						ret=tree.Find(k);
						if(ret==-1){
							printf("QQ\n");
						}else{
							printf("%d\n",ret);
						}
						break;
					case 4://把序列中所有數字 xor k
						tree.XOR(k);
						break;
			  }
	   }
}
C++
Last updated on 2023 年 8 月 14 日

Comments

No comments yet. Why don’t you start the discussion?

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *