蓝桥杯17届B组c++
发布时间：2026/7/23 12:37:31
Ahttps://www.luogu.com.cn/problem/P16232思路:找规律(n1)/2B思路:打表,找规律,bfs,阶乘逆元来自B站up yeVegetablehttps://www.bilibili.com/video/BV1PzDkBsEzU/?spm_id_from333.1391.0.0打表找规律,很神奇,最后是个杨辉三角(遇到跟2有关的选项杨辉三角)#includebits/stdc.h using namespace std; #define ll long long #define ull unsigned long long #define endl \n void bfs(int n) { vectorints(n); queue vectorintq; mapvectorint,intdis; q.push(s); dis[s] 0; while (q.size()) { auto u q.front(); q.pop(); for (int i 0; i n; i) { auto v u; if (dis[u] % 2 0) { for (int j i; j n; j) v[j]^1; } else for (int j 0; j i; j) v[j] ^ 1; if (!dis.count(v)) { dis[v] dis[u] 1; q.push(v); } } } int ans 0; for (auto [v, d] : dis) { for (auto x : v)coutx ; cout endl; cout 步数 d endl; ans d; } cout 总步数 ans endl; } void solve() { for (int i 1; i 5; i) { cout n i endl; bfs(i); } } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int t 1;//cint; while (t--)solve(); return 0; }n操作数(0- ∞ )操作数的个数10 11 120 1 2 11 2 130 1 3 1 2 2 2 11 3 3 140 1 3 1 3 4 3 1 2 2 3 2 2 2 2 11 4 6 4 1………得出公式s u m ∑ i 1 n C n i ∗ i sum\sum_{i1}^n C^i_n*isum∑i1nCni∗i然后n2026求解#includebits/stdc.h using namespace std; #define ll long long #define ull unsigned long long #define endl \n ll fact[3000],inv[3000]; const int mod 998244353; ll fastpow(ll a, ll b) { ll res 1; while (b) { if (b 1)res res * a % mod; a a * a % mod; b 1; } return res; } ll calc(int n, int m) { if (m n)return 0; return fact[n] * inv[n - m] % mod * inv[m] % mod; } void solve() { fact[0] 1; for (int i 1; i 2026; i)fact[i] fact[i - 1] * i % mod; inv[2026] fastpow(fact[2026], mod - 2); for (int i 2025; i 0; i--)inv[i] inv[i 1] * (i 1) % mod; ll sum 0; for (int i 0; i 2026; i) { sum (sum calc(2026, i)*i%mod) % mod; } cout sum endl; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int t 1;//cint; while (t--)solve(); return 0; }Chttps://www.luogu.com.cn/problem/P16234思路:无即序列元素都相同#includebits/stdc.h using namespace std; #define ll long long #define ull unsigned long long #define endl \n void solve() { ll n, x, y; cin n x y; if (x y)cout 0 endl; else cout y - x 1 endl; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int t 1;cint; while (t--)solve(); return 0; }Dhttps://www.luogu.com.cn/problem/P16235思路:数论总和sum%50,队员的最大数量mxsum/5证:if mxsum/5,需要总人数mx*5sum,不成立,所以mxsum/5#includebits/stdc.h using namespace std; using ll long long; using ull unsigned long long; #define endl \n void solve() { ll n; cin n; ll maxx -1, sum 0; for (int i 0; i n; i) { ll num; cin num; maxx max(maxx, num); sum num; } if (sum % 5 ! 0 || maxx sum / 5) { cout F endl; } else { cout T endl; } } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int t 1; cin t; while (t--)solve(); return 0; }Ehttps://www.luogu.com.cn/problem/P16236思路:枚举,前缀和注意到在m个’?里左边为’L’右边为’Q’永远是最优的,在m里枚举分界线的位置#includebits/stdc.h using namespace std; using ll long long; using ull unsigned long long; #define endl \n int l[100010], r[100010]; void solve() { int n; cin n; string s; cin s; vectorintpos; if (s[0] ?)s[0] L; if (s[0] L)l[0] 1; if (s[n - 1] ?)s[n - 1] Q; if (s[n - 1] Q)r[n - 1] 1; for (int i 1; i n; i) { l[i] l[i - 1]; if (s[i] L)l[i] 1; else if (s[i] ?) { pos.push_back(i); s[i] Q; } } for (int i n - 2; i 0; i--) { r[i] r[i 1]; if (s[i] Q)r[i] 1; } ll res 0, cntl 0; for (int i 0; i n; i) { if (s[i] L)cntl; else res cntl; } ll ans res; for (int i 0; i pos.size(); i) { ans max(ans, res -l[pos[i]] r[pos[i] 1] - i); }//当前贡献res -(i左边原始L的个数)(i右边Q的个数)-(修改增加的L的个数 cout ans endl; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int t 1;//cint; while (t--)solve(); return 0; }Fhttps://www.luogu.com.cn/problem/P16237思路:并查集!!!考虑有环,要用并查集求块的数量,未联通的联通块也要联通,所以是cnt1个连通块需要cnt个跳线,计算cnt个跳线的度,用n个电脑去平摊,f(2*cnt)/n,f1,需要某块额外连一个块,0f1,保证一个块最多连一个块,f0,只有一个块。#includebits/stdc.h using namespace std; #define ll long long #define ull unsigned long long #define endl \n int fa[100010]; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void merge(int x, int y) { fa[find(x)] find(y); } void solve() { int n, m; cin n m; for (int i 1; i n; i)fa[i] i; for (int i 0; i m; i) { int a, b; cin a b; int fa find(a), fb find(b); if (fa ! fb) { merge(a, b); } } int cnt 0; for (int i 1; i n; i)if (fa[i] i)cnt; cout --cnt (2 * cnt n - 1) / n endl; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int t 1;//cint; while (t--)solve(); return 0; }Ghttps://www.luogu.com.cn/problem/P16238思路:最大字段和,前缀和先求出差值c[i]数组,计算从1到该位置0个数的前缀和s[i],把差值相同的下标用unordered_mapll,vectorint存起来,遍历差值,求最大字段和ans,最后答案为ans总0的个数。复杂度O(n)#includebits/stdc.h using namespace std; #define ll long long #define ull unsigned long long #define endl \n void solve() { int n; cin n; vectorlla(n1), b(n1), c(n1), s(n1); for (int i 1; i n; i) cin a[i]; for (int i 1; i n; i) cin b[i]; for (int i 1; i n; i)c[i] a[i] - b[i]; int c0 0; unordered_mapll, vectorintmp; for (int i 1; i n; i) { s[i] s[i - 1] (c[i] 0); if (c[i] 0)c0; else mp[c[i]].push_back(i); } int ans 0; for (auto [k, v] : mp) { int dp 1,mx 1;//初始 就可以选择这一个端点变为合法 for (int i 1; i v.size(); i) { int l v[i - 1], r v[i]; int cnt0 s[r - 1] - s[l]; dp max(1, dp 1 - cnt0);//字段和加上当前端点减去中间的0 mx max(mx, dp); } ans max(ans, mx); } cout ans c0 endl;//加上所有的0 } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int t 1;//cint; while (t--)solve(); return 0; }Hhttps://www.luogu.com.cn/problem/P16239思路:二分,优先队列核心数学原理边际收益我们要最大化乘积∏ ( a i k i b i ) \prod (a_i k_i b_i)∏(aikibi)。假设我们当前已经分配了一些天数现在多出 1 天该给谁给队员i ii乘积会变为原来的a i ( k i 1 ) b i a i k i b i 1 b i a i k i b i \frac{a_i (k_i1)b_i}{a_i k_i b_i} 1 \frac{b_i}{a_i k_i b_i}aikibiai(ki1)bi1aikibibi为了让乘积增幅最大我们要选择b i a i k i b i \frac{b_i}{a_i k_i b_i}aikibibi最大 的人。这等价于选择a i k i b i b i \frac{a_i k_i b_i}{b_i}biaikibi最小 的人。我们将这个值拆解a i b i k i \frac{a_i}{b_i} k_ibiaiki。这就变成了一个“补短板”的问题谁的“实力/天赋”比值加上已训练天数最小我们就训练谁。二分搜索寻找“水位线”因为m mm太大不能一个个加。代码想象了一个“水位线”p pp代码中 c[i] a[i] / b[i] 是每个队员初始的“基础水位”。如果我们想让所有队员的“水位”至少达到p pp那么第i ii名队员需要的训练天数k i p − c [ i ] k_i p - c[i]kip−c[i]如果p c [ i ] p c[i]pc[i]。chk§ 函数计算如果要达到水位p pp总共需要多少天。如果总天数≤ m \le m≤m说明水位p pp还可以更高。通过二分查找代码找到了在m mm天内能让所有人达到的最高整数水位l ll。处理余数精细排序二分只能处理整数部分 c[i]但实际的“水位”是a i b i k i ⌊ a i / b i ⌋ ⋅ b i r i b i k i \frac{a_i}{b_i} k_i \frac{\lfloor a_i/b_i \rfloor \cdot b_i r_i}{b_i} k_ibiaikibi⌊ai/bi⌋⋅biriki。即使整数部分相同余数r i r_iri越小的人其实际数值越小也就越优先需要训练。排序逻辑代码第 52-53 行比较两个人的“分数”r x b x \frac{r_x}{b_x}bxrx和r y b y \frac{r_y}{b_y}byry。代码通过 r[x] * b[y] r[y] * b[x]交叉相乘来避免浮点误差。余数比例越小的人在分配完基础天数后优先获得额外的 1 天训练机会。计算结果最后根据二分出的水位p pp和排序补齐的额外天数算出每个队员最终的实力值v a i k ⋅ b i v a_i k \cdot b_ivaik⋅bi累乘并取模得到答案。#includebits/stdc.h using namespace std; #define ll long long #define ull unsigned long long #define endl \n const ll mod 998244353; void solve() { int n; cin n; ll m; cin m; vectorll a(n), b(n), c(n), r(n); ll mx 0; for (int i 0; i n; i) { cin a[i] b[i]; if (b[i] 0) { c[i] a[i] / b[i]; // 实力比值 r[i] a[i] % b[i]; // 余数 mx max(mx, c[i]); // 记录最大实力比值二分上界 } else {// b[i]为0时c[i]设为一个极大值使其不参与二分补齐 c[i] 9e18; } } // 二分检测函数达到比值 p 需要多少天 auto check [](ll p) { ll s 0; for (int i 0; i n; i) { if (p c[i]) { s p - c[i]; if (s m) return s; // 防止累加溢出提前退出 } } return s; }; // 1. 二分查找最大可以达到的整数比值 p ll l 0, h mx m 1;//上界为最大比值加上所有天数保证足够大 while (l h) { ll mid (l h 1) 1; if (check(mid) m) l mid; else h mid - 1; } ll p l; // 最终比值 ll used check(p); ll rem m - used; // 剩下的天数每人最多再分1天 // 2. 按余数比例 r/b 从小到大排序 // 比例越小说明在当前比值下其实际实力越弱优先补齐 vectorint id; for (int i 0; i n; i) { if (b[i] 0 c[i] p) { id.push_back(i); } } sort(id.begin(), id.end(), [](int x, int y) { // 比较 r[x]/b[x] r[y]/b[y] - r[x]*b[y] r[y]*b[x] return (ll)r[x] * b[y] (ll)r[y] * b[x]; }); // 3. 分配额外的训练天数 vectorint ad(n, 0); for (int i 0; i id.size() i rem; i) { ad[id[i]] 1; } // 4. 计算最终结果 ll ans 1; for (int i 0; i n; i) { ll k 0;//天数 if (b[i] 0 p c[i]) { // 跳过不增长的和已达标的 k p - c[i];//补齐到比值 p 需要的天数 } if (ad[i]) k; // 如果分配了额外天数再加1 // 最终实力 v a k*b ll v (a[i] k * b[i]%mod)%mod; ans ans * v % mod; } cout ans endl; } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int t 1;//cint; while (t--)solve(); return 0; }总结:做题时想法很多,接近30%~80%,但是不能实际解决问题,在代码细节上还不熟练,代码从想法到实现不成熟;目标评估:思维67% 实现50%,目前刷题200个,目标400个。
