A. 给三个数 \(x\) \(y\) \(n\) 。需要构造一个长度为 \(n\) 的数组满足以下条件
- \(a_1 = x\), \(a_n = y\) 。
- \(a\) 严格递增。
- 定义 \(b_i = a_{i + 1} - a_{i}\) ，\(b\) 严格递减。
显然前两个条件非常宽松，定义好起始点，让 \(a\) 严格单调递增即可。
显然 \(b\) 是 \(a\) 的差分数组，从后往前贪心地让 \(b_{n - 1} = 1，b_{n - 2} = 2, \cdots, b_2 = n - 2\) 构造出 \(a_2\) 到 \(a_n\) 即可。然后只需要判断 \(a_2 - a_1\) 满足 \(\geq n - 1\) 时合法。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve() {
int x, y, n; std::cin >> x >> y >> n;
std::vector<int> a(n+1);
a[1] = x; a[n] = y;
for (int i = n - 1, cur = 1; i >= 2; --i, cur++) {
a[i] = a[i + 1] - cur;
}
if (a[2] - a[1] >= n - 1) for (int i = 1; i <= n; i++) std::cout << a[i] << " \n"[i==n];
else std::cout << -1 << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while ( _-- ) { solve(); }
return 0;
}
B. 给一个长为 \(n\) 的字符串 \(s\) 和一个正整数 \(k, (k - 1 \leq n)\) 。允许做任意次以下步骤。
- 交换第 \(i\) 位和第 \(i + 2\) 位字符
- \(reverse\) 第 \(i\) 位到 \(i + k - 1\) 位的字符
经过任意次上次操作后使 \(s\) 字典序最小。
- 允许无限次交换次数的情况下：第一步操作意味着可以任意排列偶数位和奇数位上的字符。
- 允许无限次 \(reverse\) 的情况下：
- \(k \& 1\) 即 \(revrse\) 段的长度为奇数时时不会改变奇偶位。答案唯一。
- \(!k \& 1\) 即 \(revrse\) 段的长度为偶数时
- \(k = n\) ，即整段 \(reverse\) ，互换所有的奇偶位，此时答案为两种选一。（虽然这题没这个条件，没意思）
- \(1 \leq k \leq n - 1\) ，可以互换任意一对奇数位元素和偶数位元素。
故讨论 \(k\&1\) ，\(!k\&1\ and\ k=n\)，\(!k\&1\ and\ k<n\) 三种情况即可。
view
#include <bits/stdc++.h>
typedef long long ll;
char s[2000005], s_odd[2000005], s_even[2000005];
void solve() {
int n, k; std::cin >> n >> k;
for (int i = 1; i <= n; i++) {
std::cin >> s[i];
if (i & 1) s_odd[(i+1)/2] = s[i];
else s_even[i/2] = s[i];
}
std::string ans = "";
if (k & 1) {
std::sort(s_odd + 1, s_odd + (n+1)/2 + 1, [&](char a, char b){
return a < b;
});
std::sort(s_even + 1, s_even + n/2 + 1, [&](char a, char b){
return a < b;
});
for (int i = 1; i <= n/2; i++) ans += s_odd[i], ans += s_even[i];
if (n&1) ans += s_odd[n/2+1];
}
else {
if (k == n) {
std::string ts1 = "", ts2 = "";
std::sort(s_odd + 1, s_odd + (n+1)/2 + 1, [&](char a, char b){
return a < b;
});
std::sort(s_even + 1, s_even + n/2 + 1, [&](char a, char b){
return a < b;
});
for (int i = 1; i <= n/2; i++) ts1 += s_odd[i], ts1 += s_even[i];
if (n&1) ans += s_odd[n/2+1];
for (int i = n; i; --i) {
int l = n - i + 1;
if (l & 1) s_odd[(l+1)/2] = s[i];
else s_even[l/2] = s[i];
}
std::sort(s_odd + 1, s_odd + (n+1)/2 + 1, [&](char a, char b){
return a < b;
});
std::sort(s_even + 1, s_even + n/2 + 1, [&](char a, char b){
return a < b;
});
for (int i = 1; i <= n/2; i++) ts2 += s_odd[i], ts2 += s_even[i];
if (n&1) ans += s_odd[n/2+1];
ans = std::min(ts1, ts2);
}
if (k < n) {
std::sort(s + 1, s + n + 1, [&](char a, char b){
return a < b;
});
for (int i = 1; i <= n; i++) ans += s[i];
}
}
std::cout << ans << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while ( _-- ) { solve(); }
return 0;
}
C. 给一个数 \(x\) ，把它变成 \(1\) 。具体操作为每次可以让 \(x\) 减去一个它的因子，但是每个因子不能减去超过两次。
题目其实有引导性地让我们分两步做，每一步每个因子至多会用到一次。
方法：以二进制形式观察 \(x\) 。
- 第一步，让 \(x\) 每次减去最低位的 \(1\) 直到 \(x\) 只余一个 \(1\) 。
- 第二部，让 \(x\) 的 \(1\) 每次右移一位直到变为 \(\cdots 0001\) 。
第一步，显然二进制上任意一个 \(1\) 的权重不同，不会重复。
只需证： \(x\) 最低位的 \(1\) 一定是它的因子 。（此题主要考点）
证明：将二进制低位到高位编号，最低位为 \(0\) 。第 \(k\) 个 \(1\) 代表 \(2^{i_k}\)。显然有 \(2^{i_1} | 2^{i_1} + 2^{i_2} + \cdots + 2^{i_k}\) 。qed。
第二步，也显然余下的 \(x\) 只剩下一个 \(1\) 即 \(2^m\) 的形式，每次减去一半既是它的因子，也不重复。
两步分别用到的因子不重复，故总的用到的因子不会重复 \(2\) 次以上。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve() {
int x; std::cin >> x;
std::vector<int> ans(1, x);
while ( __builtin_popcount(x) != 1 ) {
x -= ( x & ( -x ) );
ans.push_back(x);
}
while (x != 1) {
x >>= 1;
ans.push_back(x);
}
int m = ans.size(); std::cout << m << '\n';
for (int i = 0; i < m; i++) std::cout << ans[i] << " \n"[i==m-1];
}
int main() {
int _ = 1; std::cin >> _;
while ( _-- ) { solve(); }
return 0;
}
D. 给一个 \(n \times n\) 的 \(01\) 网格。定义 \(a_{i, j}\) 的一次翻转为 \(a_{i, j} \oplus 1\) 。
对 \((i, j)\) 位置的格子翻转会产生以下影响：
- 自身翻转，即 \(a_{i, j} = a_{i, j} \oplus 1\) 。
- 任意 \((x, y)\) 位置满足 \(x > i\) 的格子翻转，满足 \(x - i \geq |y - j|\) 的格子翻转。
解方程：
不要被笛卡尔坐标系给荼毒了……。
在所给坐标系中是垂直向下九十度的扇形。
考虑：
- \(01\) 翻转最 \(naive\) 的性质：一个位置翻转 \(n\) 次，只有其中的 \(n\&1\) 次是有意义的。
- 网格内操作某个格子带动翻转一个区域且“翻转形式唯一或能转化为翻转形式唯一”的情形，具备一些性质：（只有区域翻转形式唯一情况下才能直接进行数理讨论，否则考虑 \(DP\) 等方案）
- 任何方向有后效性的翻转：当边界行（通常选第一行）的状态确定，整个方格的状态唯一确定。可以知晓有无解，有解时的最小操作次数。
- 证明：当边界行状态确定，由于后效性存在，不存在一种方案可以维持已确定的边界行的状态且改变其他行。
- 推论：当边界格的状态唯一确定，整行的状态唯一确定。
- 存在或可转化为一个方向无后效性的翻转：贪心地选择无后效性的方向翻转一定有解，当方向唯一时最小操作次数唯一。（比如此题的格子翻转严格影响向下的区域）
- 证明：有解性显然。最优性可以反证按其他方向翻转不会更优。
- 任何方向有后效性的翻转：当边界行（通常选第一行）的状态确定，整个方格的状态唯一确定。可以知晓有无解，有解时的最小操作次数。
于是此题变为，如何在 \(O(n^2)\) 或者 \(O(n^2 \log n)\) 的复杂度内，完成从第 \(1\) 行到第 \(n\) 行逐行操作所有 \(1\) 的格子。
- 仅按从上到下的方向操作所有 \(1\) 便是 \(O(n^2)\) 的，所以操作复杂度需要是 \(O(1)\) 或 \(O(\log n)\) 。
- 于是面临两个问题：
- 空间允许情况下容易想到二维区间修改，很像需同时修改和询问。
- 差分空间非水平，而是斜率为 \(1\) 和 \(-1\) 的空间。
这调用 \(fenwik\ tree\) 将会是一套繁杂的推式子和代码实现。
- 向下斜率为正负 \(1\) 的区间修改问题，是经典的 \(tag\) 下放问题。
- 我们只需要在 \(\mod 2\) 意义即位异或意义下，下放 \(tag\) 合并更新即可。
- 三叉树中 \(tag\) 的下放比二叉树中 \(tag\) 的下放区别：
- 二叉树的 \(tag\) 压标记时直接压到左右儿子即可，常见于二叉搜索树的 \(lazy\ tag\) 。
- 三叉树的 \(tag\) 压标记时也只把标记压到左右儿子.若左右儿子都存在，则给中孙子放一个负标记（如果它存在）。更新信息时不仅要加上自己的标记，还要加上父亲的标记。
（待补图） - 三叉树更常见于如网格中这种具备垂直关系的结构中应用。
时间复杂度 \(O(n^2)\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve() {
int n; std::cin >> n;
std::vector<std::vector<int> > a(n+1, std::vector<int>(n+1)), tag(n+1, std::vector<int>(n+1));
for (int i = 1; i <= n; i++) {
std::string s; std::cin >> s;
for (int j = 1; j <= n; j++) {
a[i][j] = (s[j - 1] - '0');
}
}
auto settag = [&](int i, int j, int v) {
tag[i][j] = ( tag[i][j] + v ) % 2;
};
auto pushdown = [&](int i, int j) {
if (i + 1 <= n) { // 下一层存在
a[i + 1][j] = ( a[i + 1][j] + tag[i][j] ) % 2; // 更新中儿子信息
if (j - 1 >= 1) { // 标记压到左儿子，更新左右子信息
tag[i + 1][j - 1] = ( tag[i + 1][j - 1] + tag[i][j] ) % 2;
a[i + 1][j - 1] = ( a[i + 1][j - 1] + tag[i][j] ) % 2;
}
if (j + 1 <= n) { // 标记压到右儿子，更新右儿子信息
tag[i + 1][j + 1] = ( tag[i + 1][j + 1] + tag[i][j] ) % 2;
a[i + 1][j + 1] = ( a[i + 1][j + 1] + tag[i][j] ) % 2;
}
}
if (i + 2 <= n && j - 1 >= 1 && j + 1 <= n) { // 中孙子在存在且左右儿子都存在则打上负标记
tag[i + 2][j] = ( tag[i + 2][j] - tag[i][j] + 2 ) % 2;
a[i + 2][j] = ( a[i + 2][j] - tag[i][j] + 2 ) % 2;
}
tag[i][j] = 0; // 压完标记清空
};
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j]) ans++, settag(i, j, 1);
pushdown(i, j);
}
}
std::cout << ans << '\n';
}
int main() {
int _ = 1; std::cin >> _;
while ( _-- ) { solve(); }
return 0;
}