0%

北市賽倒數13天!

北市賽剩下不到兩週就要比賽了

我決定從今天開始每天都要解一年的北市賽考古題

因為 $2019$ 的我已經做過了 所以今天來解 $2018$ 的

2018 北市賽

第一題、森林大火

第一題我就不太會解了 有點太實作

所以這題是我最後才解的

想法

先做一次 $O(mn)$ 去找到每一個連通塊

找到連通塊最多延燒的 將其封鎖

之後再延燒其他連通塊

不斷進行同樣的動作 整體複雜度應該還是 $O(mn)$ 只是常數很大

自己的解通過了全部的範測 所以還是放上來看看

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#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 = 205;
int grid[N][N];
vector<vector<int>> vis, vis2;
vector<pair<int,pair<int,int>>> points;
vector<pair<int,int>> pt;
int n,m, sz, ans;

void dfs(int x, int y, bool s){
vis[x][y] = 1;
for(int i : {-1,0,1}){
for(int j : {-1,0,1}){
if(abs(i)==abs(j)) continue;
if(x+i < 0 || x+i >= n || y+j < 0 || y+j >= m) continue;
if(!vis[x+i][y+j]){
if(grid[x+i][y+j]){
dfs(x+i,y+j,false);
}else{
vis[x+i][y+j] = 1;
sz++;
}
}
}
}
if(s) points.push_back({sz,{x,y}}),sz = 0;
}

void dfs2(int x, int y){
vis2[x][y] = 1;
for(int i : {-1,0,1}){
for(int j : {-1,0,1}){
if(abs(i)==abs(j)) continue;
if(x+i < 0 || x+i >= n || y+j < 0 || y+j >= m) continue;
if(!vis2[x+i][y+j]){
if(grid[x+i][y+j]){
dfs2(x+i,y+j);
}else{
ans++;
}
}
}
}
}

void dfs3(int x, int y){
vis[x][y] = 1;
for(int i : {-1,0,1}){
for(int j : {-1,0,1}){
if(abs(i)==abs(j)) continue;
if(x+i < 0 || x+i >= n || y+j < 0 || y+j >= m) continue;
if(!vis[x+i][y+j]){
if(grid[x+i][y+j]){
dfs3(x+i,y+j);
}else{
pt.emplace_back(x+i,y+j);
}
}
}
}
}

signed main(){
fastio
cin >> n >> m;
vis.resize(n,vector<int>(m,0));
vis2.resize(n,vector<int>(m,0));
int num;
cin >> num;
while(num--){
int x,y;
cin >> x >> y;
grid[x][y] = 1;
}
while(true){
vis = vis2;
points.clear();
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(!vis[i][j]&&grid[i][j]) dfs(i,j,1);
}
}
if(points.size()==0) break;
pair<int,int> p = (*max_element(points.begin(),points.end())).second;
vis = vis2;
dfs2(p.first,p.second);
vis = vis2;
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
if(!vis[i][j]&&grid[i][j]) dfs3(i,j);
}
}
for(auto x : pt) grid[x.first][x.second] = 1;

}
cout << ans << "\n";
}

第二題、勇者冒險(Adventure)

給兩點

找到路徑上最大值最小的路徑最大值

$bfs$裸題

應該能直接拿$100$分

不負責任程式碼

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
#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 = 1005;
int grid[N][N];

signed main(){
fastio
memset(grid,-1,sizeof grid);
int n,m;
cin >> n >> m;
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
int num;
cin >> num;
for(int i = 0;i < num;i++){
int x,y,w;
cin >> x >> y >> w;
grid[x][y] = w;
}
grid[sx][sy] = 0;
grid[ex][ey] = 0;
int ans[n+1][m+1];
memset(ans,0x3f3f3f3f,sizeof ans);
queue<pair<int,int>> q;
q.emplace(sx,sy);
ans[sx][sy] = grid[sx][sy];
while(!q.empty()){
auto [x,y] = q.front(); q.pop();

for(int i : {-1,0,1}){
for(int j : {-1,0,1}){
if(abs(i)==abs(j)) continue;
if(x+i < 0 || x+i >= n || y+j < 0 || y+j >= m) continue;
if(~grid[x+i][y+j]){
if(ans[x+i][y+j] > max(ans[x][y],grid[x+i][y+j])){
ans[x+i][y+j] = max(ans[x][y],grid[x+i][y+j]);
q.emplace(x+i,y+j);
}
}
}
}
}
cout << ans[ex][ey] << "\n";
}

第三題、表演節目 (Show)

給予容量與價值的0/1背包問題(完全裸題)

在固定容量內能裝的最高價值為何

