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

牛客 周赛110 20251007

牛客 周赛110 20251007

https://ac.nowcoder.com/acm/contest/118760

A:
题目大意:给定 \(n\) 个白球,每次可以将 \(2,3\) 个白球染为红色,判断通过无限次操作能否将所有球都变为红色

void solve(){int n;cin >> n;if (n == 1) cout << "NO";else cout << "YES";
}

当且仅当只有一个球时不能全部被染色,因为除 \(1\) 以外的所有正整数都能被表示为 \(2i+3j\) 的形式

B:
题目大意:给定 \(n\) 个元素的数组,重新排列后使得 \(S = (a_1 + a_2) + (a_2+ a_3) +\cdots+(a_{n - 1}+a_{n})\) 的值最大

void solve(){int n;cin >> n;vector<int> a(n);for (auto &x : a) cin >> x;sort(a.begin(), a.end());LL sum = 0;for (auto x : a) sum += x;cout << sum * 2 - a[0] - a[1] << '\n';
}

整理方程可以得到 \(S = 2\times\sum\limits_{i = 1} ^n a_i - a_1 -a_2\) ,找到最小的 \(a_1,a_2\) 代入方程可以得到最大的 \(S\)

C:

题目大意:

image-20251006143927539

void solve(){int n;cin >> n;vector<int> a(n);for (auto &x : a) cin >> x;int ans = -1;for (int i = 0; i < n - 1; i ++){if (a[i] == 0 || a[i + 1] == 0){if (a[i + 1] == a[i] + 1 || a[i] == a[i + 1] + 1)ans = max(ans, -1);elseans = max(ans, max(a[i], a[i + 1]) - 1);}elseans = max(ans, max(a[i], a[i + 1]));}cout << ans << '\n';
}

首先对一段序列来说,他的 MAX 一定是他其中的一个元素,要使得 MAX-MEX 最大,那么就是让这个序列的 MEX 最小。又因为一个序列越长他的 MEX 一定不会变小,所以说我们的序列越短越好

遍历这个数组,找每两个相邻的元素,这两个元素组成的序列一定是最优的,每次都判断 MAX 和 MEX 即可找到答案

时间复杂度 \(O(n)\)

D:
题目大意:

image-20251006144359761

void solve(){int n;cin >> n;vector<LL> a(n);for (auto &x : a) cin >> x;sort(a.begin(), a.end());LL md = a[(n - 1) / 2];LL sum1 = 0, sum2 = 0;LL mx1 = 0, mx2 = 0;LL ans = 1e18;if (n & 1){LL mdl = a[(n - 1) / 2 - 1];for (int i = 0; i < n; i ++){sum1 += abs(a[i] - md);sum2 += abs(a[i] - mdl);if (i <= n / 2)mx1 = max(mx1, md - a[i]);elsemx2 = max(mx2, a[i] - mdl);}ans = min(sum1 - mx1, sum2 - mx2);cout << ans << '\n';}else{int mdr = a[(n - 1) / 2 + 1];for (int i = 0; i < n; i ++){sum1 += abs(a[i] - md);sum2 += abs(mdr - a[i]);if (i >= n / 2)mx1 = max(mx1, a[i] - md);elsemx2 = max(mx2, mdr - a[i]); }ans = min(sum1 - mx1, sum2 - mx2);cout << ans << '\n';}
}

题目定义的中位数是下标下取整的元素,考虑删去元素后中位数发生的变化

  • 如果 \(n\) 为奇数,那么删去下标 \(\lfloor\frac{n}{2}\rfloor\) 左边的元素后,中位数不发生变化,删去右边的元素后,中位数变为原来下标 \(\lfloor\frac{n}{2}\rfloor - 1\) 的这个元素
  • 如果 \(n\) 为偶数,删去下标 \(\lfloor\frac{n}{2}\rfloor\) 左边的元素,中位数变成原来下标 \(\lfloor\frac{n}{2}\rfloor + 1\) 的这个元素,删去右边的元素中位数不发生改变

对这两种情况分别进行讨论,维护两个平衡度,找在相应范围内最大的 \(a_i - \mathrm{median}\)

最终的答案为根据左右两侧的 \(\sum \lvert a_i -\mathrm{median}\rvert - \mathrm{max}(a_i,\mathrm{median})\) 取较小值

E:
题目大意:

image-20251006145938916

void solve() {string s;cin >> s;const int n = s.size();s = ' ' + s;vector<int> a(n);for (int i = 1; i <= n; i ++) a[i] = s[i] - '0';vector<vector<LL>> dp(9, vector<LL>(n + 1, 0));dp[0][0] = 1;for (int i = 1; i <= n; i ++) {dp[0][i] = 1;for (int j = 0; j < 9; j ++){dp[(j + a[i]) % 9][i] += dp[j][i - 1];}}vector<int> sum(9);for (int i = 0; i < 9; i ++)sum[i] = accumulate(dp[i].begin() + 1, dp[i].end(), 0);sum[0] -= n;int l = 0;for (int i = 1; i <= n; i ++){if (a[i] == 0 && l == 0){l = i;}else if (a[i] != 0 && l != 0){LL d = i - l;l = 0;sum[0] -= d * (d + 1) / 2;}}if (l){LL d = n - l + 1;sum[0] -= d * (d + 1) / 2;}LL ans = 0;for (int i = 0; i < 9; i ++)ans += 1ll*sum[i] * ((i + 8) % 9 + 1);cout << ans << '\n';
}

