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

牛客周赛 Round 91

news 2025/4/30 6:51:45

赛时成绩如下：

A. while

题目描述

小歪找到了一个由五个字符构成的字符串，它一次可以选择任意一个字符，将其修改为另一个字符，他想要知道，将这个字符串修改为 "while" 需要的最少操作次数。

解题思路：统计不同字符的个数

代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){string s;cin>>s; string a="while";int cnt=0;for(int i=0;i<5;i++){if(s[i]!=a[i]) cnt++;}cout<<cnt<<endl;
}

B. oken

题目描述

小歪正在研究大模型，但是，token很贵。他一共进行了 n 次对话，第 i 次对话的token使用 ai 表示。每一次对话都会回溯最近的十次对话，所以，第 j 次对话的真实token用量 aj+aj−1+aj−2+⋯+aj−9。如果不足十次，则不足部分用 0 补齐。
现在，小歪想知道，真实token用量最多的一次对话，最多用了多少token。

解题思路：维护一个大小为10的窗口, 然后维护一个最大值即可, 我用的是deque实现的, 为了防止爆int, 我们把数据范围开到long long

代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {int n;cin >> n;vector<long long> a(n);for (int i = 0; i < n; i++) cin >> a[i];long long totalSum = 0,res = 0;deque<long long> q;  for (int i = 0; i < n; i++) {totalSum += a[i];q.push_back(a[i]);if (q.size() > 10) {totalSum -= q.front();q.pop_front();}res = max(res, totalSum);}cout << res << endl;return 0;
}

C.小苯的逆序对和

题目描述

小苯拿到了一个长度为 n 的排列 a，他希望你帮他找出一对总和最大的逆序对，请你帮帮他吧。（你只需要输出这个最大和即可。）
形式化的：请找出一对下标 i,j (1≦i<j≦n)且 ai>aj，并最大化 ai+aj。

数据范围：n(排列a的长度) -> [1,2x10^5], 卡你两层循环呢，但是某蓝某桥某杯一般不卡。

ai -> [1,n]

解题思路：为了最大化ai+aj, 我们依旧是在遍历的同时去维护一个最大值, ai和前i-1个数中的最大值 x 进行比较, x>ai, 配对成功 -> (x,ai)。然后此基础上求出所有的情况的最大值

代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {int t;cin >> t;while (t--) {int n;cin >> n;vector<int> a(n);for (int i = 0; i < n; ++i) cin >> a[i];int res = 0;int b = a[0];for (int j = 1; j < n; ++j) {if (b > a[j]) {res = max(res, b + a[j]);}b = max(b, a[j]);}cout << res << endl;}return 0;
}

D. 数组4.0

题目描述

小红有一个长度为 n 的数组 a，下标从 1 开始。
如果两个数ai,aj的绝对差值为1, 那么 i,j 之间存在一条无向边。
为了使得所有索引之间相互可达，小红至少需要手动再加多少条边。

数据范围：数组长度n -> [1, 2x10^5], 依旧卡你两层循环 ;

数组的第i个元素ai -> [1,2x10^5]

解题思路：题意说的是由n-1个节点, 确保让每两个数ai,aj，都满足|ai-aj|=1

如果两个数ai,aj的绝对差为1，是不需要进行连边的，当做一个连通块；另外如果两个数ai,aj的绝对差不为1，此时需要连边，eg: 1 3 5, 这就需要连3-1=2条(这就是为啥代码中结果count-1) , eg: 1 2 4 5 -> 连续的数字是(1,2)和(4,5), 不需要连边, 一共两个连通块，连接两个联通块需要1条边 eg: 1 1 3 3 ->没有连续的数字, 每个都是独立的联通块, 1：freq(2) 3: freq(2) , 一共4个联通块, 需要3条边

