A. Least Product
假如序列中有 \(0\)，那么答案是 \(0\)。
否则如果有奇数个负数，只需要让每个数的绝对值最大：不操作是最优的。
否则如果有偶数个负数，乘积只会 \(\ge 0\)，为了达到最小值 \(0\)，只需要将任意一个数改成 \(0\)。
时间复杂度 \(\mathcal{O}(n)\)。
code for A
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, A[N];
inline void solve() {
cin >> n;
for(int i = 1; i <= n; i ++) cin >> A[i];
for(int i = 1; i <= n; i ++)
if(A[i] == 0) {
cout << "0" << '\n';
return;
}
int cnt = 0;
for(int i = 1; i <= n; i ++)
cnt += (A[i] < 0);
if(cnt % 2 == 0) {
cout << "1" << '\n';
cout << "1 0" << '\n';
} else {
cout << "0" << '\n';
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
B. Erase First or Second Letter
最终序列会变成XcXS的形状，其中X是被删掉的一段连续子串，S是被留下来的一段连续子串，c是一个字符，X和S都可以为空。
枚举那个后缀S，看前面有多少种字符即可。
code for B
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n; char S[N];
inline void solve() {
int n; cin >> n >> (S + 1);
set<char> Set; int ans = n;
Set.insert(S[1]);
for(int i = 3; i <= n; i ++) {
ans += Set.size();
if(Set.count(S[i - 1])) ans --;
Set.insert(S[i - 1]);
}
Set.insert(S[n]), ans += Set.size() - 1; // S 为空串
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
C. Watering an Array
当序列全变为 \(0\) 之后，由于每次加的是一个前缀，所以最多只会有一个 \(i\) 满足 \(a_i = i\)，因此最优方案就是加一次让 \(a_1=1\)，紧跟着将序列清零，贡献加一，答案为 \(\lfloor \frac{c}{2} \rfloor\)，其中 \(c\) 为操作次数。
但是最开始序列不全为 \(0\)，但是我们可以枚举它加了多少次后变成全 \(0\)，一个暴力的想法是 \(nk\) 次，因为这之后，每个 \(a_i\) 要么就是不能通过 \(b\) 变化，要么就是再加就会 \(>a_i\) 了。
直接暴力加是 \(\mathcal{O}(n^2k)\) 的，肯定过不了，但是我们可以用一个小根堆维护当前满足 \(a_i < i\) 的下标 \(i\) 和 \(a_i = i\) 的下标 \(i\)，每次取出某些堆顶再放回去（或者不放回），每个下标只会出队、入队 \(\mathcal{O}(n)\) 次，复杂度是 \(\mathcal{O}(nk + n^2 \log n)\) 的，可以通过。
一个更聪明的做法是，最开始加的次数不会超过 \(2n\)，这是因为若加的次数超过 \(2n\)，这些操作最终的贡献也不会超过 \(n\)（只有 \(n\) 个数），但是我们可以在一开始就把序列清 \(0\)，然后用 \(2n\) 次操作获得相同的贡献。每次暴力做前缀加法，统计 \(a_i=i\) 的数量，时间复杂度 \(\mathcal{O}(n^2)\)。
code for C
#include <bits/stdc++.h>
using namespace std;
const int N = 2010, K = 1e5 + 10;
int n, k, d;
long long a[N], v[K];
inline void solve() {
cin >> n >> k >> d;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= k; i ++) cin >> v[i];
int cnt = 0;
for(int i = 1; i <= n; i ++)
cnt += a[i] == i;
long long ans = cnt + (d - 1) / 2;
for(int i = 1, op = 1; i < min(d, 2 * n + 1); i ++, op ++) {
if(op == k + 1) op = 1;
for(int j = 1; j <= v[op]; j ++) a[j] ++;
cnt = 0;
for(int j = 1; j <= n; j ++) cnt += a[j] == j;
ans = max(ans, 1ll * cnt + (d - i - 1) / 2);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
D. Yet Another Inversions Problem
将整个序列分为 \(n\) 块，每块 \(k\) 个元素。块内之间的逆序对数量为 \(q\) 的逆序对数量的 \(n\) 倍，这是因为每块内部的 \(p\) 都一样。写一个树状数组统计 \(q\) 的逆序数即可。
对于不同块元素之间的逆序对数量，从左到右枚举每个块，将 \(p_i2^{q_i} > p_j2^{q_j}\) 重写为 \(p_i2^{q_i-q_j} > p_j\)。枚举 \(\delta = q_i-q_j\)，算出右边的块有多少个的 \(p\) 小于这个东西。
注意到指数的增长速度，因此当 \(\delta < -20\) 的时候不等式必然不成立，当 \(\delta > 20\) 的时候等式必然成立，因此只需要枚举 \(\delta \in [-20,20]\) 即可，是 \(\mathcal{O}(\log w)\) 级别的，再加上一个树状数组维护后面的 \(p_i\)，是 \(\log^2\) 的。
单组数据的时间复杂度为 \(\mathcal{O}(k \log k + n \log^2 w)\)。
code for D
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10, MOD = 998244353;
inline int Plus(int a, int b) {return a + b >= MOD ? a + b - MOD : a + b; }
inline int Minus(int a, int b) {return a - b < 0 ? a - b + MOD : a - b; }
int n, k, P[N], Q[N];
struct Fenwick {
int C[N];
inline void Add(int p, int x) {while(p < N) C[p] += x, p += p & -p; }
inline int Ask(int p) {int r = 0; while(p) r += C[p], p -= p & -p; return r; }
inline void clear(int n) {
for(int i = 0; i <= n; i ++)
C[i] = 0;
}
} BIT;
inline void solve() {
cin >> n >> k;
for(int i = 1; i <= n; i ++) cin >> P[i];
for(int i = 1; i <= k; i ++) cin >> Q[i];
BIT.clear(k + 1);
long long ans = 0;
for(int i = k; i >= 1; i --) {
ans += BIT.Ask(Q[i]);
BIT.Add(Q[i] + 1, 1);
}
ans = ans % MOD * n % MOD;
long long all = (k) * (k + 1ll) / 2;
for(int i = 0; i < min(21, k); i ++)
all -= (k - i);
all %= MOD;
BIT.clear(2 * n + 1);
for(int i = n; i >= 1; i --) {
for(int d = -min(k - 1, 20); d < min(k, 21); d ++) {
long long val;
if(d < 0) val = 1ll * P[i] >> (-d);
else val = (1ll * P[i] << d) - 1;
if(val <= 0) continue;
val = min(val, 2ll * n);
ans = Plus(ans, 1ll * BIT.Ask(val) * (k - abs(d)) % MOD);
}
ans = Plus(ans, BIT.Ask(2 * n) * all % MOD);
BIT.Add(P[i], 1);
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
E. Construct Matrix
有趣构造。
首先 \(k\) 为奇数的时候一定无解，这是因为每一行的1的个数的奇偶性相同而一共有偶数行，然后特判 \(n=2\) 的情况。
当 \(k \equiv 0 \pmod 4\) 的时候，我们可以每次将一个 \(2 \times 2\) 的全0矩阵全部变成1，每行、列的奇偶性不变。
当 \(k \equiv 2 \pmod 4\) 的时候，可以构造如下含有 \(6\) 个1的方案到左上角的 \(4 \times 4\) 的子矩阵中（\(n=2\) 的情况已经特判掉了）：
1 1 0 0
1 0 1 0
0 1 1 0
0 0 0 0
若 \(k=2\)，无解，否则将左上角填上这 \(6\) 个1后接着往别的地方填 \(2 \times 2\) 的全1矩阵即可。
但是注意到此时 \(k \le n^2-10\)，还有 \(k = n^2-6,n^2-2\) 的情况没有考虑（左上角浪费了 \(10\) 个位置）。
\(k=n^2-2\) 和 \(k=2\) 本质相同，无解。
对于 \(k=n^2-6\) 的情况，可以将左上角的0和1反转得到
0 0 1 1
0 1 0 1
1 0 0 1
1 1 1 1
剩下的位置填1就构造完成了，单组询问的时间复杂度为 \(\mathcal{O}(n^2)\)。
code for E
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, k, A[N][N];
inline void solve() {
cin >> n >> k;
if(k % 2 == 1) {
cout << "No" << '\n';
return;
}
if(n == 2) {
cout << "Yes" << '\n';
if(k == 0) cout << "0 0\n0 0\n";
else if(k == 2) cout << "0 1\n1 0\n";
else cout << "1 1\n1 1\n";
return;
}
if(k % 4 == 0) {
cout << "Yes" << '\n';
for(int i = 1; i <= n; i += 2) {
for(int j = 1; j <= n; j ++) {
if(k) A[i][j] = 1, k -= 2;
else A[i][j] = 0;
}
for(int j = 1; j <= n; j ++)
A[i + 1][j] = A[i][j];
}
} else {
if(k == 2 || k == n * n - 2) {cout << "No" << '\n'; return; }
cout << "Yes" << '\n';
if(k == n * n - 6) {
A[1][1] = 0, A[1][2] = 0, A[1][3] = 1, A[1][4] = 1;
A[2][1] = 0, A[2][2] = 1, A[2][3] = 0, A[2][4] = 1;
A[3][1] = 1, A[3][2] = 0, A[3][3] = 0, A[3][4] = 1;
A[4][1] = 1, A[4][2] = 1, A[4][3] = 1, A[4][4] = 1;
k -= 10;
} else {
A[1][1] = 1, A[1][2] = 1, A[1][3] = 0, A[1][4] = 0;
A[2][1] = 1, A[2][2] = 0, A[2][3] = 1, A[2][4] = 0;
A[3][1] = 0, A[3][2] = 1, A[3][3] = 1, A[3][4] = 0;
A[4][1] = 0, A[4][2] = 0, A[4][3] = 0, A[4][4] = 0;
k -= 6;
}
for(int i = 1; i <= n; i += 2) {
for(int j = 1; j <= n; j ++) if(i > 4 || j > 4) {
if(k) A[i][j] = 1, k -= 2;
else A[i][j] = 0;
}
for(int j = 1; j <= n; j ++)
if(i > 4 || j > 4) A[i + 1][j] = A[i][j];
}
}
assert(k == 0);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
cout << A[i][j] << " \n"[j == n];
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) solve();
return 0;
}
F. Construct Tree
考虑长度最大的那条边，设长度为 \(L\)，那么如果 \(L > \lfloor \frac{d}{2} \rfloor\)，\(L\) 就必然在直径上。
证明考虑若它不在直径上，那么我们总可以将这条边取代直径的某一侧获得更大的直径。
之后，既然它在直径上，那么直径就会成为一条长 \(L\) 的边拼上一条长 \(d-L\) 的路径，若存在另外一条长度为 \(L'\) 的边使得 \(L'>d-L\)，一定无解，证明同上。既然所有边的长度都不超过 \(d-L \le L\)了，那么不在直径上的边总是可以找到一个合法位置的（挂在 \(L\) 与 \(d-L\) 的交界处），于是只需要做一个背包判断剩下的长度能不能拼出 \(d-L\) 即可，时间复杂度 \(\mathcal{O}(nd)\)。
否则 \(L \le \lfloor \frac{d}{2} \rfloor\)，同样考虑这条边 \(L\)，如果它可以在直径上，那么所有其它没有在直径上的边也就可以得到一个合法的位置，判断这个只需要和之前 \(L > \lfloor \frac{d}{2} \rfloor\) 一样，判断剩下的边是否可以拼出 \(d-L\) 即可。
否则它不在直径上，删掉它，设 \(dp_{i,j,k}\) 表示前 \(i\) 条边是否可以拼出一段长为 \(j\) 的路径和一段长为 \(k\) 的路径，值只有 \(0\) 和 \(1\)，可以用std::bitset 优化至 \(\frac{nd^2}{w}\)。之后只需要看是否存在一组 \(j,k\) 满足 \(\min(j,k) \ge L\) 并且 \(j,k\) 可以被拼出即可。
单组数据的时间复杂度为 \(\mathcal{O}\left(\frac{nd^2}{w}\right)\)。
code for F
#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, d, L[N];
inline bool check(int n, int d) {
static bitset<2001> f; f.reset();
f[0] = 1;
for(int i = 1; i <= n && !f[d]; i ++)
f = f | (f << L[i]);
return f[d];
}
inline bool BackPack() {
static bitset<2001> f[2][2001];
for(int i = 0; i <= d; i ++) f[0][i].reset();
f[0][0] = 1; int cur = 0;
for(int i = 1; i < n; i ++) {
cur ^= 1;
for(int j = 0; j <= d; j ++)
f[cur][j] = f[cur ^ 1][j] | (f[cur ^ 1][j] << L[i]);
for(int j = L[i]; j <= d; j ++)
f[cur][j] = f[cur][j] | f[cur ^ 1][j - L[i]];
}
for(int i = L[n]; i <= d - L[n]; i ++)
if(f[cur][i][d - i]) return true;
return false;
}
inline string solve() {
cin >> n >> d;
for(int i = 1; i <= n; i ++) cin >> L[i];
sort(L + 1, L + n + 1);
if(L[n] > (d >> 1)) {
if(L[n - 1] > d - L[n]) return "No";
return check(n - 1, d - L[n]) ? "Yes" : "No";
} else {
if(check(n - 1, d - L[n])) return "Yes";
return BackPack() ? "Yes" : "No";
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int T; cin >> T;
while(T --) cout << solve() << '\n';
return 0;
}