時間過得很快 馬上就要邁入十天倒數了
然而 我卻還是原地踏步 絲毫沒有一點點的進步
好想要有更多的時間練習競程 好希望接下來能在北市賽打到好成績
好希望能比全國賽 好希望能進明年TOI選訓營
有好多的目標 而北市賽只是這一切的開始 希望不要在第一個目標就失敗
2016 北市賽
這一年的題目 TIOJ 上面有（除了第三題） 所以就不會是自己去猜自己的解是不是對的了
然後大概也是做出 $300$ ~ $400$ 分 我真的很爛QQ
第一題、飛天桑妮（Sunny）
這題其實之前就解過了 但是還是再來解一次
先對每個點以 $x^2+y^2$ 去做排序
然後用前綴Max與後綴Min來找到最佳解
程式碼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
using namespace std;
struct Point{
int x,y,v;
Point(int x, int y, int v): x(x), y(y), v(v){}
bool operator < (Point b){
return (x*x+y*y==b.x*b.x+b.y*b.y ? v > b.v : x*x + y*y < b.x*b.x+b.y*b.y);
}
};
signed main(){
fastio
int n;
cin >> n;
vector<Point> v;
for(int i = 0;i < n;i++){
int x,y,w;
cin >> x >> y >> w;
v.emplace_back(x,y,w);
}
sort(v.begin(),v.end());
int ma[n], mi[n+1];
//ma prefix max
//mi prefix min
ma[0] = 0, mi[n] = 1e9;
for(int i = 1;i < n;i++){
ma[i] = max(ma[i-1],v[i-1].v);
}
int ans = 0;
for(int j = n-1;~j;j--){
mi[j] = min(mi[j+1],v[j].v);
ans = max(ans,ma[j]-mi[j]);
}
cout << ans << "\n";
}
第二題、地雷區 (Mine)
這題我們可以觀察出 在一個地雷的 $5 \times 5$ 範圍內
如果還有另一顆地雷 這兩個就屬於同一個連通塊
因此我們可以 dfs （並沒有 這題的 $row,col \leq 10000$）
使用 dfs 的話一定會 TLE
因此 我們可以拿出另外一個找連通塊數量的方法
也就是「並查集」啦（Disjoint Set Union）
每次輸入一個地雷時 去尋找 $5 \times 5$ 之內是否還有另一顆地雷 將這兩個 Unite
最後再用 $O(n)$ 時間就可以得到解答了
程式碼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
using namespace std;
const int N = 5e4+5;
map<pair<int,int>,int> m; //store the index of the point
int dsu[N];
int find(int u){
return u==dsu[u] ? u : dsu[u] = find(dsu[u]);
}
void unite(int u, int v){
u = find(u), v = find(v);
if(u==v) return;
dsu[u] = v;
}
signed main(){
fastio
iota(dsu,dsu+N,0);
int a,b,c;
cin >> a >> b >> c;
for(int i = 1;i <= c;i++){
int x,y;
cin >> x >> y;
for(int dx : {-2,-1,0,1,2}){
for(int dy : {-2,-1,0,1,2}){
if(dx==0&&dy==0) continue;
if(m[{x+dx,y+dy}]){
unite(m[{x+dx,y+dy}],i);
}
}
}
m[{x,y}] = i;
}
set<int> s;
for(int i = 1;i <= c;i++){
s.insert(find(i));
}
cout << s.size() << "\n";
}
第三題、導線短路（Short）
裸題 判斷線段是否相交
應該是能 $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 double EPS = 1e-7;
struct Point{
double x,y;
Point(double x, double y): x(x), y(y){}
double operator ^ (Point b){
return x*b.y-y*b.x;
}
Point operator - (Point b){
return {x-b.x,y-b.y};
}
double operator * (Point b){
return x*b.x+y*b.y;
}
};
bool collinear(Point a, Point b, Point c){
return fabs((a-c)^(b-c)) < EPS;
}
bool btw(Point a, Point b, Point c){
if(!collinear(a,b,c)) return 0;
else return (a-c)*(b-c) < EPS;
}
int ori(Point a, Point b, Point c){
double res = (b-a)^(c-a);
if(fabs(res) < EPS) return 0;
else return res > 0 ? 1 : -1;
}
struct Segment{
Point a,b;
Segment(Point a, Point b): a(a), b(b) {}
bool intersect(Segment s){
int abc = ori(a,b,s.a);
int abd = ori(a,b,s.b);
int cda = ori(s.a,s.b,a);
int cdb = ori(s.a,s.b,b);
if(abc==0&&abd==0) return btw(a,b,s.a) || btw(a,b,s.b) || btw(s.a,s.b,a) || btw(s.a,s.b,b);
else if(abc*abd < EPS && cda * cdb < EPS) return 1;
return 0;
}
};
signed main(){
fastio
int n;
cin >> n;
vector<Segment> v;
for(int i = 0;i < n;i++){
double a,b,c,d;
cin >> a >> b >> c >> d;
v.push_back(Segment({a,b},{c,d}));
}
for(int i = 0;i < n;i++){
for(int j = i+1;j < n;j++){
if(v[i].intersect(v[j])){
cout << 1 << "\n";
return 0;
}
}
}
cout << 0 << "\n";
}
第四題、小米雷射（Laser）
還在想
第五題、手續費（Fee）
這題算是用想的一下就知道每次合併兩個最小的一定會有最好的答案
這時我們就可以將數字放入min heap (priority_queue)
然後每次拿出最小的兩個數字 合併後再放回去
這題應該是2016最簡單的一題了吧
程式碼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
using namespace std;
signed main(){
fastio
priority_queue<int,vector<int>,greater<int>> pq;
int n;
cin >> n;
for(int i = 0, tmp;i < n;i++){
cin >> tmp;
pq.push(tmp);
}
int ans = 0;
while(pq.size() > 1){
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
pq.push(a+b);
ans += a+b;
}
cout << ans << "\n";
}