#include <bits/stdc++.h>
using namespace std;
int main(){int t;cin >> t;while (t--){int n;cin >> n;vector<int> b(n);for (int i = 0; i < n; i++) cin >> b[i];sort(b.begin(), b.end());vector<pair<int,int>> groups;for (int i = 0; i < n; ){int v = b[i], cnt = 0;while (i < n && b[i] == v){cnt++;i++;}groups.emplace_back(v, cnt);   
//             连续相同数字的出现次数}int count = 0;   //联通块的数量int m = groups.size();for (int i = 0; i < m; ){int j = i;while (j+1 < m && groups[j+1].first == groups[j].first + 1){j++;}if(i == j){count += groups[i].second;    
//                 需要手动添加的边数} else {count += 1;     
//                 连续字符是一个连通块               }i = j + 1;}int ans = max(0, count - 1);cout << ans << endl;}return 0;
}

E-小苯的矩阵反转

题目描述

小苯有一个 n 行 m 列的 01 矩阵，其中有些格子是 1，另一些为 0。小苯希望从其中选择恰好：两行（可以相同），或两列（可以相同），或一行和一列。将选择的行和列中的数字先后 "反转"。（即 0 变 1，1 变 0。）
（需要注意的是：如果同时选择了行和列，则交叉点处的点会 "反转" 两次，相当于没有 "反转"。）
现在他想知道，他是否可以把矩阵变成全 0 的，请你帮他确定一下吧。

数据范围：n,m都是[1,10^3], 这次不卡你两层循环了

解题思路：模拟即可

代码如下：

#include <bits/stdc++.h>
using namespace std;
int main(){int t;cin >> t;while (t--){int n, m;cin >> n >> m;vector<string> a(n);for (int i = 0; i < n; i++)  cin >> a[i];vector<int> rowSum(n, 0), colSum(m, 0);long long total = 0;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (a[i][j] == '1'){rowSum[i]++;colSum[j]++;total++;}}}if (total == 0) {cout << "YES"<< endl;continue;}{int cnt = 0;bool f = false;for (int i = 0; i < n; i++){if (rowSum[i] == m) cnt++;else if (rowSum[i] != 0) { f = true; break; }}if (!f && cnt == 2 && total == 2LL * m) {cout << "YES" << endl;continue;}}{int cnt = 0;bool f = false;for (int j = 0; j < m; j++){if (colSum[j] == n) cnt++;else if (colSum[j] != 0) { f = true; break; }}if (!f && cnt == 2 && total == 2LL * n) {cout << "YES" << endl;continue;}}if (total == (long long)(m - 1) + (n - 1)){int ri = -1, cj = -1;for (int i = 0; i < n; i++){if (rowSum[i] == m - 1){if (ri != -1) { ri = -2; break; }ri = i;}}for (int j = 0; j < m; j++){if (colSum[j] == n - 1){if (cj != -1) { cj = -2; break; }cj = j;}}if (ri >= 0 && cj >= 0 && a[ri][cj] == '0'){bool f = true;for (int j = 0; j < m; j++){if (j == cj) continue;if (a[ri][j] != '1'){ f = false; break; }}for (int i = 0; f && i < n; i++){if (i == ri) continue;if (a[i][cj] != '1'){ f = false; break; }}for (int i = 0; f && i < n; i++){if (i == ri) continue;for (int j = 0; j < m; j++){if (j == cj) continue;if (a[i][j] != '0'){ f = false; break; }}}if (f){cout << "YES" << endl;continue;}}}cout << "NO" <<endl;}return 0;
}

F. 小苯的因子查询

题目描述

小苯对奇数很感兴趣，他给定了一个正整数 n，希望你求出：如果从 n!（即 n 的阶乘）的因子中随机等概地取一个数，则其是奇数的概率是多少，请你帮他算一算吧。

x 的因子：即整除 x的正整数，例如 3 就是 6 的因子，2 也是。

解题思路：P=奇数因子数/总因子数，设n!=2^e*m(m为奇数), 所以总因子数=(e+1)*奇数因字数(m) , 所以 P=m/m*(e+1)=1/(e+1), 接着计算e, (e是n!中2的幂次)，就是累加二进制数中所有的1, __builtin_ctz(i)是计算i的二进制末尾 0 的个数, 题目结果计算的是分数%M，将除法转化为乘法 eg: p/q mod M => p*q^-1 mod M,q^-1是q的模逆元我们这里使用递推式预处理逆元，c[1]=1, c[i]=(M - M / i) * c[M % i] % M (i>1)，注：c[i] 表示 i^−1 mod M, 最后答案是c[b[n] + 1]

代码如下：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int M = 998244353;
int solve(ll a, ll b){ return int((a*b) % M); }
int main(){int t;cin >> t;vector<int> a(t);int maxn = 0;for(int i = 0; i < t; i++){cin >> a[i];maxn = max(maxn, a[i]);}vector<int> b(maxn+1);b[0] = 0;for(int i = 1; i <= maxn; i++){b[i] = b[i-1] + __builtin_ctz(i);}int maxe = b[maxn]; vector<int> c(maxe + 2);c[1] = 1;for(int i = 2; i <= maxe+1; i++){c[i] = solve(M - M/i, c[M % i]);}for(int i = 0; i < t; i++){int n = a[i];int x = b[n];int ans = c[x + 1];cout << ans;if (i + 1 < t) cout << ' ';}return 0;
}