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; vectorpairint, int a; a.push_back({0, 0}); mapint, 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第一次选最大的前缀或后缀?? listint 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/21个蛋糕但是总和被B控制因为当B选择了一边之后,A只能选择合并另个方向的一个否则合成的蛋糕会被B吃掉所以A的上限由B决定但是下限即最少吃多少是固定的中间的最小连续n/21个之和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; vectorvectorchar e(n 1, vectorchar(n 1)); vectorvectorint d(n 1, vectorint(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]; } } queuepairint, 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; vectorint a(n 1), b(n 1); vectorint 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_queueint, vectorint, lessint 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]); } coutans; }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; vectorint 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) vectorint 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); } vectorll 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.14D - 1122 Substring 很好的双指针#include bits/stdc.h using namespace std; int n; vectorint 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 abcE - 1D Bucket Tool 并查集好难实现...很考验并查集运用的题#include bits/stdc.h using namespace std; int main() { int n, q; cin n q; vectorint col(n 1), colcnt(n 1), l(n 1), r(n 1); vectorint 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 abcF - Falling Bars 线段树9.21 abcD - 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; vectorint fa(n 1), sz(n 1); for(int i 1; i n; i) fa[i] i, sz[i] 1; vectorvectorint 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; vectorint temp; for(auto i : num[u]) { temp.push_back(i); } for(auto i : num[v]) { temp.push_back(i); } sort(temp.begin(), temp.end(),greaterint()); 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 369A ~ G 题讲解_哔哩哔哩_bilibiliE - Sightseeing Tour (atcoder.jp) √9.11 div3 dp,但是以为是贪心Problem - F - Codeforces9.5 div3 dpProblem - 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; vectorint 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 abcPedometer √ 但是还是有点懵E - Permute K times √ 倍增模板题8.15 niuke10Doremys IQ 2Collinear Exception8.13 div3Photoshoot for Gorillas √8.9 niuke9Sticky Pistons8.8 niuke8Haitang and GameHaitang and MathHaitang and Triangle8.6niuke7Fight Against the Monster8.4 niukezhousai清楚姐姐的布告规划 √ 简单DP竹鼠宝藏与故事8.3 abcTasks - Educational DP Contest (atcoder.jp)需要补概率DP和期望DP 比如这道J - Sushi (atcoder.jp)D - AtCoder Janken 3 √ 就是一个普通的DP应该多想想的E - Xor Sigma Problem8.1 niuke6Cake 2Puzzle: WagiriChallenge NPC 27.30 niuke5入知7.28 niukezhousai小红走矩阵 √ 加一维有奇效7.27 niuke4Friends √LCT √要加强并查集信息维护Yet Another Origami Problem √Good TreeSort4 √7.27 div31996E - Decode77.23 niuke3Crash Test √Bridging the Gap 2 √7.22 vpMany Many Heads √ 纯思维Gifts from Knowledge7.18 niuke2Red Playing Cards √ 有点难的区间DP 很不错的题解MST 迷糊了不知道为什么会T就这样吧Instructions Substring √