当前位置：首页 > news >正文

Wrong Collections

news 2026/4/24 21:23:46

4.5 P10188 [USACO24FEB] Milk Exchange B - 洛谷

观察问题的能力有待提升，如果肉眼找不出突破点，应该打表找找规律

3.26 P1908 逆序对 - 洛谷

太有价值了，综合树状数组、离散化（存数的时候当前的下标）、对于相同数字计数的处理

3.16 P9974 [USACO23DEC] Candy Cane Feast B - 洛谷

看起来很难找到正解思路，但是通过分析可以发现时间复杂度并不是O(n*m)

3.5 802. 区间和 - AcWing题库离散化复健

#include <bits/stdc++.h> using namespace std; int main() { int n, m; cin >> n >> m; vector<pair<int, int>> a; a.push_back({0, 0}); map<int, int> mp; for(int i = 1; i <= n; i++) { int x, y; cin >> x >> y; mp[x] += y; } for(auto [k, v] : mp) { a.push_back({k, v}); } for(int i = 1; i <= a.size() - 1; i++) { a[i].second += a[i - 1].second; } for(int i = 1; i <= m; i++) { int L, R; cin >> L >> R; int l = 1, r = a.size() - 1; while(l < r) { int mid = l + r + 1 >> 1; if(a[mid].first <= R) l = mid; else r = mid - 1; } if(a[l].first > R) { cout << 0 << endl; continue; } R = l; l = 1, r = a.size() - 1; while(l < r) { int mid = l + r >> 1; if(a[mid].first >= L) r = mid; else l = mid + 1; } if(a[r].first < L) { cout << 0 << endl; continue; } L = l; // cout << L << " " << R << endl; cout << a[R].second - a[L - 1].second << endl; } }

3.3 218. 扑克牌 - AcWing题库概率与期望 => 本质是基础的概率知识+记忆化搜索

事件发生的期望的线性性

将问题转为图
起点->终点的路径的期望长度
点(状态) 边(状态转移)

2.25 P11452 [USACO24DEC] Cake Game S - 洛谷

错解：

#include <bits/stdc++.h> #define int long long #define endl '\n' #define ios ios::sync_with_stdio(0), cin.tie(0) using namespace std; signed main() { ios; int t; cin >> t; while(t--) { int n; cin >> n; // 1 2 3 4 5 6 1 2 3 4 5 6 // 1 2 [7] 5 (6) 1 2 [7] 5 (6) // 1 [9] (5) (6) 1 2 ([12]) (6) // [10] (5) (6) // 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 // 1 2 3 [9] 6 7 (8) 1 2 3 4 [11] 7 8 9 (10) // 1 2 [12] 6 (7)(8) 1 2 3 4 [18] 8 (9) (10) // 1 [14] (6)(7)(8) 1 2 3 [22] (8) (9) (10) //[15] (6)(7)(8) // B每次选择max(h,t) A是被动选的 // A只能避开B的方向,因为如果A存在一次靠近B就会被B吃掉 // B第一次选最大的前缀或后缀?? list<int> lst; for(int i = 1; i <= n; i++) { int x; cin >> x; lst.push_back(x); } auto p = lst.begin(); // 指向第一个元素 // cerr << "error" << ' ' << *p << endl; advance(p, n / 2 - 1); // 直接修改指针，前进n/2-1步 int a = 0, b = 0; a += *p + *next(p, 1); lst.erase(next(p, 1)); // cerr << "error" << ' ' << a << endl; int cnt = 1; while(cnt < n / 2) { if(lst.front() > lst.back()) { b += lst.front(); lst.pop_front(); p = next(p, 1); lst.erase(prev(p, 1)); } else { b += lst.back(); lst.pop_back(); p = prev(p, 1); lst.erase(next(p, 1)); } a += *p; cnt++; } cout << a << " " << b << endl; } }

实际上，A无论怎么样都可以吃到n/2+1个蛋糕，但是总和被B控制，因为当B选择了一边之后,A只能选择合并另个方向的一个，否则合成的蛋糕会被B吃掉，所以A的上限由B决定，但是下限即最少吃多少是固定的（中间的最小连续n/2+1个之和）

