InfOJ NOIP2023 模拟赛
T1
给定长度为 \(n\) 的数列 \(a\)，每次操作需要选择 \([l, r]\)，满足 \(a_l, a_{l + 1}, \cdots, a_r\) 按位与的结果为 \(0\)，然后删去 \([l, r]\)，删去后左边和右边合并起来。
问最多能合并多少次。
\(n \le 63, a_i \le 63\)。
简单区间 dp。
设 \(f_{l, r, x}\) 为区间 \([l, r]\) 经过若干次删除操作之后，剩下的数字按位与结果为 \(x\)，最多的删除次数。
转移就枚举中转点 \(m\)，\(f_{l, m, x} + f_{m + 1, r, y} \to f_{l, r, x \& y}\)。当 \(x \& y = 0\) 时，也能转移 \(f_{l, m, x} + f_{m + 1, r, y} + 1 \to f_{l, r, 63}\)，即将剩下的数字作为一次操作删去，然后没有剩下的数字了， 按位与设为 \(63\)。
时间复杂度 \(O(n ^ 2 V ^ 3)\)，\(V\) 是值域。
Code of T1
#include <bits/stdc++.h>
const int M = 70;
const int inf = 1e9 + 7;
int f[M][M][M];
int n, a[M];
int main() {
double st = clock();
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++)
for (int k = 0; k < M; k++) f[i][j][k] = -inf;
for (int i = 1; i <= n; i++)
if (a[i] == 0) f[i][i][63] = 1;
else f[i][i][a[i]] = 0;
for (int len = 2; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int m = l; m <= r; m++) {
for (int x = 0; x < 64; x++)
if (f[l][m][x] != -inf)
for (int y = 0; y < 64; y++)
if (f[m + 1][r][y] != -inf) {
f[l][r][x & y] = std::max(f[l][r][x & y], f[l][m][x] + f[m + 1][r][y]);
if ((x & y) == 0) f[l][r][63] = std::max(f[l][r][63], f[l][m][x] + f[m + 1][r][y] + 1);
}
}
int sum = a[l];
for (int i = l + 1; i <= r; i++) sum &= a[i];
f[l][r][sum] = std::max(f[l][r][sum], 0);
if (sum == 0) f[l][r][63] = std::max(f[l][r][63], 1);
}
}
int ans = 0;
for (int l = 1; l <= n; l++)
for (int r = l; r <= n; r++)
for (int x = 0; x < 64; x++) ans = std::max(ans, f[l][r][x]);
printf("%d\n", ans);
double ed = clock();
std::cerr << (int)(ed - st) << '\n';
return 0;
}
T2
定义一个长度为 \(n\) 的数组 \(h\) 的不优美度为 $ h_1 + h_n + \sum\limits_{i = 1} ^ {n - 1} |h_i - h_{i + 1}|$。
给定数组 \(h\)，\(Q\) 次询问，若有 \(X\) 次机会让某一个 \(h_i > 0\) 执行 \(h_i \gets h_i - 1\)，最小的不优美度是多少。
\(n, Q \le 10 ^ 5, a_i \le 10 ^ {12}, X \le 10 ^ {18}\)。
令 \(h_0 = h_{n + 1} = 0\)，那么不优美度就是相邻两项的绝对值的差之和。
考虑如何减小不优美度。容易发现当 \(h_i > h_{i - 1} \land h_i > h_{i + 1}\) 时，执行 \(h_i \gets h_i - 1\) 会对不优美度造成 \(-2\) 的贡献。
进一步地，如果有 \([L, R]\) 满足 \(h_{L - 1} < h_L = h_{L + 1} = \cdots = h_R > h_{R + 1}\)，那么对 \([L, R]\) 全部操作一遍，也有 \(-2\) 的贡献。容易发现只有这样会造成负的贡献。贪心地每次找到最短的满足上述条件的 \([L, R]\) 即可，用堆维护。
但是每次只对 \([L, R]\) 做一遍显然是不够的。注意到在 \(h_{L - 1} = h_L\) 或者 \(h_{R + 1} = h_R\) 之前，\([L, R]\) 仍然是最短的，所以可以直接做 \(\min(h_L - h_{L - 1}, h_R - h_{R + 1})\) 遍。然后向左右两边将 \(h\) 相同的合并成新的一段 \([L', R']\)。如果有 \(h_{L' - 1} < h_{L'} = h_{L' + 1} = \cdots = h_{R'} > h_{R' + 1}\) 那么将 \([L', R']\) 丢进堆里即可。
将询问的 \(X\) 排序，维护当前操作了 \(tot\) 次，以及操作过后的不优美值 \(sum\)。假如现在对 \([L, R]\) 进行 \(h\) 遍操作，那么对于 \(X \in [tot + 1, tot + (R - L + 1)h]\)，答案是 \(sum - 2 \left\lfloor \frac{X - tot}{R - L + 1} \right\rfloor\)。
因为有 \(n\) 个不同的 \(h\)，所以总共需要向左右合并 \(n\) 次。每个 \(h\) 只会被合并一次，时间复杂度 \(O(n \log n)\)。
Code of T2
#include <bits/stdc++.h>
using namespace std;
const int M = 5e5 + 10;
template<typename T>
inline T read() {
char ch = getchar();
T x = 0;
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
return x;
}
int n, q;
long long a[M];
pair<long long, int> x[M];
struct Node {
int l, r;
long long hgt;
bool operator > (const Node& o) const {
return r - l > o.r - o.l;
}
};
priority_queue<Node, vector<Node>, greater<Node> > Q;
struct BIT {
long long c[M];
void add(int x, long long v) {
for (; x <= n + 1; x += (x & -x)) c[x] += v;
}
void add(int l, int r, long long v) {
add(l, v), add(r + 1, -v);
}
long long operator[](int x) {
if (x < 1 || x > n) return 0;
long long ret = 0;
for (; x; x -= (x & -x)) ret += c[x];
return ret;
}
}h;
int L[M], R[M];
long long ans[M];
void Insert() {
for (int i = 1; i <= n; ) {
int cur = i;
while (cur < n && a[cur] == a[cur + 1]) cur++;
R[i] = cur, L[cur] = i;
if (a[cur] > a[cur + 1] && a[i] > a[i - 1]) Q.push({ i, cur, a[cur] });
i = cur + 1;
}
}
int main() {
double st = clock();
n = read<int>(), q = read<int>();
for (int i = 1; i <= n; i++) a[i] = read<long long>();
for (int i = 1; i <= q; i++) x[i].first = read<long long>(), x[i].second = i;
sort(x + 1, x + 1 + q);
long long sum = a[1] + a[n];
for (int i = 1; i < n; i++) sum += abs(a[i] - a[i + 1]);
for (int i = 1; i <= n; i++) h.add(i, a[i] - a[i - 1]);
Insert();
int curq = 0;
long long tot = 0;
while (x[curq + 1].first == 0 && curq < q) ans[x[++curq].second] = sum;
while (!Q.empty()) {
Node tp = Q.top(); Q.pop();
int len = tp.r - tp.l + 1;
long long hgt = std::max(h[tp.l - 1], h[tp.r + 1]);
long long size = (tp.hgt - hgt) * len;
h.add(tp.l, tp.r, hgt - tp.hgt);
while (curq < q && tot < x[curq + 1].first && x[curq + 1].first <= tot + size) {
curq++;
long long res = (x[curq].first - tot) / len;
ans[x[curq].second] = sum - res * 2;
}
tot += size, sum -= (tp.hgt - hgt) * 2;
int newL = tp.l, newR = tp.r;
if (tp.l > 1 && h[tp.l - 1] == hgt) newL = L[tp.l - 1];
if (tp.r < n && h[tp.r + 1] == hgt) newR = R[tp.r + 1];
R[newL] = newR, L[newR] = newL;
if (h[newL - 1] < hgt && h[newR + 1] < hgt) Q.push({ newL, newR, hgt });
}
while (curq < q) ans[x[++curq].second] = 0;
for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
double ed = clock();
std::cerr << (int)(ed - st) << '\n';
return 0;
}
T3
给定 \(n\) 个点的树，结点 \(1\) 为根。要用 \(m\) 种颜色对每个结点染色。每个结点有一个参数 \(f_u\) 表示 \(u\) 的子树恰好出现了 \(f_u\) 种颜色。如果 \(f_u = -1\) 说明不限制子树颜色个数。问染色方案数。
\(m \le n \le 1.5 \times 10 ^ 5\)。保证 \(f_1 = m\)。
考虑二项式反演。
设 \(F(u, x)\) 为 \(u\) 的子树种恰好出现 \(x\) 种颜色的方案数，\(G(u, x)\) 为 \(u\) 的子树种至多用 \(x\) 种颜色的方案数。那么 \(F(u, f_u) = \sum\limits_{i = 0} ^ {f_u} (-1) ^ {f_u - i} \binom{f_u}{i} G(u, i)\)。
根据 \(G\) 的定义，显然有 \(G(u, i) = \prod\limits_{v \in son_u \land f_v \ne -1} \binom{i}{f_v} F(v, f_v) \prod\limits_{v \in son_u \land f_v = -1} G(v, i)\)。这样是 \(O(nm)\) 的。
\(O(n \sqrt{n})\) 的正解不会，鸽了。
Code of T3
#include <bits/stdc++.h>
const int M = 2e5 + 10;
const int mod = 1e9 + 7;
int n, m, col[M];
std::vector<int> t[M];
int fac[M], facinv[M];
void calc() {
fac[0] = fac[1] = facinv[0] = facinv[1] = 1;
for (int i = 2; i < M; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
for (int i = 2; i < M; i++) facinv[i] = 1ll * (mod - mod / i) * facinv[mod % i] % mod;
for (int i = 2; i < M; i++) facinv[i] = 1ll * facinv[i - 1] * facinv[i] % mod;
}
int C(int x, int y) {
if (x < y || x < 0 || y < 0) return 0;
return 1ll * fac[x] * facinv[y] % mod * facinv[x - y] % mod;
}
int siz[M], fa[M];
void dfs(int u, int f) {
siz[u] = 1, fa[u] = f;
for (int v : t[u]) {
if (v == f) continue;
dfs(v, u), siz[u] += siz[v];
}
}
namespace Sub1 {
int f[M], g[M][110];
void dp(int u) {
for (int i = 1; i <= m; i++) g[u][i] = i;
for (int v : t[u]) {
if (v == fa[u]) continue;
dp(v);
for (int i = 0; i <= m; i++)
if (col[v] != -1)
g[u][i] = 1ll * g[u][i] * f[v] % mod * C(i, col[v]) % mod;
else
g[u][i] = 1ll * g[u][i] * g[v][i] % mod;
}
for (int i = 0; i <= col[u]; i++) {
if ((col[u] - i) & 1)
(f[u] += mod - 1ll * C(col[u], i) * g[u][i] % mod) %= mod;
else
(f[u] += 1ll * C(col[u], i) * g[u][i] % mod) %= mod;
}
//printf("f[%d] = %d\n", u, f[u]);
}
void main() {
dp(1);
printf("%d\n", f[1]);
}
}
int main() {
calc();
scanf("%d%d", &n, &m);
for (int i = 2, fa; i <= n; i++)
scanf("%d", &fa), t[fa].push_back(i);
dfs(1, 0);
bool A = true;
for (int i = 1; i <= n; i++)
scanf("%d", &col[i]), A &= (col[i] != -1);
Sub1::main();
return 0;
}
T4
给定长度为 \(n\) 的序列 \(a\)，有两种可执行的操作。
有 \(m\) 种形如 \(X_i, L_i, R_i, W_i\) 的操作，表示将 \(a_{X_i}\) 减一，将 \(a_{L_i}, a_{L_i + 1}, \cdots, a_{R_i}\) 加一，代价是 \(W_i\)。
有 \(n\) 种形如 \(b_i\) 的操作，表示将 \(a_i\) 减一，代价是 \(b_i\)。若 \(b_i = -1\) 代表这个操作不可用。
问将 \(a\) 中所有元素变成 \(0\) 的最小代价。
\(n, m \le 4 \times 10 ^ 5\)。
先考虑一种特殊情况：只有 \(a_i = 1\)，其余都为 \(0\)。
这时有两种选择，一种是直接使用 \(b_i\)，一种是使用 \(X_j = i\) 的 \(X_j, L_j, R_j, W_j\)，转化为只有 \([L_j, R_j]\) 为 \(1\)，其余都为 \(0\) 的情况。而这样又是 \(R_j - L_j + 1\) 个子问题。
令 \(f_i\) 为只有 \(a_i = 1\) 其余都为 \(0\) 的情形的答案，初始是 \(f_i = b_i\)。当 \(X_j = i\) 且 \(f_{L_j}, f_{L_j + 1}, \cdots, f_{R_j}\) 都求出来的时候 \(f_i \gets \min(f_i, W_j + \sum\limits_{k = L_j} ^ {R_j} f_k)\)。这个可以用类似 Dijkstra 的方式求，每次取出最小的 \(f_i\) 去更新其它的。对于 \(f_{L_j}, f_{L_j + 1}, \cdots, f_{R_j}\) 是否都求出来，可以用线段树将一个 \([L, R]\) 拆成 \(O(\log n)\) 个区间，维护每个区间中有多少个 \(f_i\) 被求出。
最后答案就是 \(\sum\limits_{i = 1} ^ n a_i f_i\)。时间复杂度 \(O(n \log n)\)。
Code of T4
#include <bits/stdc++.h>
const int M = 4e5 + 10;
const long long inf = 2e18 + 10;
int n, m, a[M], b[M];
int X[M], L[M], R[M], W[M];
int d[M];
int cnt[M << 2];
long long sum[M << 2];
std::vector<int> vec[M << 2];
void Insert(int k, int l, int r, int L, int R, int x) {
if (L <= l && r <= R) {
vec[k].push_back(x), d[x]++;
return;
}
int mid = (l + r) >> 1;
if (L <= mid) Insert(k << 1, l, mid, L, R, x);
if (R > mid) Insert(k << 1 | 1, mid + 1, r, L, R, x);
}
std::priority_queue<std::pair<long long, int>,
std::vector<std::pair<long long, int> >, std::greater<std::pair<long long, int> > > q;
long long cost[M], dis[M];
bool vis[M];
void Modify(int k, int l, int r, int p, long long v) {
cnt[k]++, sum[k] += v;
if (cnt[k] == r - l + 1)
for (int x : vec[k]) {
cost[x] += sum[k];
if (!(--d[x]))
if (dis[X[x]] > cost[x] + W[x]) {
dis[X[x]] = cost[x] + W[x];
if (!vis[X[x]]) q.push({ dis[X[x]], X[x] });
}
}
if (l == r) return;
int mid = (l + r) >> 1;
if (p <= mid) Modify(k << 1, l, mid, p, v);
else Modify(k << 1 | 1, mid + 1, r, p, v);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= m; i++) {
scanf("%d%d%d%d", &X[i], &L[i], &R[i], &W[i]);
Insert(1, 1, n, L[i], R[i], i);
}
for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
for (int i = 1; i <= n; i++) dis[i] = (b[i] == -1) ? inf : b[i];
for (int i = 1; i <= n; i++)
if (b[i] != -1) q.push({ b[i], i });
while (!q.empty()) {
auto tp = q.top(); q.pop();
if (vis[tp.second]) continue;
vis[tp.second] = true;
Modify(1, 1, n, tp.second, dis[tp.second]);
}
for (int i = 1; i <= n; i++)
if (dis[i] >= inf && a[i] > 0) return printf("-1\n"), 0;
long long ans = 0;
for (int i = 1; i <= n; i++) ans += dis[i] * a[i];
printf("%lld\n", ans);
return 0;
}