利用算法自动将内网机器进行分组，识别出哪些机器属于同一个业务集群
2026/7/23 14:04:15
A
https://www.luogu.com.cn/problem/P16232
思路:找规律
(n+1)/2
B
思路:打表,找规律,bfs,阶乘逆元
来自B站up yeVegetable
https://www.bilibili.com/video/BV1PzDkBsEzU/?spm_id_from=333.1391.0.0
打表找规律,很神奇,最后是个杨辉三角(遇到跟2有关的选项杨辉三角)
#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define endl '\n' void bfs(int n) { vector<int>s(n); queue <vector<int>>q; map<vector<int>,int>dis; 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)cout<<x<<" "; 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;//cin>>t; while (t--)solve(); return 0; }| n | 操作数 | (0- ∞ )操作数的个数 |
|---|---|---|
| 1 | 0 1 | 1 1 |
| 2 | 0 1 2 1 | 1 2 1 |
| 3 | 0 1 3 1 2 2 2 1 | 1 3 3 1 |
| 4 | 0 1 3 1 3 4 3 1 2 2 3 2 2 2 2 1 | 1 4 6 4 1 |
| … | … | … |
得出公式
s u m = ∑ i = 1 n C n i ∗ i sum=\sum_{i=1}^n C^i_n*isum=∑i=1nCni∗i
然后n=2026求解
#include<bits/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;//cin>>t; while (t--)solve(); return 0; }C
https://www.luogu.com.cn/problem/P16234
思路:无
即序列元素都相同
#include<bits/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;cin>>t; while (t--)solve(); return 0; }D
https://www.luogu.com.cn/problem/P16235
思路:数论
总和sum%5==0,队员的最大数量mx<=sum/5
证:if mx>sum/5,需要总人数mx*5>sum,不成立,所以mx<=sum/5
#include<bits/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; }E
https://www.luogu.com.cn/problem/P16236
思路:枚举,前缀和
注意到在m个’?'里左边为’L’右边为’Q’永远是最优的,在m里枚举分界线的位置
#include<bits/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; vector<int>pos; 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;//cin>>t; while (t--)solve(); return 0; }F
https://www.luogu.com.cn/problem/P16237
思路:并查集
!!!考虑有环,要用并查集求块的数量,未联通的联通块也要联通,所以是cnt+1个连通块需要cnt个跳线,计算cnt个跳线的度,用n个电脑去平摊,f=(2*cnt)/n,f>1,需要某块额外连一个块,0<f<1,保证一个块最多连一个块,f=0,只有一个块。
#include<bits/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;//cin>>t; while (t--)solve(); return 0; }G
https://www.luogu.com.cn/problem/P16238
思路:最大字段和,前缀和
先求出差值c[i]数组,计算从1到该位置0个数的前缀和s[i],把差值相同的下标用
unordered_map<ll,vector<int>>存起来,遍历差值,求最大字段和ans,最后答案为=ans+总0的个数。
复杂度O(n)
#include<bits/stdc++.h> using namespace std; #define ll long long #define ull unsigned long long #define endl '\n' void solve() { int n; cin >> n; vector<ll>a(n+1), b(n+1), c(n+1), s(n+1); 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_map<ll, vector<int>>mp; 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;//cin>>t; while (t--)solve(); return 0; }H
https://www.luogu.com.cn/problem/P16239
思路:二分,优先队列
- 核心数学原理：边际收益我们要最大化乘积∏ ( a i + k i b i ) \prod (a_i + k_i b_i)∏(ai+kibi)。假设我们当前已经分配了一些天数，现在多出 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_i+1)b_i}{a_i + k_i b_i} = 1 + \frac{b_i}{a_i + k_i b_i}ai+kibiai+(ki+1)bi=1+ai+kibibi为了让乘积增幅最大，我们要选择b i a i + k i b i \frac{b_i}{a_i + k_i b_i}ai+kibibi最大 的人。这等价于选择a i + k i b i b i \frac{a_i + k_i b_i}{b_i}biai+kibi最小 的人。我们将这个值拆解：a i b i + k i \frac{a_i}{b_i} + k_ibiai+ki。这就变成了一个“补短板”的问题：谁的“实力/天赋”比值（加上已训练天数）最小，我们就训练谁。
- 二分搜索：寻找“水位线”因为m mm太大，不能一个个加。代码想象了一个“水位线”p pp：代码中 c[i] = a[i] / b[i] 是每个队员初始的“基础水位”。如果我们想让所有队员的“水位”至少达到p pp，那么第i ii名队员需要的训练天数k i = p − c [ i ] k_i = p - c[i]ki=p−c[i]（如果p > c [ i ] p > c[i]p>c[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_ibiai+ki=bi⌊ai/bi⌋⋅bi+ri+ki。即使整数部分相同，余数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_iv=ai+k⋅bi，累乘并取模得到答案。
#include<bits/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; vector<ll> 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 从小到大排序 // 比例越小，说明在当前比值下其实际实力越弱，优先补齐 vector<int> 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. 分配额外的训练天数 vector<int> 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;//cin>>t; while (t--)solve(); return 0; }总结:
做题时想法很多,接近30%~80%,但是不能实际解决问题,在代码细节上还不熟练,代码从想法到实现不成熟;
目标评估:思维67% 实现50%,目前刷题200个,目标400个。