居然距離北市賽已經剩下不到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
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）
這題就是裸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
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
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
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
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";
}
}