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 :
感觉这次比赛有点简单?如果当时参赛了应该能加五六十分吧
本来一小时切完前四题,感觉有机会切一次
看了下题,二分图,告辞
以前稍微学过一点点,但没刷题(当时退役了,去机房溜达了几次,然后旁听了一会二分图)
现在早就忘了
下次校队作业补题就选二分图吧,应该有这个专题