算法设计中,二进制和状态压缩
是很常见的处理dp问题,搜索问题的关键

二分,序列问题,单调性也常常一起出现

二进制状态压缩

  • 取出nn 在二进制下的第kk 位:(n>>k) & 1(n >>k) \ \& \ 1
  • 取出nn 在二进制下的第0k10 \to k-1 位(后kk 位):n & ((1<<k)1)n \ \& \ \left((1<<k)-1\right)
  • 把整数nn 在二进制表示下的第kk 位取反:n(1<<k)n \oplus (1<<k)
  • 对整数nn 在二进制表示下的第kk 位赋值11n(1<<k)n \mid (1<<k)
  • 对整数nn 在二进制表示下的第kk 位赋值00n & ( (1<<k))n \ \& \ (\text{~}(1<<k))

位运算每一位都是相对独立的
一般来说,需要从高位到低位每个 bit 依次检查
决定该位填 0 或者填 1

如果这一位填的是 0,那么对于这个数valval该位无贡献
否则的话,应该要将

1
val += (1 << bit)

Acwing998

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
const int maxn = 1e5 + 10;
pair<string, int> a[maxn];
int n, m;

inline int calc(int bit, int cur) {
_rep(i, 1, n) {
int x = a[i].second >> bit & 1;
if (a[i].first == "AND") cur &= x;
else if (a[i].first == "OR") cur |= x;
else cur ^= x;
}
return cur;
}

void solve() {
int val = 0, ans = 0;
for (int bit = 29; bit >= 0; bit--) {
int res0 = calc(bit, 0);
int res1 = calc(bit, 1);

if (val + (1<<bit) <= m && res0 < res1) {
val += (1<<bit);
ans += (res1<<bit);
}
else ans += res0<<bit;
}
printf("%d\n", ans);
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);

_rep(i, 1, n) {
char str[10];
int x;
scanf("%s%d", str, &x);
a[i] = make_pair(str, x);
}

// then solve
solve();
}

一个数在二进制下有多少个1

1
2
3
4
5
void bitcount(int x) {
int cnt = 0;
for (; x; x -= lowbit(x)) cnt++;
return cnt;
}

状态压缩二维矩阵

Acwing116
Acwing116

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
typedef pair<int, int> PII;
const int maxn = 5;
char a[maxn][maxn];

int change[maxn][maxn], st = 0;

inline int _hash(int x, int y) { return 4*x + y; }
// decode (i, j) <-- (x/4, x%4)

void prework() {
st = 0;
_for(i, 0, 4) _for(j, 0, 4) {
if (a[i][j] == '+') st += (1<<_hash(i, j));
}

// then prework change
memset(change, 0, sizeof change);
_for (i, 0, 4) _for(j, 0, 4) {
_for(k, 0, 4) {
change[i][j] += (1<<_hash(i, k));
change[i][j] += (1<<_hash(k, j));
}
change[i][j] -= (1<<_hash(i, j));
}
}

void solve() {
vector<PII> ans;

_for(val, 0, (1<<16)) {
// enumerate solution val
vector<PII> path;
int cur = st;
_for(i, 0, 16) if ((val>>i) & 1) {
// i is counted
int x = i / 4, y = i % 4;
path.push_back(make_pair(x, y));
cur ^= change[x][y];

if (cur == 0 && (ans.empty() || ans.size() > path.size())) ans = path;
}
}

printf("%d\n", (int)ans.size());
for (auto x : ans) printf("%d %d\n", x.first + 1, x.second + 1);
}

void init() {
memset(change, 0, sizeof change);
st = 0;
}

int main() {
freopen("input.txt", "r", stdin);
init();

// get data
_for(i, 0, 4) scanf("%s", a[i]);

// prework
prework();

// then solve
solve();
}

状态依赖与递推

Acwing95
Acwing95

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
const int inf = 0x3f3f3f3f;
const int maxn = 10;
char _a[maxn][maxn];
int a[maxn][maxn], b[maxn][maxn];
int n, ans = inf;

void init() {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
ans = inf;
}

void handle(int x, int y) {
b[x][y] ^= 1;
b[x-1][y] ^= 1;
b[x][y-1] ^= 1;
b[x+1][y] ^= 1;
b[x][y+1] ^= 1;
}

bool ok() {
_rep(i, 1, 5) _rep(j, 1, 5) if (b[i][j] == 0) return false;
return true;
}

void solve() {
for (int sta = 0; sta <= (1<<5); sta++) {
int cnt = 0;
memcpy(b, a, sizeof(a));

for (int i = 1; i <= 5; i++) if (sta >> (i-1) & 1) {
cnt++;
handle(1, i);
}

_rep(i, 1, 4) _rep(j, 1, 5) {
if (b[i][j] == 0) {
cnt++;
handle(i+1, j);
}
}

if (ok()) chmin(ans, cnt);
}
if (ans > 6) ans = -1;
}

void dbg() {
_rep(i, 1, 5) {
_rep(j, 1, 5) printf("%d", a[i][j]);
printf("\n");
}
printf("\n");
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d", &n);

_rep(kase, 1, n) {
init();
_rep(i, 1, 5) scanf("%s", _a[i]+1);
_rep(i, 1, 5) _rep(j, 1, 5) a[i][j] = _a[i][j] - '0';
// dbg();

// then solve
solve();
printf("%d\n", ans);
}
}

计算几何问题中的精度处理

在解决计算几何问题的时候,常常涉及到四舍五入相关的输出
在处理此类问题, 特别是比如距离 dist 结果时
可以用以下代码

1
2
3
ll dx = ans1.first - ans2.first, dy = ans1.second - ans2.second;
double dist = (double)sqrt(dx*dx + dy*dy);
printf("%.0lf\n", dist);

序列问题

无长度限制的最大子段和

To the max
Acwing126

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
const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
int n, a[maxn][maxn], S[maxn][maxn];
bool allnegative = true;
int res = -inf;

void prework() {
_rep(i, 1, n) {
_rep(k, 1, n) S[k][i] = S[k-1][i] + a[k][i];
}
}

void solve() {
if (allnegative) {
_rep(i, 1, n) _rep(j, 1, n) chmax(res, a[i][j]);
return;
}

_rep(l, 1, n) _rep(r, l, n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += S[r][i] - S[l-1][i];

if (sum < 0) sum = 0;
else chmax(res, sum);
}
}
}

void init() {
memset(S, 0, sizeof S);
allnegative = true;
res = -inf;
}

int main() {
freopen("input.txt", "r", stdin);
cin >> n;
init();
_rep(i, 1, n) _rep(j, 1, n) {
scanf("%d", &a[i][j]);
if (a[i][j] >= 0) allnegative = false;
}

// prework and solve
prework();
solve();
printf("%d\n", res);
}