Kattis pebblesolitaire

題目

https://open.kattis.com/problems/pebblesolitaire

題目包含多筆測資，每筆測資有一個字串，字串當中只會有 - 和 o 兩種字元

對於一個字串，如果有連續出現 -oo 或是 oo- ，我們可以選擇要不要把第一個以及最後一個交換，然後把中間換成 -

也就是 -oo -> o-- ; oo- -> --o

請問經過多次這樣的操作之後，字串中最少可以只剩下多少 o

想法

我們每次操作都必定只會讓 o 的數量減少，但是要在甚麼時機選擇進行操作是不明確的

這時候可以考慮枚舉，注意到每次 o 減少的數量都是固定的，那麼我們就可以用 BFS 來枚舉了

每次檢查字串中每個出現 -oo 以及 o-- 的位置，只要操作後的字串過去沒有出現過就可以繼續枚舉

那麼要怎麼檢查字串有沒有用過?

可以用位元運算來解決，我們用一個 int 的每個 bit 來記錄字串中某個位置是不是 o

例如 --o 就紀錄成 001，用十進位表示就是 2

字串長度固定會是 $12$，那麼我們只需要 $2^{12} = 4096$ 就可以紀錄全部的情況了

Code

//By Koios1143
#include<iostream>
using namespace std;
int n, stat;
string s, str, tmp, que[5000];
bool vis[5000];

int str_to_stat(string s){
	// 把字串轉換成數字的狀態
	int res = 0;
	for(int i=0 ; i<s.size() ; i++){
		if(s[i] == 'o'){
			res |= (1<<i);
		}
	}
	return res;
}

int BFS(){
	que[0] = s;
	vis[str_to_stat(s)] = true;
	
	int i, j=1;
	for(i=0, j=1 ; i<j ; i++){
		str = que[i];
		for(int k=0 ; k<str.size()-2 ; k++){
			if((str[k] == 'o' && str[k+1] == 'o' && str[k+2] == '-') || (str[k] == '-' && str[k+1] == 'o' && str[k+2] == 'o')){
				tmp = str;
				swap(tmp[k], tmp[k+2]);
				tmp[k+1] = '-';
				stat = str_to_stat(tmp);
				if(!vis[stat]){
					vis[stat] = true;
					que[j] = tmp;
					j++;
				} 
			}
		}
	}
	return j-1;
}

int main(){
	cin>>n;
	while(n--){
		for(int i=0 ; i<5000 ; i++){
			vis[i] = false;
		}
		cin>>s;
		int last = BFS();
		int ans = 0;
		for(int i=0 ; i<que[last].size() ; i++){
			if(que[last][i] == 'o') ans++;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(1)$

BFS 時間複雜度為狀態數 $\times$ 操作數量，最多為 $4096 \times 10$

假設字串長度是 $s$，那麼 BFS 時間複雜度估計為 $O(10 \times 2^s)$

總時間複雜度為 $O(2^s \times n)$

Koios1143的筆記

Kattis - pebblesolitaire

Kattis pebblesolitaire

題目

想法

Code

時間複雜度分析