题目来源:https://leetcode.com/problems/minimum-number-of-k-consecutive-bit-flips/description/

标记难度:Hard

提交次数:4/5

代码效率:

  • 暴力贪心:12.68%(5152ms)
  • 线段树:52.11%(288ms)
  • O(n):96.20%(84ms)

题意

有一个只包含0和1的数组A,每次可以将数组A中的恰好连续k个元素取反,问能否将A变成全1?

分析

很容易就能想到一种贪心策略:找到左边第一个0,从它开始翻转连续k个元素(因为这个0只能在这里通过翻转而变成1,否则左边就会出现新的0),然后对于右边的0,继续进行这一操作,如果最后能成功则A可以变成全1。这个算法是O(n*k)的,或者说是O(n^2)的,可能太慢了。

很容易就能想到一种优化策略:用线段树来进行区间更新。这样复杂度就会变成O(n*log(n)),可以接受。

用线段树实在是overkill了。可以很简单地通过记录区间的开闭事件来确定当前元素是否需要取反。甚至可以不显式地记录开闭事件——如果k个元素之前的元素是0,那么现在就是一个区间的关闭。[1]

代码

暴力贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
int ans = 0;
for (int i = 0; i < A.size(); i++) {
if (A[i] == 0) {
if (i + K - 1 >= A.size()) return -1;
for (int j = 0; j < K; j++)
A[i + j] = 1 - A[i + j];
ans++;
}
}
return ans;
}
};

线段树

当然,这是一种比较愚蠢的做法。

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
65
66
67
68
69
70
71
72
73
74
class Solution {
private:
struct TreeNode {
int l, r;
bool toFlip;

TreeNode(int _l = 0, int _r = 0) {
l = _l;
r = _r;
toFlip = false;
}
};
TreeNode tree[120005];
vector<int> a;

void buildTree(int node, int l, int r) {
if (l > r) return;
if (l == r) tree[node].l = tree[node].r = l;
else {
int m = (l + r) / 2;
tree[node].l = l;
tree[node].r = r;
buildTree(node * 2, l, m);
buildTree(node * 2 + 1, m + 1, r);
}
}

void update(int node, int l, int r) {
if (tree[node].r < l || r < tree[node].l) return;
if (l <= tree[node].l && tree[node].r <= r) {
tree[node].toFlip = !tree[node].toFlip;
return;
}
if (tree[node].toFlip) {
tree[node * 2].toFlip = !tree[node * 2].toFlip;
tree[node * 2 + 1].toFlip = !tree[node * 2 + 1].toFlip;
tree[node].toFlip = false;
}
update(node * 2, l, r);
update(node * 2 + 1, l, r);
}

bool query(int node, int l) {
if (tree[node].l == tree[node].r) {
if (tree[node].toFlip) return !a[l];
return a[l];
}
if (tree[node].toFlip) {
tree[node * 2].toFlip = !tree[node * 2].toFlip;
tree[node * 2 + 1].toFlip = !tree[node * 2 + 1].toFlip;
tree[node].toFlip = false;
}
int m = (tree[node].l + tree[node].r) / 2;
if (l <= m) return query(node * 2, l);
else return query(node * 2 + 1, l);
}

public:
int minKBitFlips(vector<int>& A, int K) {
a = A;
int n = A.size();
int ans = 0;
buildTree(1, 0, n - 1);
for (int i = 0; i < n; i++) {
bool x = query(1, i);
if (!x && i + K > n) return -1;
if (!x) {
update(1, i, i + K - 1);
ans++;
}
}
return ans;
}
};

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int minKBitFlips(vector<int>& A, int K) {
int n = A.size();
int event[n + 1];
memset(event, 0, sizeof(event));
int cur = 0, ans = 0;
for (int i = 0; i < n; i++) {
cur += event[i];
int x = (A[i] + cur) % 2;
if (x == 0) {
if (i + K - 1 >= n) return -1;
cur++;
ans++;
event[i + K]--;
}
}
return ans;
}
};

  1. les215's solution - [Java/C++/Python] One Pass and O(1) Space

题意

洛谷 P1459 三值的排序 Sorting a Three-Valued Sequence

给定一个只包含1,2,3的数组,问将这个数组排序最少需要多少次交换。

分析

这个好像是之前的翻译:贪心算法(USACO)的原题……所以做法也没什么好说的了。首先找出一次交换可以解决的“错位”二元组的数量,然后再找出需要两次交换才能解决的“错位”三元组的数量即可。只要仔细一想就可以发现,每种二元组和三元组的数量是固定的,只跟每个“区域”(排序之后某种元素应该占的位置)内的其他元素的数量相关。

以及我觉得这道题和Codeforces 1102D. Balanced Ternary String有一点点像。(虽然像的程度很有限就是了……)

代码

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
65
/*
ID: zhanghu15
TASK: sort3
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
typedef long long int LL;

int N;
int a[1000];
int num[4];
int cnt[4][4];

int main() {
ofstream fout("sort3.out");
ifstream fin("sort3.in");
fin >> N;
for (int i = 0; i < N; i++) {
fin >> a[i];
num[a[i]]++;
}
int start = 0;
// cnt[i][j]:在i“区域”内j的数量
for (int i = 1; i <= 3; i++) {
for (int j = 0; j < num[i]; j++) {
cnt[i][a[start + j]]++;
}
start += num[i];
}
int swaps = 0;
// 一次交换能解决的数所需交换次数
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (i == j) continue;
// 尽可能地将i区域内的j和j区域内的i相交换
int x = min(cnt[i][j], cnt[j][i]);
swaps += x;
cnt[i][j] -= x;
cnt[j][i] -= x;
}
}
// 两次交换能解决的数所需交换次数
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
if (i == j) continue;
int k = 6 - i - j;
// 尽可能地将i区域内的j和j区域内的k交换,然后再和k区域内的i交换
int x = min(min(cnt[i][j], cnt[j][k]), cnt[k][i]);
swaps += x * 2;
cnt[i][j] -= x;
cnt[j][k] -= x;
cnt[k][i] -= x;
}
}
fout << swaps << endl;
return 0;
}

题目来源:https://codeforces.com/contest/1107/problem/C

提交次数:1/1

题意

给定n个英文小写字符和对应的n个值,按某个字符就可以得到对应的值,不能连续按某个字符超过k次,问得到的值的总和最大是多少。

分析

这次比赛我做得乱七八糟。从提交数量来看,C应该是道很简单的题,但是我却做不出来。事后我发现我看错题了。

PS. 我决定以后CF比赛中我能做出来的题就不写题解了。不然题目实在太多了。。。


对于一串连续的字符,如果它的长度超过了k,那么从里面挑k个最大值就行。没了!

(比赛的时候我以为是要把这个串分割成若干个长度小于k的串。)

[soln1]: Codeforces Blog - Quick unofficial editorial for Educational Round 59 (Div. 2)

[soln2]: Codeforces Blog - Educational Codeforces Round 59 Editorial

代码

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
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int k, n;
LL a[200005];
char s[200005];
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
cin >> s;
LL ans = 0;
int start = 0;
for (int i = 1; i <= n; i++) {
if (i == n || s[i] != s[i-1]) {
if (i - start > k)
sort(a + start, a + i);
for (int j = 0; j < k && i-j-1 >= start; j++)
ans += a[i - j - 1];
start = i;
}
}
cout << ans << endl;
return 0;
}