一个数的根其实是这个数的数位之和对 \(9\) 取模的余数,考虑子区间对答案的贡献可以利用计数DP

区间 \(a_{i:j}\) 的余数如果为 \(m\) ,那么这段区间对答案的贡献也为 \(m\)

特别的,如果一段区间对 \(9\) 取模的余数为 \(0\) ,当这个区间的所有元素都为 \(0\) 时显然这个区间对答案是没有贡献的

否则非全 \(0\) 区间对答案的贡献为 \(9\)

定义 \(dp_{i,j}\) 表示\(a_j\) 子区间的最后一个元素且前缀和对 \(9\) 取模的余数为 \(i\) 的区间个数

状态转移方程为

\[dp_{i,j} =dp_{i-a[j](\mathrm{mod}\ 9), j-1},i\in[0,8] \]

\(sum_i = \sum\limits_{j} dp_{i,j}\) 表示区间和对 \(9\) 取模的余数为 \(i\) 的所有子区间个数

遍历数组找到所有的全 \(0\) 区间,最后对每个 \(sum_i\) 统计总贡献

需要注意的是,DP过程中,我们初始化 \(dp_{0,j} = 1\) 的原因是我们可以只选取子区间 \([j,j]\) ,存在空前缀和等于 \(0\)

\(dp_{0,j}\) 表示从 \(j\) 开始的子区间,相当于「空前缀 + 当前数位」

F:
题目大意:
image-20251006152648022

void solve(){int n;cin >> n;vector<int> a(n + 1);for (int i = 1; i <= n; i ++) cin >> a[i];vector<int> p(n + 1);for (int i = 1; i <= n; i ++) p[i] = a[i] ^ p[i - 1];int ans = p[n];for (int i = 1; i <= n; i ++)ans = max(ans, p[i] & (p[n] ^ p[i]));cout << ans << '\n';
}

存在这样一个结论是:通过合并操作可以将序列划分为多个区间,当区间个数为 \(1\) 或者 \(2\) 时才存在最优解

简单证明:

当区间数为奇数时 (\(n\ge3\)),形如 \(x_1,x_2,x_3\) 当这三个数的某一位 \(d_i\) 上都为 \(1\) ,区间 AND 的结果 \(x^\prime\)\(d_i\) 才为 \(1\)

显然如果将这三个区间都合并,那么 \(d_i\) 异或后同样为 \(1\)

这里可以得出如果最终的答案的 \(d_i\)\(1\)那么合并奇数个包含 \(d_i = 1\) 的区间一定不会使答案变劣

相反,在某些位置 \(d_j\) 如果既有 \(1\) 又有 \(0\) ,合并奇数个区间后 \(d_j\) 是有可能变为 \(1\)

所以对于能合并的奇数个区间一定要合并,所以最终的区间划分情况要么是被划分一整个区间,要么就是两个区间

所以维护一个前缀异或和,枚举每一个区间分裂的位置,统计答案即可

http://www.hskmm.com/?act=detail&tid=25549

相关文章:

  • Python列表初始化的陷阱:重复引用的坑
  • MongoDB
  • 实用指南:第三十三天打卡复习
  • 实用指南:Hardening fixes lead to hard questions
  • 赛前训练6 状压
  • 排序综合
  • NKOJ全TJ计划——NP11745
  • InfinityFree教程 ——免费搭建属于你的网站
  • 关于调和级数估算前n项的和
  • 10.6 模考 T4(QOJ 1836)
  • 实用指南:【Node.js 深度解析】npm install 遭遇:npm ERR! code CERT_HAS_EXPIRED 错误的终极解决方案
  • 顺序结构
  • Windows漏洞利用技巧:虚拟内存访问陷阱(2025更新)
  • Python编译期优化:隐藏在代码背后的效率魔法
  • 一篇文章带你了解 WGCLOUD运维监控系统的部署与应用
  • 选择结构
  • Python函数默认参数陷阱:可变对象的共享问题深度解析
  • 无需安装的Photoshop:网页版完整使用指南与在线图片编辑技巧
  • 求阶
  • gin 框架 - 教程
  • 赛前训练 5 树形 dp
  • 递推求解逆元
  • 一些做题记录(2025 2-3)
  • 智慧决策的透明化路径:“空白金兰契”架构下的“悟空备案制”研究
  • 笔记:寻找适合自己的简历工具(YAMLResume)
  • 实用指南:Linux 权限管理入门:从基础到实践
  • vue插槽
  • Magnet Axiom 9.6 新增功能概览 - 数字取证与分析
  • Windows 11 24H2 中文版、英文版 (x64、ARM64) 下载 (2025 年 9 月发布)
  • Windows 11 25H2 正式版发布,新增功能简介