2.23 E - Palindromic Shortest Path

好久没写图论相关的题了，感觉思路很值得学习：

当边包含很多信息时，尽可能拆成多个数组，组装入一个容器很容易混乱

#include <bits/stdc++.h> #define int long long using ll = long long; #define ios ios::sync_with_stdio(0), cin.tie(0); using namespace std; signed main() { int n; cin >> n; vector<vector<char>> e(n + 1, vector<char>(n + 1)); vector<vector<int>> d(n + 1, vector<int>(n + 1)); for(int i = 1; i <= n; i++) { string s; cin >> s; s = " " + s; for(int j = 1; j <= n; j++) { d[i][j] = 1e5; e[i][j] = s[j]; } } queue<pair<int, int>> que; for(int i = 1; i <= n; i++) { d[i][i] = 0; que.push({i, i}); } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(i == j || e[i][j] == '-') continue; d[i][j] = 1; que.push({i, j}); } } while(que.size()) { auto [i, j] = que.front(); que.pop(); for(int k = 1; k <= n; k++) { for(int l = 1; l <= n; l++) { if(e[k][i] == e[j][l] && e[k][i] != '-' && d[k][l] > d[i][j] + 2) { d[k][l] = d[i][j] + 2; que.push({k, l}); } } } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { if(d[i][j] == 1e5) cout << -1 << " "; else cout << d[i][j] << " "; } cout << endl; } }

E-和+和_牛客周赛 Round 82

难点在如何预处理前 i 个数字的最小/大的m个数字 => 优先队列维护堆中的最值

#include <bits/stdc++.h> using ll = long long; #define int ll #define ios ios::sync_with_stdio(0), cin.tie(0) using namespace std; const int mod = 998244353; signed main() { ios; int n, m; cin >> n >> m; vector<int> a(n + 1), b(n + 1); vector<int> pa(n + 1), pb(n + 1); for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) cin >> b[i]; priority_queue<int, vector<int>, less<int>> pq1, pq2; int suma = 0, sumb = 0; for(int i = 1; i <= n; i++) { if(i <= m) { pq1.emplace(a[i]); suma += a[i]; } else { auto h = pq1.top();// logn 级别的复杂度 if(h > a[i]) { pq1.pop(); pq1.push(a[i]); suma += a[i] - h; } } pa[i] = suma; } for(int i = n; i >= 1; i--) { if(i > n - m) { pq2.emplace(b[i]); sumb += b[i]; } else { auto h = pq2.top(); if(h > b[i]) { pq2.pop(); pq2.push(b[i]); sumb += b[i] - h; } } pb[i] = sumb; } int ans = 1e15; for(int i = m; i <= n - m; i++) { ans = min(ans, pa[i] + pb[i + 1]); } cout<<ans; }

2.19

双指针Problem - 1873F - Codeforces

#include <bits/stdc++.h> using namespace std; using ll = long long; signed main() { ios::sync_with_stdio(0), cin.tie(0); int t; cin >> t; while(t--) { int n, k; cin >> n >> k; vector<int> a(n + 1), h(n + 1); for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) cin >> h[i]; int max_len = 0, sum = 0; // 维护当前有效窗口的左右边界 for(int l = 1, r = 1; r <= n;) { // 新起点需要满足单元素条件 if(a[r] > k) { r++; l = r; sum = 0; continue; } // 尝试扩展右边界 if(l == r || h[r - 1] % h[r] == 0) { // 扩展窗口并维护sum sum += a[r]; // 当sum超过k时收缩左边界 while(sum > k) { sum -= a[l]; l++; } // cout << l << " " << r << endl; max_len = max(max_len, r - l + 1); r++; // 关键步进！ } else { // 不可扩展时重置窗口 sum = 0; l = r; } } cout << max_len << "\n"; } }

1.22 P9420 [蓝桥杯 2023 国 B] 子 2023 / 双子数 - 洛谷 | 计算机科学教育新生态

看起来简单，但是实现的时候很多细节容易错

