A. Brick Wall
因为水平砖块的长度至少为 \(2\)，所以一行中水平砖块最多放 \(\lfloor \frac{m}{2} \rfloor\) 块，因此答案不超过 \(n \cdot \lfloor \frac{m}{2} \rfloor\)。如果 \(m\) 是奇数，用长度为 \(\lfloor \frac{m}{2} \rfloor\) 的水平砖块平铺过去，最后一块长度为 \(3\)，这样也没有垂直砖块。因此最大稳定性就是 \(n \cdot \lfloor \frac{m}{2} \rfloor\)。
参考代码
#include <cstdio>
int main()
{
int t; scanf("%d", &t);
while (t--) {
int n, m; scanf("%d%d", &n, &m);
printf("%d\n", m / 2 * n);
}
return 0;
}
B. Minimize Inversions
注意对 \(a_i\) 和 \(a_j\)、\(b_i\) 和 \(b_j\) 的操作是同时进行的，不妨假设我们随意调整 \(a\) 的顺序，则原来的每一对 \(a_i\) 和 \(b_i\) 的匹配关系是不变的。令 \(a\) 变得有序，即没有逆序对，这样的状态是逆序对总数最少的状态。
证明：考虑两对元素 \(a_i\) 和 \(a_j\)、\(b_i\) 和 \(b_j \ (i<j)\)。这样数对中每一对的逆序对数可能为 \(0\) 或 \(1\)，所以对于两个数对而言，逆序对数可能为 \(0\) 或 \(1\) 或 \(2\)。如果操作前是 \(0\) 对逆序对，那么操作后会变成 \(2\) 对；如果本来是 \(1\) 对，操作后还是 \(1\) 对；如果操作前是 \(2\) 对，操作后是 \(0\) 对。如果将 \(a\) 排成有序，则每一对下标 \(i\) 和 \(j\) 对应的两个数对最多产生 \(1\) 个逆序对，这时不可能通过交换操作将逆序对数再减少了，所以这就是逆序对数量最少的情况。
时间复杂度为 \(O(n)\)。
参考代码
#include <cstdio>
const int N = 200005;
int idx[N], b[N];
int main()
{
int t; scanf("%d", &t);
while (t--) {
int n; scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int x; scanf("%d", &x); idx[x] = i;
}
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
for (int i = 1; i <= n; i++) printf("%d%c", i, i == n ? '\n' : ' ');
for (int i = 1; i <= n; i++) printf("%d%c", b[idx[i]], i == n ? '\n' : ' ');
}
return 0;
}
C. XOR-distance
考虑 \(a,b,x\) 的二进制表示。分析 \(a\) 和 \(b\) 中同一个位置上的两个二进制位，如果是相等的，则无论 \(x\) 在这一位上取什么值，\(|(a⊕x)−(b⊕x)|\) 在这一位上的贡献必然为 \(0\)。因此 \(x\) 在这一位上应该选 \(0\)，因为我们希望 \(x \le r\)，所以既然取值无所谓，则应尽量节省。
不妨设 \(a > b\)，则存在第一个（最高）位，那一位上 \(a\) 对应的值为 \(1\)，\(b\) 对应的值为 \(0\)，考虑对于除了这一位以外的之后每一个这样的位，在 \(x\) 的这一位还有机会取 \(1\) 时（即这一位置 \(1\) 后仍小于等于 \(r\)）令其取 \(1\)，这样一来 \(a \oplus x\) 在这一位上会变成 \(0\)，而 \(b \oplus x\) 在这一位上会变成 \(1\)，这样能够使得 \(|(a⊕x)−(b⊕x)|\) 的差值尽可能小。
参考代码
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int LOG = 60;
int main()
{
int t; scanf("%d", &t);
while (t--) {
LL a, b, r, x = 0; scanf("%lld%lld%lld", &a, &b, &r);
if (a < b) swap(a, b);
bool high = true;
for (int i = LOG - 1; i >= 0; i--) {
int ai = (a >> i) & 1, bi = (b >> i) & 1;
if (ai == 1 && bi == 0) {
if (!high && r >= 1ll << i) {
x += 1ll << i; r -= 1ll << i;
}
high = false;
}
}
printf("%lld\n", abs((a ^ x) - (b ^ x)));
}
return 0;
}
D. Blocking Elements
考虑二分答案。因为尝试的分隔代价限定得越小，就越难实现，限定得越大则越有可能实现，满足单调性。
当尝试的分隔代价限定为 \(x\) 时，设 \(dp_i\) 表示前 \(i\) 个数，以第 \(i\) 个数作为分隔元素时，在保证每一段的元素和不超过 \(x\) 的情况下，所有的分隔元素之和的最小值，于是 \(dp_i = \min \{ dp_j \} + a_i\)，其中 \(j\) 是每一个保证 \([j+1,i-1]\) 的区间和不超过 \(m\) 的位置。由于 \(a_j\) 保证非负，这样的 \(j\) 的取值范围一定是一个连续区间，也就是一个滑动窗口，这个窗口会随着 \(i\) 的右移而右移。因此，这个 \(dp\) 的计算过程可以用单调队列来优化。
时间复杂度为 \(O(n \log \sum a_i)\)。
参考代码
#include <cstdio>
#include <deque>
using namespace std;
typedef long long LL;
const int N = 100005;
int a[N], n;
LL dp[N], sum[N];
bool check(LL x) {
deque<int> dq; dq.push_back(0);
int idx = 0;
for (int i = 1; i <= n + 1; i++) {
while (idx <= i && sum[i - 1] - sum[idx] > x) idx++;
while (!dq.empty() && dq.front() < idx) dq.pop_front();
dp[i] = dp[dq.front()] + a[i];
while (!dq.empty() && dp[dq.back()] >= dp[i]) dq.pop_back();
dq.push_back(i);
}
return dp[n + 1] <= x;
}
int main()
{
int t; scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]); sum[i] = sum[i - 1] + a[i];
}
a[n + 1] = 0; sum[n + 1] = sum[n];
LL ans, l = 1, r = sum[n];
while (l <= r) {
LL mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1; ans = mid;
} else l = mid + 1;
}
printf("%lld\n", ans);
}
return 0;
}