山姆的競程日記

從綠牌開始的旅途

0%

北市賽倒數10天

發表於 更新於 Disqus：

居然距離北市賽已經剩下不到10天了 時間真的過得很快

為了北市賽做準備真的比段考還要緊張很多

目前已經做了 5 年的考古題了

北市賽每年都大概會考一題 dfs, bfs

然後每年都會有裸題 1 ~ 2 題不等

有的題目可以暴搜來得到答案

這些分數都是我覺得一定要拿到的分數

據說北市賽只要拿到 350 ~ 400 分左右就有機會一、二等獎了

我一定要盡全力喇分

2015 北市賽

2015 年的題目比較難的大概就是第四題和第五題了

第五題其實沒很難 只是不好想到要使用 Floyd-Warshall

而第四題我現在還沒想到 據說要用 KMP 的樣子

第一題、質數加法分解（Prime）

我們可以藉由哥德巴赫定理

任一大於5的奇數都可寫成三個質數之和

得知 所有的質數（除了 2,3 都有機會化成其他質數的和）

我們可以先利用質數篩 在 O(nlogn) 的時間內找到所有質數

當輸入一個數字時 我們判斷他是否是質數 之後再用遞迴找到解

程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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;

const int N = 1e6+5;
bitset<N> isPrime;
vector<int> primes;

void init(){
	isPrime.flip();
	for(int i = 2;i <= N;i++){
		if(!isPrime[i]) continue;
		primes.push_back(i);
		for(int j = i*i;j <= N;j += i){
			isPrime[j] = false;
		}
	}
}
bool done;
vector<int> ans;
void solve(int n){
	if(done) return;
	if(n==0){
		done = true;
		return;
	}
	if(n==1) return; 
	if(n==2||n==3){
		if(!ans.empty()&&n==ans.back()) return;
		ans.push_back(n);
		done = true;
		return;
	}
	auto itr = lower_bound(primes.begin(),primes.end(),n);
	int idx = (*itr==n ? itr-primes.begin()-1 : itr-primes.begin());
	for(int i = idx;~i;i--){
		if(n < primes[i]) continue;
		if(!ans.empty()&&primes[i]==ans.back()) continue;
		ans.push_back(primes[i]);
		solve(n-primes[i]);
		if(done) return;
		ans.pop_back();
	}
}

void solve(){
	ans.clear();
	int n;
	cin >> n;
	if(!isPrime[n]){
		cout << 0 << "\n";
		return;
	}
	done = false;
	solve(n);
	if(!done){
		cout << n << "\n";
	}else{
		for(auto x : ans) cout << x << " ";
		cout << "\n";
	}
}

signed main(){
	fastio
	init();
	int t;
	cin >> t;
	while(t--) solve();
}

第二題、舞會（Party）

Uploading file..._0kkehpp4z

這題就是裸LCS 刻下去大概就過了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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;

signed main(){
	fastio
	int n,m;
	cin >> n >> m;
	int arr[n+1], arr2[m+1];
	for(int i = 1;i <= n;i++) cin >> arr[i], arr[i] ^= 1;
	for(int j = 1;j <= m;j++) cin >> arr2[j];
	int dp[n+1][m+1] = {};
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
			if(arr[i]==arr2[j]){
				dp[i][j] = dp[i-1][j-1] + 1;
			}else{
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
			}
		}
	}
	cout << dp[n][m] << "\n";
}

第三題、大黑馬（Underdog）

這題看到題目就是那種很長會不想讀的題目

但其實很簡單

找出數字比較大的一隊如果有機會超越其他隊 那麼就輸出那隊的編號

照著做就可以 AC 了

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;