輸出最高價值與所需容量

應該也能直接拿$100$分

不負責任程式碼

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
#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 m,s;
cin >> m >> s;
int dp[s+1][m+1] = {};
for(int i = 1;i <= s;i++){
int val, cp;
cin >> val >> cp;
for(int j = 0;j <= m;j++){
if(cp+j <= m) dp[i][cp+j] = max(dp[i][cp+j],dp[i-1][j] + val);
if(i!=s) dp[i+1][j] = max(dp[i][j],dp[i+1][j]);
}
}
int ans = 0, num = 0;
for(int i = 0;i <= s;i++){
for(int j = 0;j <= m;j++){
if(ans < dp[i][j]) ans = dp[i][j], num = j;
}
}
cout << ans << " " << num << "\n";
}

第四題、幸運表格(Lucky)

簡單的 $dp$ 題 這題很像今年十月APCS 但是簡單很多

想法

列出轉移式
$dp[i][j] = max(grid[i][j],dp[i-1][j]+grid[i][j], dp[i][j-1]+grid[i][j])$

希望沒想錯 不過應該不會偏差太多

$100$分GET!

我的程式碼(兩個範測都$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
#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 dp[n][m] = {}, grid[n][m] = {};
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
cin >> grid[i][j];
}
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
dp[i][j] = max({(int)grid[i][j],max({(i!=0 ? dp[i-1][j] : 0), (j!=0 ? dp[i][j-1] : 0),(int)0})+grid[i][j]});
}
}
cout << *max_element(dp[n-1],dp[n-1]+m) << "\n";
}

第五題、保護女王(Queen)

幾何問題

想法

先照著題目做 將點依照 $x$ 座標排序並分成兩群

接下來分別找出兩群凸包上的點(第二子題的提示)

子題一、二

子題二提到兩群凸包上的點數量(先設其為$n’$)不超過 $3000$

我們可以對兩群凸包上的點去做 $O(n’^2)$ 找到線段

把斜率最大和最小的線段找出來 然後找出兩線段交點

$65$分GET!

不負責任程式碼

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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;

struct Point{
int x,y;
Point(int x, int y): x(x), y(y){}
bool operator < (Point b){
return x < b.x;
}
int operator ^ (Point b){
return x*b.y-y*b.x;
}
Point operator - (Point b){
return {x-b.x,y-b.y};
}
};

struct Line{
double m, c;
Line(Point a, Point b){
m = 1.0*(b.y-a.y)/(b.x-a.x);
c = a.y-m*a.x;
}
Line(double m1, double c1){
m = m1;
c = c1;
}
double findY(double x){
return m*x+c;
}
};

vector<Point> getHull(vector<Point> v){
int n = v.size();
vector<Point> hull;
for(int i = 0; i < 2;i++){
int t = hull.size();
for(auto x : v){
while(hull.size()-t >= 2&&((hull.back()-hull[hull.size()-2])^(x-hull[hull.size()-2]))<=0)
hull.pop_back();
hull.push_back(x);
}
hull.pop_back();
reverse(v.begin(),v.end());
}
return hull;
}
// y = m1x + b1
// y = m2x + b2
// => (m1-m2)x + (b1-b2) = 0
// => x = (b2-b1)/(m1-m2);
pair<double,double> intersect(Line a, Line b){
double x = (b.c-a.c)/(a.m-b.m);
double y = a.findY(x);
return {x,y};
}

signed main(){
fastio
cout << fixed << setprecision(10);
int n;
cin >> n;
vector<Point> v;
for(int i = 0;i < n;i++){
int x,y;
cin >> x >> y;
v.emplace_back(x,y);
}
sort(v.begin(),v.end());
vector<Point> v1, v2;
for(int i = 0;i < n;i++){
if(2*i < n) v1.push_back(v[i]);
else v2.push_back(v[i]);
}
v1 = getHull(v1);
v2 = getHull(v2);
Line ma(-1e9,0), mi(1e9,0);
for(int i = 0; i < v1.size();i++){
for(int j = 0;j < v2.size();j++){
Line tmp(v1[i],v2[j]);
if(tmp.m > ma.m) ma = tmp;
if(tmp.m < mi.m) mi = tmp;
}
}
pair<double,double> p = intersect(ma,mi);
cout << p.first << " " << p.second << "\n";
}

子題三

我還沒想到 應該能把 $O(n’^2)$ 做優化 來通過這個子題

心得

$2018,2019$ 年的北市賽 在自己打的感覺看來 難度不算太高

很難說今年會不會提昇難度 不過能拿到的裸題就要盡量拿分

不會解的就再去問其他電神或慢慢想吧!