大数组必须开全局，不然会爆栈（具体是终端进程自己结束）

注意大数相乘的上界，有时候甚至会超出unsigned long long，这个时候就要加特判

#include <bits/stdc++.h> using namespace std; using ll = unsigned long long; #define ios ios::sync_with_stdio(0), cin.tie(0) vector<int> prime; bool notprime[5000010]; int main() { ios; ll ans[2]; char T; cin >> T; // A string s = ""; for(int i = 1; i <= 2023; i++) { s += to_string(i); } vector<ll> dp(5); // dp1:2 // dp2:20 // dp3:202 // dp4:2023 for(int i = 0; i < s.size(); i++) { if(s[i] == '2') dp[1]++, dp[3] = dp[3] + dp[2]; else if(s[i] == '0') dp[2] = dp[2] + dp[1]; else if(s[i] == '3') dp[4] = dp[4] + dp[3]; } ans[0] = dp[4]; // B 区间最大值10^13 ，质数找到10^4 就可以了 // 错误的，如果是大数配小数呢？ auto find = [&](int n) -> void { for(int i = 2; i <= n; i++) { if(!notprime[i]) prime.push_back(i); for(int j : prime) { if(i * j > n) break; notprime[i * j] = 1; if(i % j == 0) break; } } }; ll cnt = 0; find(5000000); // for(auto i : prime) cout << i << endl; for(int i = 0; i < prime.size(); i++) { for(int j = i + 1; j < prime.size(); j++) { if(prime[i] >= 1e4 && prime[j] >= 1e4) break; if((ll)prime[i] * prime[i] * prime[j] * prime[j] < 2333) continue; if((ll)prime[i] * prime[i] * prime[j] * prime[j] > 1ll * 23333333333333) break; cnt++; } } ans[1] = cnt; cout << ans[T - 'A'] << endl; }

1.22 对拍要注意的几个点

代码的编码格式和终端的格式要一致:终端输入chcp ，查看终端编码格式，65001为utf8

终端修改：控制面板->时钟和区域-> 区域-> 管理-> 更改系统区域设置

1.14

D - 1122 Substring 很好的双指针

#include <bits/stdc++.h> using namespace std; int n; vector<int> a, cnt; int solve(int start_l) { for(int i = 1; i <= n; i++) cnt[i] = 0; int r = start_l; int ans = 0; for(int l = start_l; l <= n; l += 2) { while(r + 1 <= n && a[r] == a[r + 1] && cnt[a[r]] == 0) { cnt[a[r]] += 2; r += 2; } ans = max(ans, r - l); if(r >= l + 2) { cnt[a[l]] -= 2; } else r = l + 2; } return ans; } int main() { cin >> n; a.resize(n + 1), cnt.resize(n + 1); for(int i = 1; i <= n; i++) { cin >> a[i]; } int ans1 = solve(1); int ans2 = solve(2); cout << max(ans1, ans2); }

E - Takahashi is Slime 2

大数相除可能产生浮点时的去浮点操作

做题要思路严谨，多想一会儿

12.4 abc

E - 1D Bucket Tool 并查集？好难实现...

很考验并查集运用的题

#include <bits/stdc++.h> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> col(n + 1), colcnt(n + 1), l(n + 1), r(n + 1); vector<int> fa(n + 1), cnt(n + 1); for(int i = 1; i <= n; i++) { col[i] = fa[i] = l[i] = r[i] = i; colcnt[i] = cnt[i] = 1; } auto find = [&](auto self, int x) -> int { if(fa[x] != x) fa[x] = self(self, fa[x]); return fa[x]; }; auto paint = [&](int x, int c) -> void { int fx = find(find, x); colcnt[c] += cnt[fx]; colcnt[col[fx]] -= cnt[fx]; col[fx] = c; }; auto merge = [&](int x, int y) -> void { int px = find(find, x); int py = find(find, y); if(cnt[px] < cnt[py]) swap(px, py); fa[py] = px; l[px] = min(l[px], l[py]); r[px] = max(r[px], r[py]); cnt[px] += cnt[py]; }; while(q--) { int op; cin >> op; if(op == 1) { int x, c; cin >> x >> c; paint(x, c); int L = l[find(find, x)]; int R = r[find(find, x)]; if(L >= 2 && col[find(find, L - 1)] == c) merge(L - 1, x); if(R <= n - 1 && col[find(find, R + 1)] == c) merge(R + 1, x); } else { int c; cin >> c; cout << colcnt[c] << endl; } } }

