TIOJ 2155 & TIOJ 2151

今天Codeforces燒機

所以只能上TIOJ解解題目 (´;ω;`)

然後就發現建中的校內賽有夠難的

果然是全台第一志願

TIOJ 2155 - 對發票 Again！

看到這題時 發現就是要找所有字串的共同子字串且這個子字串在每個字串中不重複

突然想到不久前才學過的 Suffix Array 可以做到這件事情

所以就開始刻這題了

舉例

5
ramen
lamian
raaamen
yesiam
diamond 

我們先將這些字串串起來 然後找出這幾個的 LCP Array

最後將後綴編號 最後選取所有編號都出現一次的那個 找出LCP值

且與前後比對 就可以找到不重複的共同子字串

aaamen#yesiam#diamond$                            編號:3 ,與前一個的LCP: 0
aamen#yesiam#diamond$                             編號:3 ,與前一個的LCP: 2
==========================================================================
這段是我們所要選的答案 LCP大小為: 2 共同子字串為: "am"
am#diamond$                                       編號:4 ,與前一個的LCP: 1
amen#lamian#raaamen#yesiam#diamond$               編號:1 ,與前一個的LCP: 2
amen#yesiam#diamond$                              編號:3 ,與前一個的LCP: 5
amian#raaamen#yesiam#diamond$                     編號:2 ,與前一個的LCP: 2
amond$                                            編號:5 ,與前一個的LCP: 2
==========================================================================
an#raaamen#yesiam#diamond$                        編號:2 ,與前一個的LCP: 1
d$                                                編號:5 ,與前一個的LCP: 0
diamond$                                          編號:5 ,與前一個的LCP: 1
en#lamian#raaamen#yesiam#diamond$                 編號:1 ,與前一個的LCP: 0
en#yesiam#diamond$                                編號:3 ,與前一個的LCP: 3
esiam#diamond$                                    編號:4 ,與前一個的LCP: 1
iam#diamond$                                      編號:4 ,與前一個的LCP: 0
iamond$                                           編號:5 ,與前一個的LCP: 3
ian#raaamen#yesiam#diamond$                       編號:2 ,與前一個的LCP: 2
lamian#raaamen#yesiam#diamond$                    編號:2 ,與前一個的LCP: 0
==========================================================================
這段不是我們要選的答案 LCP大小為: 0  共同子字串為: ""
m#diamond$                                        編號:4 ,與前一個的LCP: 0
men#lamian#raaamen#yesiam#diamond$                編號:1 ,與前一個的LCP: 1
men#yesiam#diamond$                               編號:3 ,與前一個的LCP: 4
mian#raaamen#yesiam#diamond$                      編號:2 ,與前一個的LCP: 1
mond$                                             編號:5 ,與前一個的LCP: 1
==========================================================================
n#lamian#raaamen#yesiam#diamond$                  編號:1 ,與前一個的LCP: 0
n#raaamen#yesiam#diamond$                         編號:2 ,與前一個的LCP:2
n#yesiam#diamond$                                 編號:3 ,與前一個的LCP:2
nd$                                               編號:5 ,與前一個的LCP:1
ond$                                              編號:5 ,與前一個的LCP:0
raaamen#yesiam#diamond$                           編號:3 ,與前一個的LCP:0
ramen#lamian#raaamen#yesiam#diamond$              編號:1 ,與前一個的LCP:2
siam#diamond$                                     編號:4 ,與前一個的LCP:0
yesiam#diamond$                                   編號:4 ,與前一個的LCP:0

程式碼

#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int N = 4e5;

void count_sort(int pos[], int n, vector<int> &rank){
	int cnt[n] = {};
	for(int i = 0;i < n;i++) cnt[rank[pos[i]]]++;
	for(int i = 1;i < n;i++) cnt[i] += cnt[i-1];
	int ans[n];
	for(int i = n-1;~i;i--){
		ans[cnt[rank[pos[i]]]-1] = pos[i];
		--cnt[rank[pos[i]]];
	}
	for(int i = 0;i < n;i++) pos[i] = ans[i];
}
// 只需要在求完Suffix Array之後順便求LCP就好了
void get_suffix(string &s, int pos[], vector<int> &lcp){
	s += '$';
	int n = s.size();
	vector<int> rank(n);
	//k = 0
	iota(pos,pos+n,0);
	sort(pos,pos+n,[&](int a, int b){ return s[a] < s[b]; });
	for(int i = 0;i < n;i++){
		if(i==0){ 
			rank[pos[i]] = 0;
		}else{
			rank[pos[i]] = rank[pos[i-1]] + (s[pos[i]]!=s[pos[i-1]]);
		}
	}
	//k > 0
	vector<int> new_rank(n);
	for(int k = 0;(1<<k) < n;k++){
		for(int i = 0;i < n;i++)
			pos[i] = (pos[i] - (1<<k)%n + n ) % n;
		count_sort(pos,n,rank);
		new_rank[pos[0]] = 0;
		for(int i = 1;i < n;i++){
			pair<int,int> prev = {rank[pos[i-1]], rank[(pos[i-1]+(1<<k))%n]};
			pair<int,int> now = {rank[pos[i]], rank[(pos[i]+(1<<k))%n]};
			new_rank[pos[i]] = new_rank[pos[i-1]] + (prev!=now);
		}
		rank = new_rank;
	}
	//求LCP Array
	int k = 0;
	for(int i = 0;i < n;i++){
		int pi = rank[i];
		int j = pos[pi-1];
		while(i+k<n && j+k<n && s[i+k]==s[j+k]) k++;
		lcp[pi] = k;
		k = max(0,k-1);
	}
}


int pos[N];
int cnt[N]; // to maintain the values so that they don't repeat

signed main(){
	fastio
	int n;
	cin >> n;
	if(n==1){
		string s;
		cin >> s;
		cout << s << "\n";
		return 0;
	}
	string s = "";
	int len = 0;
	for(int i = 0;i < n;i++){
		string tmp;
		cin >> tmp;
		s += tmp + "#"[i==n-1];
		for(int j = 0;j < tmp.size()+(i!=0);j++){
			pos[len++] = i+1;
		}
	}
	int ans[s.size()+1];
	vector<int> lcp(s.size()+1);
	get_suffix(s,ans,lcp);

	//find the minimum lcp in an interval where no pos repeated
	queue<int> v;
	for(int i = n+1;i < s.size();i++){
		while(!v.empty()&&(cnt[pos[ans[i]]]||lcp[i]==0)){
			cnt[v.front()]--;
			v.pop();
		}
		v.push(pos[ans[i]]);
		cnt[pos[ans[i]]]++;
		if(v.size()==n){
			int minlen = 1e9;
			for(int j = i-n+2;j <= i;j++){
				minlen = min(lcp[j],minlen);
			}
			if(!(minlen==0||lcp[i-n+1]>=minlen||(i!=s.size()&&lcp[i+1]>=minlen))){
				if(ans[i]+minlen<s.size()){
					cout << s.substr(ans[i],minlen) << "\n";
					return 0;
				}
			}
		}
		
	}

	cout << "7122" << "\n";
	
}

不過這題最後我砸了很多次

發現錯在Counting sort的時候使用vector會太慢

所以把Counting sort改成用陣列就可以過了

TIOJ 2151 - 大富翁

這題很明顯就是裸矩陣快速冪

所以刻出來就過了

程式碼

#include <bits/stdc++.h>

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

int n;
int INF = 1e18;

struct matrix{
	vector<vector<int>> d;
	matrix(){d.resize(n,vector<int>(n));}
	matrix operator *(matrix b){
		matrix res;
		for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++){
				res.d[i][j] = -INF;
				for(int k = 0;k < n;k++){
					res.d[i][j] = max(res.d[i][j],d[i][k]+b.d[k][j]);
				}
			}
		}
		return res;
	}
};
int m,s,t;
matrix fastpow(matrix a, int p){
	matrix res;
	for(int i = 0;i < n;i++){
		for(int j = 0;j < n;j++) if(i!=j) res.d[i][j] = -INF;
	}
	while(p){
		if(p&1) res = res * a;
		a = a * a;
		p>>=1;
	}
	return res;
}

signed main(){
	fastio
	cin >> n >> m >> s >> t;
	s--;
	int arr[n];
	matrix mat;
	for(int i = 0;i < n;i++){
			for(int j = 0;j < n;j++) mat.d[i][j] = -INF;
	}
	for(int i = 0;i < n;i++) cin >> arr[i];
	for(int i = 0;i < m;i++){
		int u,v;
		cin >> u >> v;
		u--,v--;
		mat.d[u][v] = arr[v];
	}
		
	mat = fastpow(mat,t);
	int ans = -INF;
	for(int i = 0;i < n;i++){
		ans = max(ans,mat.d[s][i]);
	}
	cout << ans << "\n";
}