signed main(){
	fastio
	int k,n;
	cin >> k >> n;
	int P[n][2*k+1], U[n][2*k+1], L[n][2*k+1];
	for(int i = 0;i < n;i++){
		int s;
		cin >> s;
		for(int j = 0;j < 2*k+1;j++){
			cin >> P[i][j];
		}
		for(int j = 0;j < 2*k+1;j++){
			cin >> U[i][j];
		}
		for(int j = 0;j < 2*k+1;j++){
			cin >> L[i][j];
		}
	}
	for(int i = n-1;~i;i--){
		for(int j = 0;j < n;j++){
			if(i==j) continue;
			for(int a = 0;a < k+1;a++){
				if(P[i][a] <= P[j][a+k]){
					goto stop;
				}
			}
		}
		cout << i+1 << " ";
		break;
		stop:;
	}
	for(int i = n-1;~i;i--){
		for(int j = 0;j < n;j++){
			if(i==j) continue;
			for(int a = 0;a < k+1;a++){
				if(U[i][a] <= L[j][a+k]){
					goto stop2;
				}
			}
		}
		cout << i+1 << " ";
		break;
		stop2:;
	}
}

第四題、猜謎遊戲

這題我想了好久都不會 上 Code Community 問這題

結果雞塊和 Wiwi 都一下子就想到結論(((ﾟДﾟ;)))

不過我還不會 先放個 Wiwi 的題解

（10/27 補）

去學了 KMP 演算法 看得懂Wiwi的解了 不過如果是我自己想一定想不到 QQ

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>

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

using namespace std;

int f[105];
int dp[1005][105];

void build_failure(string s){
	int p = 0;
	for(int i = 2;i <= s.size();i++){
		while(p == s.size() || (p&&s[p+1]!=s[i]))
			p = f[p];
		if(s[p+1]==s[i]) p++;
		f[i] = p;
	}
}

signed main(){
	fastio
	string a,b;
	cin >> a >> b;
	int n = a.size(), m = b.size();
	a = ' ' + a, b = ' ' + b;
	memset(dp,0x3f3f3f,sizeof dp);
	dp[0][0] = 0;
	build_failure(a);
	for(int i = 0;i < m;i++){
		for(int j = 0;j < n;j++){
			dp[i+1][j] = min(dp[i+1][j],dp[i][j]+1);
			int p = j;
			while(p && a[p+1]!=b[i+1])
				p = f[p];
			if(a[p+1]==b[i+1]) p++;
			dp[i+1][p] = min(dp[i+1][p],dp[i][j]);
		}
	}
	cout << *min_element(dp[m],dp[m]+n) << "\n";
}

第五題、搶救雷恩大兵（Saving Ryan）

這題是這幾年的北市賽中做到最有趣的一題

他多次詢問最短路徑

我們會想到 All Pairs Shortest Path 的演算法

最主要就兩個 Floyd-Warshall 和 Johnson’s

但是 Floyd 比較好寫 所以就寫Floyd-Warshall吧

要詢問時 我們可以枚舉我們要炸掉的點 就可以得到答案了

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#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;

inline int P(int x, int y){
	return x*n + y;
}
signed main(){
	fastio
	cin >> n;
	int arr[n][n];
	for(int i = 0;i < n;i++) for(int j = 0;j < n;j++){
		cin >> arr[i][j];
	}
	int dis[n*n][n*n];
	fill(&dis[0][0],&dis[n*n-1][n*n-1],1e9);
	for(int i = 0;i < n;i++) for(int j = 0;j < n;j++){
		dis[P(i,j)][P(i,j)] = 0;
		if(i!=n-1) dis[P(i,j)][P(i+1,j)] = arr[i+1][j];
		if(i!=0) dis[P(i,j)][P(i-1,j)] = arr[i-1][j];
		if(j!=0) dis[P(i,j)][P(i,j-1)] = arr[i][j-1];
		if(j!=n-1) dis[P(i,j)][P(i,j+1)] = arr[i][j+1];
	}

	for (int i = 0; i < n*n; i++){
            for (int j = 0; j < n*n; j++){
                for (int k = 0; k < n*n; k++){
                    if (dis[j][k] > dis[j][i] + dis[i][k]){
                        dis[j][k] = dis[j][i] + dis[i][k];
                    }
                }
            }
        }
	int q;
	cin >> q;
	while(q--){
		int a,b,c,d;
		cin >> a >> b >> c >> d;
		a--,b--,c--,d--;
		int ans = INT_MAX;
		for(int i = 0;i < n*n;i++){
			ans = min(arr[a][b]+dis[P(a,b)][i]+dis[i][P(c,d)]-arr[i/n][i%n],ans);
		}
		cout << ans << "\n";
	}
}