A. Playoff
思路
大胆猜测，小心验证
不难发现除第一轮外，每次比赛都是偶数情况
1
2
3
4
5
6
7
8
| #include<bits/stdc++.h>
void solve() {
int n;
std::cin >> n;
std::cout << (1 << n) - 1 << '\n';
}
int main() {
}
|
碎碎念
打开看题发现题面好长，慌了一下下
B. Prove Him Wrong
思路
简单的不等式计算
不妨考虑 ，要使得一次交换满足条件 ，只需要
要使得序列最长，那么序列应该是
判断边界 ，发现 时都有界
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include<bits/stdc++.h>
void solve() {
int n;
std::cin >> n;
if(n > 19) std::cout << "NO\n";
else {
std::cout << "YES\n";
int x = 1;
for(int i = 1; i <= n; i++) {
std::cout << x << ' ';
x = x * 3;
}
std::cout << '\n';
}
}
int main() {
}
|
碎碎念
边界一开始算成 了。。。 了一次
C. Fault-tolerant Network
思路
花费最小代价，让 的度变为
考虑特殊情况，即重边，其他的就遍历
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
| #include<bits/stdc++.h>
void solve() {
int n;
std::cin >> n;
std::vector<long long> a(n + 1),b(n + 1);
for(int i = 1; i <= n; i++) std::cin >> a[i];
for(int i = 1; i <= n; i++) std::cin >> b[i];
long long ans;
ans = std::min(std::abs(a[1] - b[1]) + std::abs(a[n] - b[n]),
std::abs(a[1] - b[n]) + std::abs(a[n] - b[1]));
long long a1,b1,an,bn;
a1 = b1 = std::abs(a[1] - b[1]); an = bn = std::abs(a[n] - b[n]);
for(int i = 1; i <= n; i++) {
a1 = std::min(a1,std::abs(a[1] - b[i]));
b1 = std::min(b1,std::abs(b[1] - a[i]));
an = std::min(an,std::abs(a[n] - b[i]));
bn = std::min(bn,std::abs(b[n] - a[i]));
}
ans = std::min(ans,std::min(std::abs(a[1] - b[1]) + an + bn,
std::abs(a[1] - b[n]) + an + b1));
ans = std::min(ans,std::min(std::abs(a[n] - b[1]) + a1 + bn,
std::abs(a[n] - b[n]) + a1 + b1));
ans = std::min(ans,a1 + an + b1 + bn);
std::cout << ans << '\n';
}
int main() {
}
|
碎碎念
重边的情况考虑漏了几次。。。
D. Nearest Excluded Points
思路
从外向内广度优先遍历一遍
先找到度 的点，这些点可以花费代价 实现
再往里面扩展
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
| #include<bits/stdc++.h>
struct Node {
std::pair<int,int> node,ans;
std::vector<int> To;
int vis;
};
void solve() {
int n;
std::cin >> n;
std::vector<Node> a(n + 1);
std::map<std::pair<int,int>,int> map;
for(int i = 1; i <= n; i++) {
std::cin >> a[i].node.first >> a[i].node.second;
map[a[i].node] = i;
}
int nxt[4][2] = {{0,-1},{0,1},{1,0},{-1,0}};
for(int i = 1; i <= n; i++) {
std::pair<int,int> u,v;
u = a[i].node;
for(int j = 0; j <= 3; j++) {
v.first = u.first + nxt[j][0];
v.second = u.second + nxt[j][1];
if(map[v] != 0)
a[i].To.push_back(map[v]);
}
}
std::queue<int> q;
for(int i = 1; i <= n; i++)
if(a[i].To.size() < 4) {
std::pair<int,int> u,v;
u = a[i].node;
a[i].vis = true;
for(int j = 0; j <= 3; j++) {
v.first = u.first + nxt[j][0];
v.second = u.second + nxt[j][1];
if(map[v] == 0) {
a[i].ans = v;
break;
}
}
q.push(i);
}
while(!q.empty()) {
int u = q.front();q.pop();
for(int v : a[u].To) {
if(a[v].vis == false) {
a[v].ans = a[u].ans;
a[v].vis = true;
q.push(v);
}
}
}
for(int i = 1; i <= n; i++)
std::cout << a[i].ans.first << ' ' << a[i].ans.second << '\n';
}
int main() {
}
|
碎碎念
怎么感觉这题不太像 的难度。。。
还是说最近几场的难度比较大？
E. Sum of Matchings
F. Tower Defense
总结 & 吐槽
Rating 变化： 参赛不计算
表现分：
Rank ：
感觉这次比赛有点简单？如果当时参赛了应该能加五六十分吧
本来一小时切完前四题，感觉有机会切一次
看了下题，二分图，告辞
以前稍微学过一点点，但没刷题（当时退役了，去机房溜达了几次，然后旁听了一会二分图）
现在早就忘了
下次校队作业补题就选二分图吧，应该有这个专题
