# 题目大意
给你一个长度为 n 的，只有 0,1 构成的字符串 s，你可以执行以下操作若干次
- 选择任意一个字符，Si←1−Si
请问，至少经过多少次操作，字符串的 1 连续或不存在 1
# 数据范围
- 1≤T≤2×104
- 1≤∣S∣≤2×105
# 题解
如果最终，是 [l,r] 区间连续的 1 的话，其操作次数为
区间里要翻的 0 数(r−l+1−(p[r]−p[l−1]))+区间外要翻的 1 数(p[l−1]+(p[n]−p[r])),
化简有
p[n]+(r−2p[r])+(2p[l−1]−(l−1))
这样看来，还是有两个变量，枚举需要 n2 时间，怎么办呢？
我们不放想想，我们求的是答案的最小值，那我们可以只遍历 r，对于一个确定的 r，其是不是只要找到，i=1minr−1(2p[l−1]−(l−1)) 呢，而这个我们就可以用前缀最小值来实现
C++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void solve () {
cin >> n >> s, s = " " + s;
vector<int> pre(n + 1, 0);
for (int i = 1; i <= n; i++)
pre[i] = pre[i - 1] + (s[i] == '1');
int pml = 0, res = 1e18;
for (int r = 1; r <= n; r++) {
pml = min(pml, 2*pre[r] - r);
int t = pre[n] + (r - 2*pre[r]) + pml;
res = min(res, t);
}
cout << res << '\n';
}
|
这题提示我们，如果出现了区间最小 / 最大操作次数的题目，我们不妨从暴力枚举 [l,r] 区间的地方开始着手
利用前缀和或其他知识，写出最终区间是 [l,r] 的操作数的表达式，可以猜想到，最终表达式一定是一个关于 [l,r] 的方程
此时不妨尝试枚举 r，进而观察 l 相关的式子，比如此题中，要求的是求最小值，而 l 相关的式子可以用一个前缀最小值来简化掉一层循环
# 题目大意
现有一个 n 个点 m 条边的无向连通图，请你求出，顶点 1→ 顶点 n 的路径中，所有边的权值或 OR 最小值
# 数据范围
- 2≤N≤2×105
- N−1≤M≤2×105
- 0 \le w_i \le 2^
# 题解
C++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
| struct Dsu {
int f[N];
void init(int n) {
for(int i = 1; i <= n; i++)
f[i] = i;
}
int find(int x) {
return f[x] == x ? x : f[x] = find(f[x]);
}
void merge(int x, int y) {
f[find(x)] = find(y);
}
} dsu;
struct Side {
int u, v, w;
};
int n, m;
void solve () {
cin >> n >> m;
vector<Side> a(m + 1);
for (int i = 1; i <= m; i++)
cin >> a[i].u >> a[i].v >> a[i].w;
int res = (1 << 30) - 1;
for (int i = 29; i >= 0; i--) {
res -= (1 << i);
dsu.init(n);
for (int j = 1; j <= m; j++)
if ((res | a[j].w) == res)
dsu.merge(a[j].u, a[j].v);
if (dsu.find(1) != dsu.find(n))
res += (1 << i);
}
cout << res << '\n';
}
|
