北市賽剩下不到兩週就要比賽了
我決定從今天開始每天都要解一年的北市賽考古題
因為 $2019$ 的我已經做過了 所以今天來解 $2018$ 的
2018 北市賽
第一題、森林大火
第一題我就不太會解了 有點太實作
所以這題是我最後才解的
想法
先做一次 $O(mn)$ 去找到每一個連通塊
找到連通塊最多延燒的 將其封鎖
之後再延燒其他連通塊
不斷進行同樣的動作 整體複雜度應該還是 $O(mn)$ 只是常數很大
自己的解通過了全部的範測 所以還是放上來看看
1 |
|
第二題、勇者冒險（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
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
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
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
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$ 年的北市賽 在自己打的感覺看來 難度不算太高
很難說今年會不會提昇難度 不過能拿到的裸題就要盡量拿分
不會解的就再去問其他電神或慢慢想吧！