12.2 abc

F - Falling Bars 线段树

9.21 abc

D - Buildings 没有头绪

正解：单调栈，唉，对单调队列和单调栈把握还是不深

E - K-th Largest Connected Components 思路正确，代码实现有问题（动态维护连通块的第K大点）

#include <bits/stdc++.h> #define int long long #define ios ios::sync_with_stdio(0), cin.tie(0) #define endl '\n' using namespace std; signed main() { ios; int n, q; cin >> n >> q; vector<int> fa(n + 1), sz(n + 1); for(int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1; vector<vector<int>> num(n + 1); for(int i = 1; i <= n; i++) num[i].push_back(i); auto find = [&](int x, auto self) -> int { if(fa[x] != x) { fa[x] = self(fa[x], self); } return fa[x]; }; auto merge = [&](int u, int v) -> void { if(sz[u] < sz[v]) swap(u, v); sz[u] += sz[v]; fa[v] = u; vector<int> temp; for(auto i : num[u]) { temp.push_back(i); } for(auto i : num[v]) { temp.push_back(i); } sort(temp.begin(), temp.end(),greater<int>()); num[u].clear(); for(int i = 0; i < min(10ll, (int)temp.size()); i++) { num[u].push_back(temp[i]); } }; while(q--) { int op; cin >> op; if(op == 1) { int u, v; cin >> u >> v; int fu = find(u, find); int fv = find(v, find); if(fu == fv) continue; merge(fu, fv); } else { int v, k; cin >> v >> k; int fv = find(v, find); cout << (sz[fv] < k ? -1 : num[fv][k-1])<<endl; } } }

9.19 带权并查集

P8710 [蓝桥杯 2020 省 AB1] 网络分析 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

9.12 abc 二进制枚举写的真不错 AtCoder Beginner Contest 369（A ~ G 题讲解）_哔哩哔哩_bilibili

E - Sightseeing Tour (atcoder.jp) √

9.11 div3 dp,但是以为是贪心

Problem - F - Codeforces

9.5 div3 dp

Problem - E - Codeforces √

Problem - G - Codeforces √ 又是数列互相加减跟gcd相关的数论，跟暑假牛客有题很像

Problem - H - Codeforces √

9.5 一道div3 启发式合并（按秩）

Problem - D - Codeforces √

#include <bits/stdc++.h> using namespace std; using ll = long long; vector<int> sz(2e5 + 10), fa(2e5 + 10), a(2e5 + 10), vis(2e5 + 10); string s; int find(int x) { if(x != fa[x]) fa[x] = find(fa[x]); return fa[x]; } void merge(int x, int y) { int px = find(x), py = find(y); if(px == py) return; if(sz[px] < sz[py]) swap(px, py); fa[py] = px; sz[px] += sz[py]; } void dfs(int pre, int p) { int x = a[p]; if(vis[x]) return; vis[x] = 1; sz[x] = (s[p] == '0'); if(pre != 0) { merge(pre, x); } dfs(x, a[p]); } int main() { ll t; cin >> t; while(t--) { int n; cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; iota(fa.begin(), fa.end(), 0); fill(sz.begin(), sz.end(), 0); fill(vis.begin(), vis.end(), 0); cin >> s; s = " " + s; for(int i = 1; i <= n; i++) { dfs(0, i); } for(int i = 1; i <= n; i++) cout << sz[find(a[i])] << " "; cout << endl; } }

8.26 niuke

小红的线段 √

小红的数组操作 √

8.17 abc

Pedometer √ 但是还是有点懵

E - Permute K times √ 倍增模板题

8.15 niuke10

Doremy's IQ 2

Collinear Exception

8.13 div3

Photoshoot for Gorillas √

8.9 niuke9