5 题铜尾。开题开的非常难受。的确，比赛也真的和状态有很大关系，有一些不确定性的存在。不过铜牌保卫战还是打赢了，最后 D 题贪心我用 3h 对拍调试过了这道题（+7 WA）。然后队友开 C 题也是一直 WA（+10），最后据本人说是开了 unsigned long long 才过的。下午 VP 从两点半达到六点半，另一个队友全程都在调 D 题，还是一直 WA（快破防了）。然后看了一眼当时比赛的榜，大概 rank 130 左右。
而且这把我还开错题了，一直感觉 L 题好像一个最小生成树的变体，只需要维护两种边权，然后维护最优解就好。但是一开始我用 Kruskal 做发现维护非常困难，然后又换成 prim 写，然后就过了 90 min，发现榜上一个队都没有过 M 题（最后 GYM 上也就 3 个队过，现场没有队伍过），然后才幡然醒悟。但是已经浪费了很多时间了。
（不过 ping 真的好强，如果按照正式比赛的 5h 来算，六点半离结束还有 1h，然后在吃完饭之后的 七点半他就把 M 那道计算几何过了%%%
A
签到，其实我完全可以更快得写出更好的代码的，但是毕竟 VP 的时候还是有点紧张，最后还是不能放开手脚，然后就打了这个可以过但是不是非常 pretty 的代码。
|
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 |
#include <bits/stdc++.h> void solve() { int y1; std::cin >> y1; int n; std::cin >> n; std::vector<int> s(n); for (auto &x : s) { std::cin >> x; } int y2; std::cin >> y2; int res = 0; for (int i = y1; i <= y2; ++ i) { if (std::find(s.begin(), s.end(), i) == s.end()) { res ++; } } std::cout << res << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
C
贪心，ping 一开始误判成 DP 了，然后贪心又被卡精度，开了 unsigned 才过。这场罚时从此处开始爆炸。然而此时，John 艰难开 D 题，而我在开最难的题目。。。
|
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 |
#include <bits/stdc++.h> using namespace std; #define PII pair<long long,long long> void solve() { int n; long long tot=0; cin >> n; vector<PII> a(n); for (int i=0;i<n;i++) { cin >> a[i].first >> a[i].second; tot+=a[i].second; } sort(a.begin(),a.end()); unsigned long long ans=0; long long earn=0; long long buy_tot=0,sell_tot=0; int buy=0,sell=n-1; while (buy_tot+a[buy].second<=tot/2) { buy_tot+=a[buy].second; earn=-a[buy].first*a[buy].second; buy++; while (sell_tot<buy_tot && sell_tot+a[sell].second<tot/2) { sell_tot+=a[sell].second; earn+=a[sell].first*a[sell].second; sell--; } ans+=earn; } while (buy<sell) { sell_tot+=a[sell].second; ans+=a[sell].first*a[sell].second; sell--; } ans+=a[buy].first*(buy_tot-sell_tot); cout << ans << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; for (;t;t--) solve(); return 0; } |
K
卡 L 之后和队友简单交流一下就发现 L 很不好开，于是就开始做 K，因为这题看上去非常模拟。但是实际上当时还是没有底，因为虽然数据很小，但是还是不清楚复杂度到底是不是需要剪枝，好在这题根本没打算卡我，最后非常顺利的过了。
其实我感觉 K 还是比较简单的，但是 K 过的人居然比 D 要少，是我没想到的。这题其实就是一个模拟 + BFS。其实非常好写（也许是题面太长的原因吗？）。
|
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 |
#include <bits/stdc++.h> using PII = std::pair<int, int>; using Grid = std::vector<std::vector<bool>>; const std::vector<PII> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; template<typename T> void chkmin(T &a, const T &b) { if (a > b) a = b; } void solve() { int n, m, k; std::cin >> n >> m >> k; Grid grid(n + 1, std::vector<bool>(m + 1, false)); for (int i = 1; i <= k; ++ i) { int x, y; std::cin >> x >> y; grid[x][y] = true; } auto check_inside = [&](int x, int y) -> bool { return x >= 1 && x <= n && y >= 1 && y <= m; }; int res = 2e9; std::queue<Grid> q; q.push(grid); while (q.size()) { auto cur = q.front(); q.pop(); bool flag = false; for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) { if (not cur[i][j]) continue; for (const auto &dir : dirs) { int x = i + dir.first, y = j + dir.second; if (not check_inside(x, y)) continue; if (not cur[x][y]) continue; int nx = x + dir.first, ny = y + dir.second; if (not check_inside(nx, ny) or cur[nx][ny]) continue; Grid next = cur; next[x][y] = next[i][j] = false; next[nx][ny] = true; flag = true; q.push(next); } } } if (not flag) { int cnt = 0; for (int i = 1; i <= n; ++ i) { for (int j = 1; j <= m; ++ j) { if (cur[i][j]) ++ cnt; } } chkmin(res, cnt); } } std::cout << res << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
I
我切完 K 之后，ping 在切 I 题。结束之后看了一眼题解，std 是二分做法，而我队友给的是贪心做法，这里不得不 %%% 了。
|
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 |
#include <bits/stdc++.h> using namespace std; #define PII pair<int,int> void solve() { int n,m; cin >> n >> m; int t; vector<pair<int,int>> pos(n*m+1); for (int i=0;i<n;i++) for (int j=0;j<m;j++) { cin >> t; pos[t]=make_pair(j,i); } set<PII> vis; vis.insert(make_pair(0,0)); vis.insert(make_pair(m-1,n-1)); int now; for (now=0;now<n*m;now++) { if (vis.count(pos[now])) continue; auto i=vis.lower_bound(pos[now]); auto j=i; j--; if (pos[now].first>=(*j).first && pos[now].first<=(*i).first && pos[now].second>=(*j).second && pos[now].second<=(*i).second) vis.insert(pos[now]); else break; } cout << now << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; for (;t;t--) solve(); return 0; } |
D
万恶之源，我和队友（John）打对拍一直调了 3h 才过的题。其实一开始我的思路就是对的，但是就是细节出问题，不是这里出问题，就是哪里少考虑。赛时还发现 std 的优先队列是大根堆还是小根堆我都一直没搞清楚。
self：
|
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 103 104 105 106 107 108 109 110 111 112 113 114 |
#include <bits/stdc++.h> using PII = std::pair<int, int>; using LL = long long; struct cmp { bool operator() (const PII &a, const PII &b) { return a.second - a.first < b.second - b.first; } }; template<typename T> void chkmax(T &a, const T &b) { if (a < b) a = b; } void solve() { int n, m; std::cin >> n >> m; std::vector<PII> val(n); for (auto &[a, b] : val) std::cin >> a >> b; if (n == 1) { std::cout << val[0].second << '\n'; return; } std::priority_queue<PII, std::vector<PII>, cmp> q; std::queue<PII> q2; for (int i = 0; i < n; ++ i) { if (val[i].first < val[i].second) { q.push(val[i]); } else { q2.push(val[i]); } } std::vector<PII> pos(std::min(m, n * 3 + 1) + 1, {0, 0}); LL res = 0; auto calc = [&](std::vector<PII> &pos) -> LL { LL res = 0; for (int i = 0; i < pos.size(); ++ i) { if (pos[i].first == 0) continue; if (i == 0) { res += pos[1].first ? pos[i].first : pos[i].second; } else if (i == pos.size() - 1) { res += pos[i - 1].first ? pos[i].first : pos[i].second; } else { res += pos[i - 1].first or pos[i + 1].first ? pos[i].first : pos[i].second; } } return res; }; for (int i = 0; i < m and q.size(); i += 2) { pos[i] = q.top(); q.pop(); } if (q.size()) { // 位置坐不下了 for (int i = m - 1; i >= 0 and (q.size() or q2.size()); -- i) { if (pos[i].first) continue; if (q.size()) { pos[i] = q.top(); q.pop(); } else { pos[i] = q2.front(); q2.pop(); } } } else { if (q2.size() == 1) { int i = std::min((int)pos.size() - 1, m - 1); while (pos[i].first == 0) -- i; if (i + 1 < m) { pos[i + 1] = q2.front(); chkmax(res, calc(pos)); pos[i + 1] = {0, 0}; } } for (int i = std::min((int)pos.size() - 1, m - 1); i >= 0 and q2.size(); -- i) { if (pos[i].first) continue; pos[i] = q2.front(); q2.pop(); } } chkmax(res, calc(pos)); std::cout << res << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
John：
|
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> #define int long long using namespace std; bool cmp(int a,int b){ return a>b; } void work(){ int n,m; cin>>n>>m; vector<int> a(n),b(n),c(n); int ans=0; for (int i = 0; i < n; ++i) { cin>>a[i]>>b[i]; c[i]=b[i]-a[i];//计算独居带来的收益 ans+=a[i];//首先默认群居 } if(n==1){//特判 cout<<b[0]<<endl; return; }else if(n==2){ if(m>2)cout<<max(b[0]+b[1],a[0]+a[1])<<endl; else cout<<a[0]+a[1]<<endl; return; } sort(c.begin(),c.end(),cmp); int x=m-n; int y=x; for (int i = 0; i < c.size(); ++i) { if(c[i]<=0||y<=0)break; ans+=c[i];//将这个人拆出来独居 y--;//可独居数量减1 if(i==c.size()-2){//如果是最后两个，拆分后必然导致出现两个独居 if(c[i+1]>0){ ans+=c[i+1]; break; } if(abs(c[i])>abs(c[i+1]))ans+=c[i+1];//考虑最后两人是否要拆分 else ans-=c[i]; break; } } cout<<ans<<endl; } signed main(){ int t; ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin>>t; while(t--){ work(); } } // // Created by johntime on 24-5-10. // |
考场上写的对拍：
BF：
|
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 |
#include <bits/stdc++.h> using PII = std::pair<int, int>; using LL = long long; struct cmp { bool operator() (const PII &a, const PII &b) { return a.second - a.first < b.second - b.first; } }; template<typename T> void chkmax(T &a, const T &b) { if (a < b) a = b; } void solve() { int n, m; std::cin >> n >> m; std::vector<PII> val(n); for (auto &[a, b] : val) std::cin >> a >> b; if (n == 1) { std::cout << val[0].second << '\n'; return; } LL ans = 0; auto calc = [&](std::vector<PII> &pos) -> LL { LL res = 0; for (int i = 0; i < pos.size(); ++ i) { if (pos[i].first == 0) continue; if (i == 0) { res += pos[1].first ? pos[i].first : pos[i].second; } else if (i == pos.size() - 1) { res += pos[i - 1].first ? pos[i].first : pos[i].second; } else { res += pos[i - 1].first or pos[i + 1].first ? pos[i].first : pos[i].second; } } return res; }; std::vector<PII> pos(m, {0, 0}); bool debug = false; auto dfs = [&](auto &&self, int u) -> void { if (u == n) { LL res = calc(pos); chkmax(ans, res); if (debug) { if (res == ans) { for (int i = 0; i < m; ++ i) { std::cout << pos[i].first << ' ' << pos[i].second << '\n'; } std::cout << '\n'; } } return; } for (int i = 0; i < m; ++ i) { if (pos[i].first) continue; pos[i] = val[u]; self(self, u + 1); pos[i] = {0, 0}; } }; dfs(dfs, 0); // debug = true; // dfs(dfs, 0); std::cout << ans << '\n'; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); int T; std::cin >> T; while (T --) { solve(); } } |
对拍：
|
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 |
import os, random def makedata(N): M = random.randint(N, N * 2 - 1) MaxN = int(1e9) string = '1\n' string += str(N) + ' ' + str(M) + '\n' for i in range(N): string += str(random.randint(1, MaxN)) + ' ' + str(random.randint(1, MaxN)) + '\n' with open('input.txt', 'w') as f: f.write(string) def judge(T, N): os.system('g++ d.cpp -o d.exe -std=c++17 -O2') # os.system('g++ dd.cpp -o dd.exe -std=c++17 -O2') os.system('g++ d_bf.cpp -o d_bf.exe -std=c++17 -O2') for i in range(T): print('Test', i) makedata(N) os.system('d.exe < input.txt > output.txt') # os.system('dd.exe < input.txt > output1.txt') os.system('d_bf.exe < input.txt > output2.txt') flag = False if os.system('fc output.txt output2.txt'): print('Wrong Answer on d.cpp') flag = True # if os.system('fc output1.txt output2.txt'): # print('Wrong Answer on dd.cpp') # flag = True if flag: break print('Accepted') if __name__ == '__main__': judge(10000000, 5) |
M
计算几何，没想到 ping 切了这道题。
|
1 |
// CF 上居然看不了队友自己交的代码？ |
发表回复