true
Fenwick Tree
2021 ICPC Asia East Continent Final
none
none
题目大意是，给定我们一个树状数组，我们只知道每一个位置上是否为 $0$，我们需要求出可能的最小操作次数使得一个全零的树状数组在经过这些次数的操作之后各位置上元素的状态符合题目给定的状态。
操作的数字和树状数组内的数字都可以是任意实数。
首先我们按照树状数组更新的顺序建立一片森林，可以发现在某一个节点更新之后会影响到的是其到根的一条链。
同时，这样也确保了一个位置只能被其子树内的位置上的修改影响。
那我们考虑在这个树上进行DP。
首先，我们可以确定，一个位置上如果非零的话，其一定需要子树内的至少一次操作。
然后我们考虑当前位置怎么从子树中转移。
枚举每一个儿子的时候，我们对当前位置在完成转移后将要成为的颜色进行分类讨论。
如果当前位置是零，那么要求要么其之前为零且儿子为零，要么其之前非零且儿子非零。
如果当前位置非零，那么要求要么其之前为零且儿子非零，要么其本身为零而儿子随便。
具体式子如下：
$$
\begin{align}
f_{u,0}&=\min(f_{u,0}+f_{v,0},f_{u,1},f_{v,1}) \\
f_{u,1}&=\min(f_{u,0}+f_{v_1},f_{u,1}+f_{v,0},f_{u,1}+f_{v,1})
\end{align}
$$
因为我们只知道最终的状态，操作中间的状态是不可预知的，所以我们只能在最终转移完之后，考虑其节点最终的颜色，选取对应的DP值继续向上转移。
最后统计每一棵树的根节点的DP值即可。
代码如下：
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
56
57
58
59
60
61
62
63
64
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1000010, M = N << 1;
#define lowbit(x) ((x)&(-(x))
int 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++;
}
string s;
int tag[N];
ll f[N][2];
ll ans = 0;
void dfs(int p, int fa)
{
f[p][0] = 0, f[p][1] = 1;
for(int i = h[p]; ~i; i = ne[i])
{
if(e[i] == fa)continue;
int j = e[i];
dfs(j, p);
int tmp0 = INT_MAX, tmp1 = INT_MAX;
tmp0 = min(f[p][0] + f[j][0], f[p][1] + f[j][1]);
tmp1 = min(min(f[p][0] + f[j][1], f[p][1] + f[j][0]), f[p][1] + f[j][1]);
f[p][0] = tmp0, f[p][1] = tmp1;
}
if(tag[p])f[p][0] = INT_MAX;
else f[p][1] = INT_MAX;
}
void solve()
{
scanf("%d", &n);
for(int i = 1; i <= n; i++)
h[i] = -1;
cin >> s;
for(int i = 1; i <= n; i++)
tag[i] = s[i - 1] - '0';
vector<int>v;
for(int i = 1; i <= n; i++)
{
int k = i + lowbit(i);
if(k > n)v.push_back(i);
else add(i, k), add(k, i);
}
for(auto i : v)
{
dfs(i, 0);
ans += min(f[i][0], f[i][1]);
}
printf("%lld\n", ans);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
ans = 0;
solve();
}
return 0;
}
|