题目描述:
小蓝与蓝桥杯的缘分已经走到了第四个年头。从 2023 年的初出茅庐，到 2024、2025 年的披荆斩棘，而今年的 2026 年，将是他大学生涯最后一次站上这个赛场。
退役前夕，百感交集的小蓝在草稿纸上将这四届参赛的年份倒序写下，拼接成了一个巨大的整数 \(N = 2026202520242023\)。
在整理四年的竞赛心得时，他决定将这一常数 \(N\) 拆分为两个非负整数 \(x\) 和 \(y\)，分别代表他这段旅程的前半段积累与后半段突破。按照拆分规则，这两部分的数值之和必须恰好等于 \(N\)（即 \(x + y = N\)）。
同时，由于在后半段赛程中小蓝积累了更深厚的算法功底，因此后半部分的数值 \(y\) 必须严格大于前半部分的数值 \(x\)（即 \(0 \le x < y\)）。
现在，请你计算满足上述条件的整数对 \((x, y)\) 共有多少个？
题目描述:
无
输出格式: 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
寻找满足 \(x + y = 2026202520242023\) 的式子有多少个，其中 \(x,y\) 是非负整数。
我们可以发现，每一个固定的 \(x\) 都对应了一个固定的 \(y\)，所以最先想到的肯定是 \(\left \lfloor \frac{2026202520242023}{2} \right\rfloor\)。
然而这里有个坑点: \(x,y\) 是非负整数，所以当 \(x = 0\) 时也会有一组式子成立。
所以最终的答案就是
\[\left \lfloor \frac{2026202520242023}{2} \right \rfloor + 1 \]
时间复杂度: \(O(1)\)
题目描述:
城市照明系统的智能化改造是落实国家“双碳”战略的核心试点。作为示范工程，市能源局在新建的绿色大道上部署了一组由 \(2026\) 盏智能路灯组成的线性阵列。 初始状态下，这 \(2026\) 盏路灯均处于高能耗的“全亮模式”。为了评估系统在极端工况下的响应能力，该局的主控系统需要针对理论上存在的所有开关组合进行全状态遍历推演。
只是，受限于底层硬件的物理特性，主控系统必须严格按照“双向交替”的规则执行操作：
- 第奇数次指令（第 \(1, 3, 5 \dots\) 次）：系统需选定一盏路灯 \(i\)（\(1 \le i \le 2026\)），将该路灯及其右侧（后方）所有路灯的开关状态进行翻转（亮变暗，暗变亮）。
- 第偶数次指令（第 \(2, 4, 6 \dots\) 次）：系统需选定一盏路灯 \(i\)，将该路灯及其左侧（前方）所有路灯的开关状态进行翻转。
对于 \(2026\) 盏路灯，共存在 \(2^{2026}\) 种不同的明暗状态组合，每一种状态都必定能被抵达。针对每一种特定的状态，都存在一个从初始“全亮”状态到达该状态所需的最少指令操作次数（无论有多少种不同的操作序列可以到达该状态，仅以步数最少的为准）。
注意：初始的“全亮”状态也包含在这 \(2^{2026}\) 种组合中，且到达该状态的最少操作次数记为 \(0\) 次。
现在，请你计算出这全部 \(2^{2026}\) 种状态对应的最少操作次数的累加总和。由于总和可能很大，请将结果对 \(998244353\) 取模后输出。
输入格式:
无
输出格式:
这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
有 \(2026\) 盏灯，每盏灯都有“亮”与“灭”两种状态，共 \(2^{2026}\) 种状态。有两种操作:
求得到这些灯每种状态需要操作的最小次数的和。
这题我们可以打表找规律。
首先，按照题目大意写出暴力代码寻找规律。
void solve(){
int n = 2026;
cin >> n; // 指定灯的数量
vector<int> arr(n);
queue<vector<int> > q;
map<vector<int>, int> mp; // 到达每种状态所需的最少次数
q.emplace(arr);
mp[arr] = 0;
while(!q.empty()){
auto cur = q.front();
q.pop();
for(int i = 0; i < n; i ++){ // 枚举每个位置
auto nxt = cur;
if(mp[cur] & 1){ // 第奇数次操作
for(int j = i; j < n; j ++){
nxt[j] ^= 1;
}
}else{ // 偶数次操作
for(int j = 0; j <= i; j ++){
nxt[j] ^= 1;
}
}
if(!mp.count(nxt)){
q.emplace(nxt);
mp[nxt] = mp[cur] + 1;
}
}
}
for(auto &[cur, cnt] : mp){
// for(int i = 0; i < cur.size(); i ++){
// if(i > 0) cout << ", ";
// cout << cur[i];
// }cout << endl;
// cout << "cnt:" << cnt << endl;
cout << cnt << " ";
}cout << endl;
}
以下是得到的几个数据:
n = 1: 0 1
n = 2: 0 2 1 1
n = 3: 0 2 3 2 1 2 1 1
n = 4: 0 2 3 2 3 3 3 2 1 2 4 2 1 2 1 1
我们发现有的数字有重复，对其按照 num : cnt 的格式进行整理。
n = 1: 0 1
0:1 1:1
n = 2: 0 2 1 1
0:1 1:2 2:1
n = 3: 0 2 3 2 1 2 1 1
0:1 1:3 2:3 3:1
n = 4: 0 2 3 2 3 3 3 2 1 2 4 2 1 2 1 1
0:1 1:4 2:6 3:4 4:1
将所有的 cnt 单独领出来:
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
->
1: 1 1
2: 1 2 1
3: 1 3 3 1
4: 1 4 6 4 1
这时候就发现了，这其实是一个杨辉三角!!!
而这里的每个数代表的是，所有灯到达某个状态所需的最小次数 的个数。
故假设 所求杨辉三角行的值为 {\(a_{0},a_{1},\dots,a_{n}\)}则
\[ans = \sum_{i = 0}^{n} C_{n}^{i} \times i \]
因为这里的 n = 2026 所以我们直接通过逆元暴力求出每个 \(C_{n}^{i}\) 之后相乘求和就好了。
代码:
const ll MOD = 998244353;
const int N = 2026 + 10;
ll fac[N] = {1};
ll inv_fac[N];
ll fpow(ll a, ll b){
ll ans = 1;
while(b){
if(b & 1){
ans = ans * a % MOD;
}
a = a * a % MOD;
b >>= 1;
}
return ans;
}
ll get_inv(ll a){
return fpow(a, MOD - 2);
}
ll C(ll n, ll m){
return fac[n] * inv_fac[m] % MOD * inv_fac[n - m] % MOD;
}
void init(){
for(int i = 1; i < N; i ++){
fac[i] = fac[i - 1] * i % MOD;
}
inv_fac[N - 1] = get_inv(fac[N - 1]);
for(int i = N - 2; i >= 0; i --){
inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
}
}
void solve(){
init();
int n = 2026;
// cin >> n;
ll ans = 0;
for(int i = 0; i <= n; i ++){
ans = (ans + (C(n, i) * i % MOD)) % MOD;
}
cout << ans << endl;
}
时间复杂度: \(O(n)\)
题目描述:
给定三个整数 \(N, X, Y\)。请计算有多少个长度为 \(N\) 的整数数组 \(A\) 满足以下条件：
- 数组 \(A\) 中的每个元素 \(A_i\) 都满足 \(X \le A_i \le Y\)；
- 对于数组 \(A\) 中的任意一个连续子数组，对其进行一次循环右移操作，得到的新子数组与原数组完全一致。
循环右移：对一个长度为 \(k\) 的连续子数组 \([B_1, B_2, \dots, B_k]\) 执行一次循环右移操作，是指将该子数组变换为 \([B_k, B_1, B_2, ..., B_{k-1}]\)（即把最后一个元素移到最开头，其余元素保持原有顺序依次向后顺延一位）。
输入格式:
第一行包含一个整数 \(T\)，表示测试数据的组数。
接下来的 \(T\) 行，每行包含三个由空格隔开的整数 \(N, X, Y\)。
输出格式:
对于每组测试数据，输出一行，包含一个整数，表示满足条件的数组 \(A\) 的个数。
样例:
输入: 3 3 1 2 5 10 10 2 5 3 输出: 2 1 0数据规模:
对于 \(30\%\) 的评测用例，\(1 \le T \le 20\), \(1 \le N \le 100\), \(1 \le X, Y \le 100\);
对于 \(100\%\) 的评测用例，\(1 \le T \le 10^3\), \(1 \le N \le 10^{18}\), \(1 \le X, Y \le 10^{18}\)。
对于每个例子，给出 \(3\) 个数 \(n, x, y\) ，需要寻找有多少个长度为 \(n\) 的数组，其中每个数 \(a_i\) 满足 \(x \le a_i \le y\)，且对这个数组中的任意一个连续子数组进行任意次 循环右移 操作后和原数组完全一致。
首先，根据 \(x \le a_i \le y\)，如果 \(x \gt y\) 则答案为 \(0\)。
其次，对于任意一个数组，若选择其中任意一个连续子数组进行人一次 循环右移 操作后还和原数组完全一致，则说明该数组中所有元素完全一致，即 所求数组为 \([a, a, a, \dots, a]\) 这样的形式，其中 \(x \le a \le y\)。
所以最终答案就是
\[ans = \begin{cases} 0 &,x \gt y\\ y - x + 1 &,x \le y \end{cases} \]
注: 十年 \(OI\) 一场空，不开 \(long~long\) 见祖宗。
void solve(){
ll n, lf, rt;
cin >> n >> lf >> rt;
if(lf > rt){
cout << 0 << endl;
}else{
cout << rt - lf + 1 << endl;
}
}
signed main(void){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
时间复杂度: \(O(1)\)
题目描述:
小蓝，作为电竞俱乐部“蓝桥竞技”的战队经理，正面临着一个巨大的管理危机。俱乐部目前签约了 \(N\) 种不同位置的职业选手，其中第 \(i\) 种位置的选手共有 \(A_i\) 名。
为了参加即将举办的“峡谷 5v5”，小蓝必须将俱乐部内的所有选手都编入战队，不能有任何一人坐冷板凳。
根据赛事组委会的严苛规则，一支合法的战队必须满足以下条件：
- \(5\) 人成团：每支战队由且只能由 \(5\) 名选手组成。
- 职业互斥：同一支战队内的 \(5\) 名选手，必须来自 \(5\) 种完全不同的位置。
现在，请你帮助小蓝判断：在当前的人员数量下，是否有一种分组方案，能够将所有选手恰好分配完，且每支战队都符合参赛规则？
输入格式:
第一行包含一个整数 \(T\)，表示测试用例组数。
接下来包含 \(T\) 组数据，每组数据的格式如下：
- 第一行包含一个整数 \(N\)，表示职业位置的种类数量。
- 第二行包含 \(N\) 个整数 \(A_1, A_2, \dots, A_N\)，分别表示第 \(i\) 种位置的选手人数。
输出格式:
对于每组测试用例，如果存在满足条件的分组方案，输出 T，否则输出 F。
样例:
输入: 4 5 1 1 1 1 1 6 2 2 2 2 1 1 5 1 1 1 1 2 6 3 1 1 1 2 输出: T T F F样例说明:
第一组数据：共有 \(5\) 名选手，各占 \(1\) 个位置，恰好可以组成 \(1\) 支战队。第二组数据：共有 \(10\) 名选手，可以分成 \(2\) 支战队。一种合法的分配方案是：战队一由位置 \(1, 2, 3, 4, 5\) 的选手组成；战队二由位置 \(1, 2, 3, 4, 6\) 的选手组成。
第三、四组数据不存在满足条件的分组方案。
数据规模:
对于 \(30\%\) 的评测用例：\(1 \le T \le 5\), \(1 \le N \le 20\), \(0 \le A_i \le 100\);
对于 \(100\%\) 的评测用例：\(1 \le T \le 10^3\), \(1 \le N \le 10^5\), \(0 \le A_i \le 10^9\)，且保证所有测试用例中 \(N\) 的总和不超过 \(2 \times 10^5\)。
有 \(n\) 种不同位置的选手，第 \(i\) 种位置有 \(a_i\) 人。需要将所有选手分成若干支 \(5\) 人战队，每支战队中的 \(5\) 名选手必须来自 \(5\) 个完全不同的位置。问是否存在这样的分组方案，使得所有选手恰好被分配完。存在输出 T，否则输出 F。
arr: 选手数组。
sum: 所有选手数量的和。
显然，如果 \(sum \% 5 \not= 0\) 则不存在可行方案。
假设 \(cnt = \frac{sum}{5}\)，即可以分成的队伍数量。
若 \(arr_{i} \gt cnt\) 那么显然这个位置上一定会出现 2 个以上的选手被分配到同一个队伍的情况，所以不存在可行方案。
其他情况就一定会满足题目条件。
void solve(){
ll n; cin >> n;
vector<ll> arr(n);
ll sum = 0;
for(ll i = 0; i < n; i ++){
cin >> arr[i];
sum += arr[i];
}
if(sum % 5 != 0){
cout << "F" << endl;
return;
}
ll cnt = sum / 5;
for(ll i = 0; i < n; i ++){
if(arr[i] > cnt){
cout << "F" << endl;
return;
}
}
cout << "T" << endl;
}
signed main(void){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t = 1;
cin >> t;
while(t --){
solve();
}
return 0;
}
时间复杂度: \(O(n)\)
题目描述:
2056 年，探险队在月球背面的环形山深处发现了一座信号发射塔，其核心控制台正在不断闪烁着一串长度为 \(N\) 的粒子序列。
序列中的每个位置被严格定义为 \(L\) 型粒子、\(Q\) 型粒子，或者因岁月侵蚀而模糊不清的未知状态 \(?\)。这些粒子将被依次射入反应场，而反应场的稳定性取决于序列的“\(LQ\) 聚合”数量，该数量被定义为所有满足 \(1 \le i < j \le N\) 且第 \(i\) 个节点为 \(L\)、第 \(j\) 个节点为 \(Q\) 的二元组数量。
为了重启这座沉睡的巨塔，探险队需要将序列中所有的 \(?\) 修复为确定的 \(L\) 或 \(Q\)。
现在，请你计算出在所有可能的修复方案中，所能得到的“\(LQ\) 聚合”数量的最大值是多少。
输入格式:
第一行输入一个整数 \(N\)，表示粒子序列的长度。
第二行输入一个长度为 \(N\) 的字符串，仅包含字符 \(L\)、\(Q\) 和 $? $，表示当前探测到的粒子序列状态。
输出格式:
输出一个整数，表示在将所有 \(?\) 替换为 \(L\) 或 \(Q\) 后，能获得的最大“\(LQ\) 聚合”数量。
样例:
输入: 5 ??L?? 输出: 6样例说明:
一种最优的策略是将序列修复为 LLLQQ。此时位于前面的 \(3\) 个 \(L\) 与位于后面的 \(2\) 个 \(Q\) 共可产生 \(3 \times 2 = 6\) 个聚合。
数据规模:
对于 \(30\%\) 的评测用例，字符串 \(?\) 的个数不超过 \(10\)。
对于所有评测用例，\(2 \le N \le 10^5\)。
给定一个长度为 \(n\) 的字符串，只包含字符 L、Q 和 ?。可以将每个 ? 任意替换为 L 或 Q。定义“LQ 聚合”的数量为所有满足 \(1 \le i \lt j \le n\) 且第 \(i\) 个字符为 L、第 \(j\) 个字符为 Q 的二元组 \((i, j)\) 的个数。求在所有替换方案中，能获得的最大 LQ 聚合数量。
假设 s 为该字符串, ans 为 LQ聚合数量。
对于一个已知的字符串，例如 "LLQLQ"，计算这个字符串的 LQ聚合 的数量，我们可以从后往前看，关注每个 Q 字符，之后计算出该位置之前有多少个 L 字符，这就是该 Q 能对最总答案所能得到的贡献。依次计算下去求和就是最终的 LQ聚合 数量。
而对于有位置是未知的 ? 字符，那么这时候就可以采用 贪心 的思想，将所有的 ? 先视作 L，之后再根据其分别作为 L 和 Q 字符时对最终的答案贡献大小来具体的选择。
通过前面的计算过程，那么我们就知道了需要 从后往前 进行 贪心，同时需要维护一个前缀和来快速获取字符 L 的数量，而在最初我们将所有的 ? 字符都视为了 L，那么其对答案所贡献的数量就已经计算了一次(从后往前的过程中，先遇到的 Q 字符已经和该位置的 ? 即 L) 贡献，具体产生的贡献值即为该索引位置后面的 Q 的数量。所以我们还需要动态维护一个后缀和数组来快速获取 Q 的数量。接下来比对其作为 L 和 Q 所产生的贡献值的高低来确定最终该 ? 的值。
代码:
void solve(){
int n; cin >> n;
string s; cin >> s;
int ans = 0;
vector<int> pre_l(n, 0); // pre_l[i] := 前 i 个字符中 L 的个数
if(s.front() == 'L' || s.front() == '?') { // 初始化前缀和的第一个元素
pre_l[0] ++;
}
for(int i = 1; i < n; i ++){ // 构件前缀和数组，将所有的 ? 视为 L
pre_l[i] = pre_l[i - 1];
if(s[i] == 'L' || s[i] == '?') pre_l[i] ++;
}
int suf = 0; // 动态维护后缀中 Q 的个数
for(int i = n - 1; i >= 0; i --){
if(s[i] == 'Q'){ // Q 和前面的所有 L 都可以组成一组 LQ聚合(? 也视为 L)
ans += pre_l[i]; // 答案累加
suf ++; // 后缀中 Q 的个数增加
continue;
}
if(s[i] == 'L'){ // L 已经和后面的 Q 组成了 LQ聚合，产生过了贡献
continue;
}
if(s[i] == '?'){ // 尝试将该位置的 ? 从 L 改为 Q，判断是否能产生更多的贡献
// cur := 当前位置还视为 L 时能产生的贡献
// chg := 当前位置视为 Q 时所能产生的贡献
int cur = suf, chg = (i == 0 ? 0 : pre_l[i - 1]);
if(cur < chg){ // 将 ? 改为 Q 能产生更多的贡献
s[i] = 'Q';
ans += chg - suf; // 由于在此之前该位置视为 L 时，已经和后面的 Q 产生了贡献，所以增加的为 差值
suf ++; // 后缀中 Q 的个数增加
}else{
s[i] = 'L'; // 该位置为 L 所能产生的贡献更多
}
}
}
// cout << s <<endl;
cout << ans <<endl;
}
时间复杂度: \(O(n)\)
题目描述:
实验室内，小蓝负责维护一个由 \(N\) 台计算机组成的局域网络。这些计算机原本通过高速网线互联，但随着设备老化，目前仅剩 \(M\) 条网线还能正常工作。正因如此，原本统一的网络分裂成了多个互不相连的通信区域。
为了恢复通信，小蓝计划架设一种特殊的“应急跳线”来重新连接这些区域。在物理逻辑上，只要任意两台计算机之间可以通过残存的网线或新架设的应急跳线建立直接或间接的通路，即视为它们之间恢复了连通。小蓝的任务是选定最优的布线方案，使得实验室内的所有 \(N\) 台计算机重新回到全连通的状态。
由于应急跳线的接口会占用计算机宝贵的硬件资源，小蓝在制定方案时设定了两个优先层级：首先，必须确保使用的应急跳线总数达到理论上的最小值；其次，为了减轻单台计算机的负载压力，他要求尽可能平均地分摊这些跳线。具体而言，他需要寻找一种方案，使得在所有计算机中，接入这种应急跳线数量最多的那一台机器，其接入的跳线数降到最低。
现在，请你根据当前网线的残存连接情况，计算出实现全连通所需的最少应急跳线数量，以及在这一最优前提下，单台计算机接入应急跳线数量最大值的最小可能值。
输入格式:
第一行包含两个整数 \(N\) 和 \(M\)，分别表示计算机的总数和目前完好的网线数量。
接下来的 \(M\) 行，每行包含两个整数 \(a\) 和 \(b\)，表示计算机 \(a\) 和 \(b\) 之间目前仍存在一条完好的网线。
输出格式:
输出一行，包含两个由单个空格隔开的整数。第一个整数表示最少需要添加的应急跳线数量，第二个整数表示在确保跳线总数最少的前提下，单台计算机接入跳线数量最大值的最小可能值。
样例:
输入: 7 2 1 2 2 3 输出: 4 2样例说明:
通过连接 \(1-4\), \(4-5\), \(5-6\), \(6-7\)（共计 4 条跳线），可以使节点 \(4,5,6\) 各承担两条跳线，而其他节点仅承担一条或不承担，从而使最大值达到最小值为 \(2\)。
数据规模:
对于 \(30\%\) 的评测用例，\(1 \le N \le 100\), \(0 \le M \le 100\);
对于所有评测用例，\(1 \le N \le 10^5\), \(0 \le M \le 10^5\), \(1 \le a,b \le N\), \(a \ne b\)。保证输入的连接信息中不包含重边。
给定一个 \(N\) 个点、\(M\) 条边的无向图（可能不连通）。需要添加最少数量的边，使得整个图连通。在保证添加边数最少的前提下，要求最小化“所有节点中，因添加的边而产生的度数（即新加边的条数）”的最大值。输出两个整数：最少添加的边数，以及这个最小化的最大新边度数。
注: 本题的问题中询问的只和 添加的应急条线 有关，和原本遗留网线无关!!!
第一个问题:
需要添加最少数量的边，使得整个图连通，则数量即为 连通分量的数量 - 1。
第二个问题:
假设，添加了 \(k\) 条边，那么就会产生 \(2k\) 的度数，为了最小化所有节点中因添加边所产生的度数，故对其 均摊 即可。
也就是 \(ans = \lceil\frac{2k}{n}\rceil\)。
代码:
const int N = 1e5 + 10;
int n, m;
int fa[N];
void init(){
for(int i = 0; i < N; i ++) fa[i] = i;
}
int getFa(int x){
if(fa[x] == x) return x;
return fa[x] = getFa(fa[x]);
}
void Union(int x, int y){
x = getFa(x), y = getFa(y);
if(x == y) return ;
fa[x] = y;
}
void solve(){
cin >> n >> m;
int ans = 0;
for(int i = 0; i < m; i ++){
int u, v; cin >> u >> v;
Union(u, v);
}
int k = 0;
for(int i = 1; i <= n; i ++){
if(getFa(i) == i) k ++;
}
k --;
cout << k << " " << (k * 2 + n - 1) / n << endl;
}
signed main(void){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
init();
int t = 1;
// cin >> t;
while(t --){
solve();
}
return 0;
}
题目描述:
一条工业流水线上排列着 \(n\) 个温度传感器。当前各个传感器测得的温度记录在数组 \(A\) 中，而各传感器对应的理想标准温度记录在数组 \(B\) 中（即 \(A_i\) 为第 \(i\) 个传感器的当前温度，\(B_i\) 为第 \(i\) 个传感器的理想温度）。
为了让尽可能多的传感器达到理想温度，你可以进行一次区域温度补偿操作：
- 在流水线上划定一段连续的传感器区间 \([l, r]\)（即第 \(l\) 个到第 \(r\) 个传感器）。
- 输入一个温度补偿值 \(k\)（\(k\) 为任意整数），使得该区间内所有传感器的当前温度都加上 \(k\)。
请问在执行完这一次校准操作后，最多能使多少个传感器的温度恰好等于其对应的理想标准温度？
输入格式:
第一行包含一个整数 \(n\)，表示传感器的数量。
第二行包含 \(n\) 个整数 \(A_1, A_2, \dots, A_n\)，表示各传感器的当前温度。
第三行包含 \(n\) 个整数 \(B_1, B_2, \dots, B_n\)，表示各传感器对应的理想标准温度。
输出格式:输出一行，包含一个整数，表示补偿操作后处于理想温度的传感器最大数量。
样例:输入: 5 1 2 3 4 5 2 3 2 3 2 输出: 2数据规模:
对于 \(30\%\) 的评测用例，保证 \(1 \le n \le 2000\)；
对于所有评测用例，保证 \(1 \le n \le 2 \times 10^5\), \(-10^9 \le A_i, B_i \le 10^9\)。
给定两个长度为 \(n\) 的整数数组 \(A\) 和 \(B\)。可以选择一个连续子数组 \([l, r]\) 和一个整数 \(k\)，将该子数组内的每个 \(A_i\) 加上 \(k\)。操作后，统计有多少个位置 \(i\) 满足 \(A_i + k = B_i\)。求这个数量的最大值。
对数组 \(A\) 和 \(B\) 进行作差(\(B_{i} - A_{i}\)) 得到数组 arr。
这里给出一个例子 \(arr = [3, 1, 0, 3, 0]\) ，显然所有需要考虑的 \(k\) 值就只有 \(\{0, 1, 3\}\) 这 \(3\) 个数，因为 \(k\) 取其他的值是没必要的，只会让最终的结果为 \(0\)。
当 \(k = 0\) 时，答案是显而易见的，就是 arr 数组中 \(0\) 的个数。
当 \(k \not= 0\) 时，
因题目是任选一个区间 $[l,r] $，所以加 \(k\) 的 起始 和 结束 位置也是需要考虑的。
例如针对 \(arr = [0, 1, 0, 3, -1, 2, 3, 0, 3, 0, 2]\) 这个数组，若 \(k = 3\) ，显然没有必要对前 \(3\) 个元素和后 \(2\) 个元素进行操作。
仅需对中间部分进行 最大子数组和 计算，之后加上两边的 0 的个数就是最终答案。
代码:
void solve(){
int n; cin >> n;
vector<int> a(n + 1);
vector<int> b(n + 1);
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++) cin >> b[i];
vector<int> arr(n + 1); // 差值数组
unordered_map<int, vector<int> > mp; // 记录所有差值出现的下标
for(int i = 1; i <= n; i ++){
arr[i] = b[i] - a[i];
if(arr[i]) mp[arr[i]].emplace_back(i);
}
vector<int> pre(n + 1, 0); // 差值为 0 的次数前缀和
for(int i = 1; i <= n; i ++){
if(!arr[i]) pre[i] ++;
pre[i] += pre[i - 1];
}
int zero = pre.back(); // 差值为 0 的次数
int ans = 0;
for(auto &[it, li] : mp){ // 遍历所有差值
int cur = 0;
for(int i = 0; i < li.size(); i ++){ // 最这个差值数组计算最大子数组和
if(i == 0){
cur = 1;
}else{
// max(从该位置截断作为新的子数组的开头，继续扩展当前子数组)
cur = max(1ll, cur + 1ll - (pre[li[i]] - pre[li[i - 1]]));
}
ans = max(ans, cur);
}
}
cout << ans + zero << endl;
}
时间复杂度: \(O(n)\)
题目描述:
小蓝是一支足球队的队长，他正在为下一场重要比赛做准备。接下来的 \(m\) 天中，他每天可以选择一名队员进行训练，并且选择之后当天的训练对象不能更换。
球队中共有 \(n\) 名队员。对于第 \(i\) 名队员，已知其：
- 初始实力值为 \(a_i\)；
- 天赋值为 \(b_i\)。
训练规则如下：
- 如果小蓝在某一天训练了队员 \(i\)，则这一天会使该队员的实力值增加 \(b_i\)；
- 如果一共用 \(k\) 天来训练队员 \(i\)，那么这名队员的最终实力值将变为：\(a_i + k b_i\)。
一支队伍的整体实力定义为所有队员最终实力值的乘积，即：
\[\prod_{i=1}^{n} (a_i + k_i b_i) \]
其中 \(k_i\) 表示分配给第 \(i\) 名队员的训练天数，且满足：
\[k_i \ge 0, \quad \sum_{i=1}^{n} k_i = m \]
小蓝希望通过合理分配这 \(m\) 天的训练计划，使得队伍的整体实力最大。由于结果可能非常大，你只需要输出该最大值对 \(998244353\) 取模的结果。
输入格式:
输入共 \(n+1\) 行。
第一行包含两个正整数 \(n, m\)，分别表示队员人数和可用于训练的总天数。
接下来 \(n\) 行，第 \(i\) 行包含两个正整数 \(a_i, b_i\)，表示第 \(i\) 名队员的初始实力值与天赋值。
输出格式:
输出一行，包含一个非负整数，表示经过 \(m\) 天训练后，队伍实力的最大可能值对 \(998244353\) 取模的结果。样例:
输入: 2 3 4 2 5 3 输出: 66样例说明:
一种最优方案是：
- 第 \(1\) 名队员训练 \(1\) 天；
- 第 \(2\) 名队员训练 \(2\) 天。
此时：
- 第 \(1\) 名队员的最终实力为 \(4 + 2 \times 1 = 6\)；
- 第 \(2\) 名队员的最终实力为 \(5 + 3 \times 2 = 11\)。
队伍的整体实力为：\(6 \times 11 = 66\)，因此输出 \(66\)。
数据规模:对于 \(30\%\) 的数据，\(n, m \le 8\)；
对于 \(60\%\) 的数据，\(n, m, a_i, b_i \le 3000\)；
对于 \(100\%\) 的数据，\(1 \le n \le 100000\)，\(1 \le m \le 10^9\)，\(1 \le a_i, b_i \le 10^5\)。
有 \(n\) 名队员，第 \(i\) 名队员的初始实力为 \(a_i\)，天赋为 \(b_i\)。共有 \(m\) 天训练时间，每天可以且只能训练一名队员，训练一天可使该队员实力增加 \(b_i\)。设队员 \(i\) 训练了 \(k_i\) 天，则其最终实力为 \(a_i + k_i \cdot b_i\)，且满足 \(\sum k_i = m\)，\(k_i \ge 0\)。队伍整体实力为所有队员最终实力的乘积。求在最优分配下，这个乘积的最大值对 \(998244353\) 取模的结果。
假设，在经历几次训练后，除开 \(i,j\) 两名队员外的其他队员的实力乘积为 \(S\)，两名队员的 当前实力 与 天赋 分别为 \(\{a_{i}, b_{i}\}\) 和 \(\{a_{j}, b_{j}\}\)，接下来有两种选择:
假设训练第 \(i\) 名队员更优，则:
\[\begin{align} (a_{i} + b_{i}) \cdot a_{j} \cdot S &\gt a_{i} \cdot (a_{j} + b_{j}) \cdot S \\ a_{i} a_{j} + b_{i} a_{j} &\gt a_{i} a_{j} + a_{i} b{j} \\ b_{i} a_{j} &\gt a_{i} b_{j} \\ \frac{b_{i}}{a_{i}} &\gt \frac{b_{j}}{a_{j}} \\ \frac{a_{i}}{b_{i}} &\lt \frac{a_{j}}{b_{j}} \end{align} \]
所以需要训练 \(\frac{a_{i}}{b_{i}}\) 最小的一项，那么自然就可以使用 小根堆 来实现，最后将所有队员的实力相乘。
但这样暴力的时间复杂度为 \(O(n + m\log{n}) \to O(m \log{n})\) ，显然只能通过 \(60 \%\) 的数据。
通过 \(\frac{a_{i}}{b_{i}} \lt \frac{a_{j}}{b_{j}}\) 可以发现，每次的选择是具有 单调性 的。由于每次选择的都是 \(\frac{a_{i}}{b_{i}}\) 值最小的队员，共操作 \(m\) 次。
那么我们可以通过二分确定一个值 \(mid\)，即在经历 \(m\) 次训练之后，所有队员的 \(\frac{a_{i}}{b_{i}}\) 比值至少为 \(mid\) (\(\frac{a_{i}}{b_{i}} \ge mid\))。
那么对于每个队员，对其的训练次数就可以 \(O(1)\) 的快速计算.
\[cnt = \max(0, \left\lceil mid - \frac{a_{i}}{b_{i}} \right\rceil) \to \max(0, \left\lceil \frac{mid \cdot b_{i} - a_{i}}{b_{i}} \right\rceil) \]
证明:
假设队员 \(i\) 的 初始实力 与 天赋 为 \(\{a_{i}, b_{i}\}\)，对其训练了 \(cnt\) 次。
由于 \(\frac{a_{i} + cnt \cdot b_i}{b_{i}} \ge mid\)。(注意前后 \(a_{i}\) 的定义是不同的)
所以:
\[\begin{align} \frac{a_{i} + cnt \cdot b_i}{b_{i}} &\ge mid \\ a_{i} + cnt \cdot b_{i} &\ge mid \cdot b_{i} \\ cnt \cdot b_{i} &\ge mid \cdot b_{i} - a_{i} \\ cnt &\ge \frac{mid \cdot b_{i} - a_{i}}{b_{i}} \end{align} \]
因为 \(cnt\) 为整数，所以 \(cnt\) 最小值为 \(\left\lceil \frac{mid \cdot b_{i} - a_{i}}{b_{i}} \right\rceil\)。
在确定最终的 \(mid\) 后，遍历所有队员对其进行训练，接下来可能还会有剩余的训练次数(很小)，用前面介绍的 小根堆 暴力解决，之后将所有值相乘。
代码:
const int MOD = 998244353;
struct Node{
ll x, y;
Node() = default;
Node(ll x, ll y) : x(x), y(y) {}
bool operator<(const Node &nxt) const{
return x * nxt.y > nxt.x * y;
}
};
ll n, m;
vector<Node> arr;
bool chk(double mid){
ll sum = 0;
for(int i = 0; i < n; i ++){
ll cnt = max(0ll, (ll)ceil((double)(mid * arr[i].y - (double)arr[i].x) / arr[i].y));
sum += cnt;
if(sum > m) return false;
}
return true;
}
void solve(){
cin >> n >> m;
for(int i = 0; i < n; i ++){
int u, v; cin >> u >> v;
arr.emplace_back(u, v);
}
double lf = 0.0, rt = 1e15;
double mid;
// 固定二分100次
int e = 100;
while(e --){
mid = lf + (rt - lf) / 2.0;
if(chk(mid)){
lf = mid;
}else{
rt = mid;
}
}
// 对每个队伍，根据得到的 lf 值，对其进行训练
for(int i = 0; i < n; i ++){
ll cnt = max(0ll, (ll)ceil((double)(lf * arr[i].y - (double)arr[i].x) / arr[i].y));
arr[i].x += cnt * arr[i].y;
m -= cnt;
}
// 处理剩余的训练次数
priority_queue<Node, vector<Node> > pq;
for(int i = 0; i < n; i ++) pq.emplace(arr[i]);
while(m --){
Node cur = pq.top(); pq.pop();
cur.x += cur.y;
pq.emplace(cur);
}
// 计算答案
int ans = 1;
while(!pq.empty()){
ans = (ans * pq.top().x) % MOD;
pq.pop();
}
cout << ans << endl;
}
时间复杂度: \(O(n\log{n})\)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。