牛客 周赛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:
题目大意:
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:
题目大意:
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:
题目大意:
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\) 的区间个数
状态转移方程为
记 \(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:
题目大意:
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\) 的
所以对于能合并的奇数个区间一定要合并,所以最终的区间划分情况要么是被划分一整个区间,要么就是两个区间
所以维护一个前缀异或和,枚举每一个区间分裂的位置,统计答案即可