vp 的，做出来 ABCDF。
比赛传送门
C. Least Prefix Sum
题意
给定一个长度为 $n$ 的数组 $a$，和一个数 $m$，每次可以花 $1$ 代价把一个数 $\times -1$，求最少要多少代价使得对于每个 $k\in[1,n]$：
$$\sum\limits_{i=1}^k a_i\ge \sum\limits_{i=1}^m a_i$$
$n\le 2\cdot 10^5$
题解
Tag: 贪心，数据结构
先考虑 $k<m$ 的情况。
如果 $\sum_{i=1}^k a_i< \sum_{i=1}^m a_i$，说明需要调整，而且一定是将 $k<i\le m$ 且 $a_i>0$ 的 $a_i\times -1$，才能使不等式的右式值变小。我们肯定是希望改变的 $a_i$ 越大越好。
所以我们把下标从 $m-1$ 扫到 $1$，同时用 priority_queue 维护还没有调整过的 $a_i$。如果遇到需要调整的，就从 pq 中取出一个最大值，同时 ans++。（这个思路类似 CF3D Least Cost Bracket Sequence）
$k>m$ 的情况类似，就是把正负反一下。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| ll n, m, a[200005], cnt, ans;
ll pre[200005];
priority_queue<ll>pq;
void solve() {
cin >> n >> m;
m--;
ans = cnt = 0;
while (!pq.empty())pq.pop();
rep(i, n) {
cin >> a[i];
cnt += a[i];
pre[i] = cnt;
}
if (a[m] > 0)pq.push(a[m] * 2);
for (int i = m - 1;i >= 0;i--) {
while (pre[i] < pre[m]) {
ans++;
pre[m] -= pq.top();
pq.pop();
}
if (a[i] > 0)pq.push(a[i] * 2);
}
cnt = 0;
while (!pq.empty())pq.pop();
forr(i, m + 1, n - 1) {
cnt += a[i];
if (a[i] < 0)pq.push(a[i] * -2);
while (cnt < 0) {
ans++;
cnt += pq.top();
pq.pop();
}
}
cout << ans << endl;
}
|
D. Boris and His Amazing Haircut
题意
给定长度为 $n$ 的数组 $a,b$，你的目标是将 $a$ 变成 $b$。
你有 $m$ 种操作，每种有一个参数 $x$。你可以选择一个区间 $[l,r]$，然后对于每个 $i\in [l,r],a_i:=\min(a_i,x)$。每种操作只能使用一次。可能有多种操作的参数一样。
询问可行性。
$n,m \le 2\cdot 10^5,a_i,b_i,c_i \le 10^9$
题解
Tag: 数据结构
首先判断：如果有 $a_i<b_i$ 则无解。
可以发现，对 $i$ 使用一个 $x>b_i$ 的操作是没有影响的。所以我们按照 $b_i$ 从小到大来处理。设现在处理到 $v$，那么所有 $b_i\le v$ 的位置都可以使用操作。这些位置形成了一些极长的段，我们数出有多少段包含需要改变的位置（$b_i=v$ 且 $a_i\not=b_i$），如果数量大于参数为 $v$ 的操作数量则无解。
可以用并查集维护每个位置在哪一段。最开始我的写法是：每处理过一个位置 $i$，则把 $i-1,i,i+1$ 所在的段都合并到一起。这样会被类似 2,1,3,1,2 的数据卡掉（然而 WA#72，不得不说数据真水）。正确的做法是在处理 $i$ 前判断 $i-1,i+1$ 是否已经处理过了，处理过就合并。
同时还要判断是否有 $i$ 使得 $a_i\not= b_i$ 且不存在一个操作的参数 $=b_i$，这样也是无解的。我的实现是对于每个处理过的位置打上标记，最后看有没有位置没有标记。
要离散化。注意数组开大几倍。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| const int N = 2000006;
int n, m, a[N], b[N], x[N];
vector<int>v;
int siz;
int fa[N];
int getf(int i) {
if (fa[i] == i)return i;
return fa[i] = getf(fa[i]);
}
vector<vector<int>>p;
int cnt[N];
set<int>s;
bool vis[N];
void solve() {
v.clear();
cin >> n;
rep(i, n)cin >> a[i], v.pb(a[i]);
rep(i, n)cin >> b[i], v.pb(b[i]);
cin >> m;
rep(i, m)cin >> x[i], v.pb(x[i]);
sort(v.begin(), v.end());
siz = unique(v.begin(), v.end()) - v.begin();
rep(i, n)a[i] = lower_bound(v.begin(), v.begin() + siz, a[i]) - v.begin();
rep(i, n)b[i] = lower_bound(v.begin(), v.begin() + siz, b[i]) - v.begin();
rep(i, m)x[i] = lower_bound(v.begin(), v.begin() + siz, x[i]) - v.begin();
rep(i, n)if (a[i] < b[i]) {
cout << "NO\n";
return;
}
rep(i, n)fa[i] = i;
p.resize(siz);
rep(i, siz)p[i].clear(), cnt[i] = 0;
rep(i, n)p[b[i]].pb(i);
rep(i, m)cnt[x[i]]++;
rep(i, n)vis[i] = 0;
rep(i, n - 1)if (b[i] == b[i + 1])fa[getf(i)] = getf(i + 1);
rep(i, siz) {
for (int j : p[i]) {
if (j && b[j - 1] < b[j])fa[getf(j - 1)] = getf(j);
if (j < n - 1 && b[j + 1] < b[j])fa[getf(j)] = getf(j + 1);
}
s.clear();
for (int j : p[i])if (a[j] != b[j])s.insert(getf(j));
if (cnt[i] < s.size()) {
cout << "NO\n";
return;
}
for (int j : p[i])vis[j] = 1;
}
rep(i, n)if (!vis[i]) {
cout << "NO\n";
return;
}
cout << "YES\n";
}
|
E. Anya’s Simultaneous Exhibition
题意
交互题。
有 $n$ 个人，两两之间有胜负关系。定义一个 tourment 为：$n-1$ 场淘汰赛，最后一个人胜出。称一个人为 candidate master 当且仅当合适安排赛程后他能在 tourment 中胜出。
你可以进行至多 $2n$ 场模拟。在每场模拟中，你可以让一个人依次对战另外一些人。交互库会返回他赢的次数。请你最后输出有多少人可以成为 candidate master。
$n\le 250$
题解
赛时没做出来。
以后补。
F. Xorcerer’s Stones
题意
给定一个树，节点 $i$ 权值为 $a_i$。你可以执行至多 $2n$ 次操作，每次操作可以将一个子树内所有点变成它们的异或和。求一种可行方案使得所有数变成 $0$。无解输出 $-1$。
$n\le 2\cdot 10^5,0\le a_i \le 31$
题解
Tag: 数学，DP
可以发现，如果对大小为奇数的子树执行操作，所有权值的异或和不变；如果对大小为偶数的子树执行操作，则子树内异或和变为 $0$。而当我们将整棵树的异或和变为 $0$ 后，只需要再对整棵树进行一次操作即可全部清零。
设 $f_{i,j}=0/1$ 表示能否使以 $i$ 为根的子树内异或和为 $j$。从子节点转移上来即可。如果以 $i$ 为根的子树大小为偶数，则 $f_{i,0}=1$ ，即对这棵树执行一次操作。
恶心的是居然要输出方案！写个路径还原，同时如果是执行操作的地方要打上标记。
这样做好像只要 $n$ 次操作？
时间复杂度 $O(nw^2)$，其中 $w=32$。$2\cdot 10^5 \times 32^2\approx 2\cdot 10^8$。给了 4s，能过。
Code
赛时写的代码操作次数有点多。这里放下优化后的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| const int N = 200005;
int n, a[N], fa, son[N], siz[N];
vector<int>g[N];
vector<int>dp[N][32];
void dfs(int x) {
rep(i, 32)rep(j, son[x] + 1)dp[x][i][j] = -1;
dp[x][a[x]][0] = 0;
siz[x] = 1;
rep(i, son[x]) {
int y = g[x][i];
dfs(y);
siz[x] += siz[y];
rep(m1, 32)rep(m2, 32) {
if (dp[x][m1][i] != -1 && dp[y][m2][son[y]] != -1) {
dp[x][m1 ^ m2][i + 1] = m2;
}
}
}
if (siz[x] % 2 == 0)dp[x][0][son[x]] = -2;
}
vector<int>ans;
void getans(int x, int val) {
if (dp[x][val][son[x]] == -2) {
ans.pb(x + 1);
return;
}
for (int i = son[x] - 1;i >= 0;i--) {
int y = g[x][i];
getans(y, dp[x][val][i + 1]);
val ^= dp[x][val][i + 1];
}
}
void solve() {
cin >> n;
rep(i, n)cin >> a[i];
rep(i, n - 1) cin >> fa, fa--, son[fa]++, g[fa].pb(i + 1);
rep(i, n)rep(j, 32)dp[i][j].resize(son[i] + 1);
dfs(0);
if (dp[0][0][son[0]] == -1)cout << -1;
else {
getans(0, 0);
ans.pb(1);
cout << ans.size() << endl;
for (int x : ans)cout << x << ' ';
}
}
|