CSP2023 游记
-
7:50 作为 GD-SZ 的蒟蒻来到耀华考场,碰到了机房的同学们,和我们的 zx 老师
-
8:27 拿到密码,解压 PDF,
解压的时候密码输错了好几次 -
8:30 把文件目录创建好,开始看 T1 一开始只想到用模拟,之后发现它每一次都从头开始取,就只用判断 n 在当前的位置 mod 3 是否为 1 就好,简单切掉
#include <bits/stdc++.h> using namespace std; int n, ans; int main(){ freopen("apple.in", "r", stdin); freopen("apple.out", "w", stdout); cin >> n; int pos = n, cnt = 1; while (n){ if (n % 3 == 1 && ans == 0) ans = cnt; n -= (n + 2) / 3; cnt++; } cout << cnt - 1 << " " << ans; return 0; }
-
8:50 开始看 T2,没思路,往后看看,发现后面每一题都没思路,老老实实回来看 T2,发现可以贪心:找到最近的比自己小的点取更新。简单切掉。
#include <bits/stdc++.h> #define ll long long using namespace std; ll n, d, ans; ll v[100005], a[100005], s[100005]; int main(){ freopen("road.in", "r", stdin); freopen("road.out", "w", stdout); cin >> n >> d; for (int i = 2; i <= n; i++){ cin >> v[i]; s[i] = s[i - 1] + v[i]; } for (int i = 1; i <= n; i++) cin >> a[i]; int pos = 1, pre = 0; while (pos != n){ int temp = pos; for (int i = pos; i <= n; i++){ if (a[i] < a[pos]){ temp = i; break; } } if (temp == pos){ ans += (s[n] - s[pos] + d - 1 - pre) / d * a[pos], pos = n; } else{ ans += (s[temp] - s[pos] + d - 1 - pre) / d * a[pos]; pre += ((s[temp] - s[pos] + d - 1 - pre) / d * d) - (s[temp] - s[pos]), pos = temp; } } cout << ans; return 0; }
赛后发现有的同学比如说 @gsczl71 就没判断要不要加油,然后挂到 15pts,还好我是计算路程而不是油量。
-
9:40 看 T3,大模拟,想着给代码写写注释方便调试,结果写了跟写了一样,就删了。没什么好说的就是细节多,差不多 10:50 都准备放弃了结果发现没判断 -b = 0 的情况。然后对拍过了!!!
当时我都快喊出来了 -
甚至我不敢用 __gcd 怕 CE
#include <bits/stdc++.h> using namespace std; int t, m, a, b, c; int gcd(int x, int y){ if (x == 0) return y; if (y == 0) return x; if (x >= y) return gcd(x - y, y); if (x < y) return gcd(x, y - x); } void print(int x, int y){ bool flag = 0; if (x == 0){ cout << "0"; return ; } if ((x < 0 && y > 0) || (x > 0 && y < 0)) flag = 1; x = abs(x), y = abs(y); int tmp = gcd(x, y); if (flag) cout << "-"; if (tmp == 1) cout << x << "/" << y; else if (y / tmp == 1) cout << x / tmp; else cout << x / tmp << "/" << y / tmp; } int find(int x){ int tmp = 0; for (int i = 1; i <= sqrt(x); i++){ if (i * i <= x && x % (i * i) == 0) tmp = i; } return tmp; } int main(){ freopen("uqe.in", "r", stdin); freopen("uqe.out", "w", stdout); cin >> t >> m; while (t--){ cin >> a >> b >> c; if (b * b - 4 * a * c < 0) cout << "NO"; else{ int temp = sqrt(b * b - 4 * a * c); if (temp * temp == b * b - 4 * a * c){ if (a * 2 < 0) print(-b - sqrt(b * b - 4 * a * c), a * 2); else print(-b + sqrt(b * b - 4 * a * c), a * 2); } else{ if (-b != 0) print(-b, 2 * a), cout << "+"; temp = find(b * b - 4 * a * c); bool flag = 0; if (2 * a < 0) flag = 1, a = -a; int tmp = gcd(temp, 2 * a); if (flag) a = -a; if (temp != 1){ if (tmp > 1 && temp / tmp > 1) cout << temp / tmp << "*"; else if (tmp == 1) cout << temp << "*"; } cout << "sqrt(" << (b * b - 4 * a * c) / (temp * temp) << ")"; if (2 * abs(a) / tmp > 1) cout << "/" << 2 * abs(a) / tmp; } } cout << "\n"; } return 0; }
-
10:50 切完 C 题看 D 题,感觉很玄学,就直接 dfs 结果只骗到了十分,没用分层图
#include <bits/stdc++.h> using namespace std; int n, m, k, ans = 0x3f3f3f3f; int vis[10005]; vector<pair<int, int>> g[10005], v; void dfs(int x, int tm, int li){ if (x == n){ v.push_back({tm, li}); return ; } for (int i = 0; i < g[x].size(); i++){ int v = g[x][i].first; if (vis[v] == 1 || v == 1) continue; vis[v] = 1; dfs(v, tm + 1, max(li, g[x][i].second - tm)); vis[v] = 0; } } int main(){ freopen("bus.in", "r", stdin); freopen("bus.out", "w", stdout); cin >> n >> m >> k; for (int i = 1, u, v, a; i <= m; i++){ cin >> u >> v >> a; g[u].push_back({v, a}); } dfs(1, 0, 0); for (int i = 0; i < v.size(); i++){ if ((v[i].first + (v[i].second + 2) / k * k) % k == 0) ans = min(ans, v[i].first + (v[i].second + 2) / k * k); } if (ans == 0x3f3f3f3f) cout << "-1"; else cout << ans; return 0; }
-
最后留了充足的 20 min 检查文件操作和文件名。我们班有人只拿了 T1 的 100pts,结果 T1 文操写错了,含泪爆零,你说对不对 RJC
-
中午在家睡了但又没睡,又去了耀华。
-
14:27 拿到密码,先看题,发现 T1 好像很水,但又因为这是 S 组的第一题我觉得没那么水,结果我硬是试图推翻正解,最后实在想不出来了,就把“正解”写了上去,没想到真的时正解。
切完这题才想起来创文件目录#include <bits/stdc++.h> using namespace std; int n, ans; int a[10], b[10], mp[10][10][10][10][10]; int main(){ freopen("lock.in", "r", stdin); freopen("lock.out", "w", stdout); cin >> n; for (int i = 1; i <= n; i++){ cin >> a[1] >> a[2] >> a[3] >> a[4] >> a[5]; for (int j = 1; j <= 5; j++){ for (int k = 1; k <= 9; k++) a[j] = (a[j] + 1) % 10, mp[a[1]][a[2]][a[3]][a[4]][a[5]]++; a[j] = (a[j] + 1) % 10; } for (int j = 1; j <= 4; j++){ for (int k = 1; k <= 9; k++){ a[j] = (a[j] + 1) % 10, a[j + 1] = (a[j + 1] + 1) % 10; mp[a[1]][a[2]][a[3]][a[4]][a[5]]++; } a[j] = (a[j] + 1) % 10, a[j + 1] = (a[j + 1] + 1) % 10; } } for (int i = 0; i <= 9; i++){ for (int j = 0; j <= 9; j++){ for (int k = 0; k <= 9; k++){ for (int l = 0; l <= 9; l++){ for (int p = 0; p <= 9; p++) ans += mp[i][j][k][l][p] == n ? 1 : 0; } } } } cout << ans; return 0; }
结果 AC 了
-
14:50 开始看 T2,只想到个暴力解法,最后发现还是最暴力的,只能拿 35 pts,然后尝试加个前缀和,最后挂了 25pts。但不得不说这复杂度是真的有点玄学。
#include <bits/stdc++.h> using namespace std; int n, ans; string s; int mp[8005][30]; int main(){ freopen("game.in", "r", stdin); freopen("game.out", "w", stdout); cin >> n >> s; mp[0][s[0] - 'a'] = 1; for (int i = 1; i < n; i++){ for (int j = 0; j < 26; j++) mp[i][j] = mp[i - 1][j]; mp[i][s[i] - 'a']++; } for (int i = 0; i < n; i++){ for (int j = i + 1; j < n; j += 2){ string t = s.substr(i, j - i + 1); int flag = 0; for (int k = 0; k < 26; k++){ if ((i == 0 && mp[j][k] % 2 == 1) || (i != 0 && (mp[j][k] - mp[i - 1][k]) % 2 == 1)) flag = 1; } if (flag) continue; int temp = t.size(); for (int l = 1; l <= log2(temp) + 1 && !t.empty(); l++){ for (int k = 0; !t.empty() && k < t.size() - 1; k++){ if (t[k] == t[k + 1]) t.erase(k, 2); } } if (t.empty()) ans++; } } cout << ans; return 0; }
-
15:30 T3又来大模拟?!一看就是不想做的程度,果断打个特殊点 A 走人,骗到 15 分。
#include <bits/stdc++.h> #define ll long long using namespace std; int t, op, lst; map<string, ll> mp, sz, tp; int main(){ freopen("struct.in", "r", stdin); freopen("struct.out", "w", stdout); cin >> t; sz["byte"] = 1, sz["short"] = 2, sz["int"] = 4, sz["long"] = 8; while (t--){ cin >> op; if (op == 1) continue; if (op == 2){ string s, n; cin >> s >> n; cout << (lst + sz[s] - 1) / sz[s] * sz[s] << endl; lst = (lst + sz[s] - 1) / sz[s] * sz[s] + sz[s]; mp[n] = lst - sz[s], tp[n] = sz[s]; } if (op == 3){ string n; cin >> n; cout << mp[n] << endl; } if (op == 4){ int n, flag = 0; cin >> n; for (auto it : mp){ if (it.second + tp[it.first] - 1 >= n && n >= it.second){ cout << it.first << endl; flag = 1; break; } } if (!flag) cout << "ERR" << endl; } } return 0; }
别看这时间充裕,其实一点都不充裕,T2 想智障优化想了至少 1h,结果还没有优化前的分数高。
-
最后也不知道几点了,看 T4,直接暴力,结果暴力写挂了,实在没有时间了,果断结束,去检查文操去了。
#include <bits/stdc++.h> using namespace std; int n, ans = 0x3f3f3f3f; int a[100005], b[100005], c[100005], h[100005], vis[100005]; vector<int> g[100005], v; void dfs(int x, int fa, int d){ for (int i = 1; i <= n; i++){ if (h[i] >= 0) h[i] += max(b[i] + d * c[i], 1); } h[x] = max(b[x] + d * c[x], 1); v.push_back(x); if (d == n){ // cout << x << " " << d << "\n"; // for (int i = 1; i <= n; i++) cout << h[i] << " "; int cnt = 0; for (int i = 1; i <= n; i++){ int tmp = d + 1; while (h[i] < a[i]){ h[i] += max(b[i] + tmp * c[i], 1); tmp++; } cnt += tmp - d - 1; } // cout << cnt << endl; ans = min(ans, cnt); return ; } // for (int i = 0; i < v.size(); i++) cout << v[i] << " "; // cout << endl; int temp = v.size(); for (int i = 0; i < temp; i++){ for (int j = 0; j < g[v[i]].size(); j++){ if (vis[g[v[i]][j]]) continue; vis[g[v[i]][j]] = 1; dfs(g[v[i]][j], x, d + 1); vis[g[v[i]][j]] = 0; } } h[x] = -1; for (int i = 1; i <= n; i++){ if (h[i] >= 0) h[i] -= max(b[i] + d * c[i], 1); } v.pop_back(); } int main(){ freopen("tree.in", "r", stdin); freopen("tree.out", "w", stdout); memset(h, -1, sizeof(h)); cin >> n; for (int i = 1; i <= n; i++){ cin >> a[i] >> b[i] >> c[i]; } for (int i = 1, u, v; i < n; i++){ cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vis[1] = 1; dfs(1, 0, 1); cout << ans + 3; return 0; }
这次 J 组发挥不错 小图灵 100 + 100 + 100 + 10,洛谷 100 + 100 + 100 + 15。
S 组时间分配有问题,优化也没想对,之后 100 + 25 + 15 + 0。
祈祷能够蓝勾,最好能够 1=。
标签:cout,int,CSP2023,cin,mp,freopen,ans,游记 From: https://www.cnblogs.com/ccf-ioi/p/17857980.html