2024.10.12 模拟赛
T1 delete
简要题意
给定长度为 \(n\) 的数列 \(a_i\)，每次操作需要选择 \([l,r]\)，满足 \(a_l,a_{l+1},...a_{r}\) 按位与的结果为 \(0\)，然后删去 \([l,r]\)，删去后左边和右边合并起来。问最多能合并多少次。
\(n≤63,a_i≤63\)
solution
显然的，由于这个操作是按位与，所以对一个区间操作后的结果一定不会超过 \(\max \{ a_i\}\)。也就是不会超过 \(63\)。
再看，区间删除区间合并，而且每个区间互相独立。所以可以区间 dp。
设 \(f[l][r]\) 表示经过若干次删除操作后，最多的删除次数。但是维护的信息不太够不能转移，根据最开始的性质由于区间操作后的结果一定不会超过 \(63\)，所以区间按位与的结果也可以作为维护的信息，也就是作为第三维，表示剩下的数字按位与结果。
转移方程也很简单，就是正常区间 dp 即可。\(f[l][r][x\&y] = f[l][k][x] + f[k+1][r][y]\)
如果 \(x\&y=0\)，那么 \(f[l][r][63]=f[l][k][x]+f[k+1][r][y]+1\)。其实就是将剩下的数字作为一次操作删去，然后没有剩下的数字了， 按位与设为 \(63\)。
复杂度大概是 \(O(n^5)\) 的，可以接受。
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e2 + 5;
const int inf = 1e18;
int n, a[N];
int f[N][N][N];
signed main()
{
cin >> n;
for (rint i = 1; i <= n; i++) cin >> a[i];
for (rint i = 0; i < N; i++)
for (rint j = 0; j < N; j++)
for (rint k = 0; k < N; k++)
f[i][j][k] = -inf;
for (rint i = 1; i <= n; i++)
{
if (!a[i]) f[i][i][63] = 1;
else f[i][i][a[i]] = 0;
}
for (rint len = 1; len < n; len++)
{
for (rint l = 1; l <= n - len; l++)
{
int r = l + len;
for (rint k = l; k < r; k++)
{
for (rint x = 0; x < 64; x++)
{
if (f[l][k][x] != -inf)
{
for (rint y = 0; y < 64; y++)
{
if (f[k + 1][r][y] != -inf)
{
f[l][r][x & y] = max(f[l][r][x & y], f[l][k][x] + f[k + 1][r][y]);
if (!(x & y)) f[l][r][63] = max(f[l][r][63], f[l][k][x] + f[k + 1][r][y] + 1);
}
}
}
}
}
int sum = a[l];
for (rint i = l + 1; i <= r; i++) sum &= a[i];
f[l][r][sum] = max(f[l][r][sum], 0ll);
if (sum == 0) f[l][r][63] = max(f[l][r][63], 1ll);
}
}
int ans = 0;
for (rint l = 1; l <= n; l++)
for (rint r = l; r <= n; r++)
for (rint x = 0; x < 64; x++)
ans = max(ans, f[l][r][x]);
cout << ans << endl;
return 0;
}
T2 average
简要题意
定义一个长度为 \(n\) 的数组 \(h_i\) 的不优美度为 \(h_1 + h_n + \sum\limits_{i = 1} ^ {n - 1} |h_i - h_{i + 1}|\)。该数组已知，给定 \(Q\) 次询问，有 \(X\) 次机会让某一个 \(h_i>0\) 执行 \(h_i=h_i-1\)，最小的不优美度是多少。\(n,Q≤10^5\)
solution
发现减小一个数，当且仅当其比相邻两个数都要小时式子的值才会发生变化，且变化量一定恰好为 \(2\)，所以，若存在这样的数，直接操作一定最优。
若不存在这样的数，一定存在极长值域相同段满足这个条件。此时使式子变小的方式只能是将这个值域相同连续段中的所有数 \(−1\)，使答案 \(−2\)
。每次选择长度最小的满足上述条件的值域连续段即可。
由于删去一个连续段可能产生新的连续段，所以开一个 stack 进行维护就可以了。
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N = 5e5 + 5;
int n, q;
int l[N], r[N];
int a[N], s1[N], s2[N];
pair<int, int> c[N];
stack<int> s, emp;
signed main()
{
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> q;
for (rint i = 1; i <= n; i++) cin >> a[i];
int sum = 0;
for (rint i = 0; i <= n; i++) sum += abs(a[i + 1] - a[i]);
for (rint i = 1; i <= n; i++)
{
while (!s.empty() && a[s.top()] > a[i]) s.pop();
if (!s.empty()) l[i] = s.top();
s.push(i);
}
s = emp;
for (rint i = n; i >= 1; i--)
{
while (!s.empty() && a[s.top()] >= a[i]) s.pop();
if (!s.empty()) r[i] = s.top();
else r[i] = n + 1;
s.push(i);
}
for (rint i = 1; i <= n; i++) c[i] = make_pair(r[i] - l[i] - 1, a[i] - max(a[l[i]], a[r[i]]));
sort(c + 1, c + n + 1);
for (rint i = 1; i <= n; i++)
{
s1[i] = s1[i - 1] + c[i].y;
s2[i] = s2[i - 1] + c[i].x * c[i].y;
}
while (q--)
{
int x;
cin >> x;
if (x >= s2[n]) cout << 0 << endl;
else
{
int p = upper_bound(s2 + 1, s2 + n + 1, x) - s2;
cout << sum - 2 * (s1[p - 1] + (x - s2[p - 1]) / c[p].x) << endl;
}
}
return 0;
}
T3 tree
题目大意
给定 \(n\) 个点的树，结点 \(1\) 为根。要用 \(m\) 种颜色对每个结点染色。每个结点有一个参数 \(f_x\) 表示 \(x\) 的子树恰好出现了 \(f_x\) 种颜色。如果 \(f_x=-1\) 说明不限制子树颜色个数。问染色方案数。
\(m,n ≤1.5\times10^5\)。保证 \(f_1=m\)
solution
设 \(g_i\) 表示子树 \(i\) 恰好有 \(1\sim f_i\) 这些颜色的方案数。使用容斥原理，钦定 \(k\) 种颜色使得最终只出现这 \(k\) 种之一的颜色。有 \(g_x=\sum_{i=0}^{f_x}(-1)^{f_x-i}\prod_{y\in son(x)}g_y\dbinom{i}{f_y}\)，复杂度 \(O(nm)\)。
用树的性质来优化。发现上述式子的 \(i\) 实际上只需要从 \(f\) 最大的一个儿子开始枚举。否则组合数就为 \(0\)。合并相同的 \(f\)，即有多个相同的 \(f\) 快速幂计算。
总复杂度大概是 \(O(n\sqrt n\log n)\)
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
using namespace std;
const int N = 1.5e5 + 5;
const int M = 3e6 + 5;
const int mod = 1e9 + 7;
int n, m;
int f[N], g[N], a[N];
int fac[N], ifac[N];
int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int C(int x, int y) {return fac[x] * ifac[y] % mod * ifac[x - y] % mod;}
void dfs(int x)
{
int maxx = 1, res = 1, cnt = 0;
map<int, int> v; v[1]++;
for (rint i = h[x]; i; i = ne[i])
{
int y = e[i];
dfs(y);
res = res * g[y] % mod;
maxx = max(maxx, f[y]);
v[f[y]]++;
}
for (rint i = maxx; i <= f[x]; i++)
{
int w = 1;
for (auto y : v)
{
w = w * qpow(C(i, y.first), y.second) % mod;
}
cnt = (cnt + (((f[x] - i) & 1) ? -1 : 1) * C(f[x], i) * w % mod + mod) % mod;
}
g[x] = res * cnt % mod;
}
signed main()
{
cin >> n >> m;
fac[0] = 1;
for (rint i = 1; i <= m; i++) fac[i] = fac[i - 1] * i % mod;
ifac[m] = qpow(fac[m], mod - 2);
for (rint i = m - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % mod;
for (rint i = 2; i <= n; i++) cin >> a[i];
for (rint i = 1; i <= n; i++) cin >> f[i];
for (rint i = 1; i <= n; i++)
if (f[a[i]] == -1)
a[i] = a[a[i]];
for (rint i = 1; i <= n; i++)
if (f[i] == -1)
f[i] = 1;
for (rint i = 2; i <= n; i++) add(a[i], i);
dfs(1);
cout << g[1] << endl;
return 0;
}
T4 change
简要题意
给定长度为 \(n\) 的序列 \(a\)，有两种可执行的操作。
有 \(m\) 种形如 \(X,L,R,W\) 的操作，表示将 \(a_X\) 减一，将
\(a_L...a_R\) 加一，代价是 \(W\)。
有 \(n\) 种形如 \(b_i\) 的操作，表示将 \(a_i\) 减一，代价是 \(b_i\)。若
\(b_i=-1\) 代表这个操作不可用。
问将 \(a\) 中所有元素变成 \(0\) 的最小代价。
\(n,m≤4\times10^5\)
solution
令 \(f_i\) 为只有 \(a_i=1\) 其余都为 \(0\) 的情形的答案，初始是 \(f_i=b_i\)。当 \(X_j=i\) 且 \(f_{L_j}...f_{R_j}\) 都求出来的时候
\[f_i=\min\{f_i,W_j+\sum_{k=L_j}^{R_j}f_k\} \]这个式子和 Dijkstra 是一样的。仿照 Dijkstra 堆的过程求解即可。可以用线段树将一个 \([L,R]\) 拆成 \(\log\) 个区间。维护每个区间求出的 \(f_i\) 的个数。
答案为 \(\sum_{i=1}^{n}a_if_i\)
复杂度 \(O(n \log n)\)
#include <bits/stdc++.h>
#define rint register int
#define int long long
#define endl '\n'
#define x first
#define y second
using namespace std;
const int N = 4e5 + 5;
const int M = N << 2;
const int inf = 1e18;
int n, m;
int a[M], b[M];
int X[M], L[M], R[M], W[M];
int d[M], cnt[M], sum[M];
vector<int> vec[M];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int cost[M], dist[M];
bool v[M];
void add(int p, int l, int r, int L, int R, int x)
{
if (L <= l && r <= R)
{
vec[p].push_back(x);
d[x]++;
return;
}
int mid = (l + r) >> 1;
if (L <= mid) add(p << 1, l, mid, L, R, x);
if (R > mid) add(p << 1 | 1, mid + 1, r, L, R, x);
}
void change(int p, int l, int r, int x, int k)
{
cnt[p]++, sum[p] += k;
if (cnt[p] == r - l + 1)
{
for (rint i : vec[p])
{
cost[i] += sum[p];
if ((--d[i])) continue;
int y = X[i];
int z = W[i];
if (dist[y] > cost[i] + z)
{
dist[y] = cost[i] + z;
if (!v[y]) q.push({dist[y], X[i]});
}
}
}
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) change(p << 1, l, mid, x, k);
else change(p << 1 | 1, mid + 1, r, x, k);
}
signed main()
{
cin >> n >> m;
for (rint i = 1; i <= n; i++) cin >> a[i];
for (rint i = 1; i <= m; i++)
{
cin >> X[i] >> L[i] >> R[i] >> W[i];
add(1, 1, n, L[i], R[i], i);
}
for (rint i = 1; i <= n; i++) cin >> b[i];
for (rint i = 1; i <= n; i++) dist[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 x = q.top();
q.pop();
if (v[x.y]) continue;
v[x.y] = 1;
change(1, 1, n, x.y, dist[x.y]);
}
for (rint i = 1; i <= n; i++)
if (dist[i] >= inf && a[i] > 0)
return puts("-1"), 0;
int ans = 0;
for (rint i = 1; i <= n; i++) ans += dist[i] * a[i];
cout << ans << endl;
return 0;
}