LOJ 6274 数字

发表于 更新于 分类于

首先，把所有数二进制拆分一下，然后数位\(dp\)爆搜当前位分别填什么，然后这题就做完了。

做完个锤子。

如果填\(0/1\)，\(1/0\)，\(0/0\)，最后并起来都是一个数，但是\(x,y\)却不相同了。

据可靠消息，发现这三种填法的方案数是包含关系，也就是说你在这一位填什么，最后都不会让某个方案不同于其中一个能最大化答案的那个方案。

因为当前填什么对后面的影响就是会不会碰到上下界，调整一下可以证。

具体可以看看其他大佬的博客。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 99;
ll f[N][2][2][2][2];
int t[N], a[N], b[N], c[N], d[N], mx;
int dx[4] = {1, 0, 0, 1};
int dy[4] = {0, 1, 0, 1};

ll read() {
	ll w = 0;
	char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') {
    	w = w * 10 + ch - 48;
    	ch = getchar();
    }
    return w;
}
void work(int *a, ll x) {
	int cnt = 0;
	while (x) a[++cnt] = x % 2, x /= 2;
	if (cnt > mx) mx = cnt;
}
ll dfs(int x, bool lx, bool rx, bool ly, bool ry) {
    if (x == 0) return 1;
    if (f[x][lx][rx][ly][ry] != -1) return f[x][lx][rx][ly][ry];
    ll &res = f[x][lx][rx][ly][ry], ans;
    res = 0;
    for (int i = 0; i < 4; i++) {
    	int nx = dx[i], ny = dy[i];
    	if ((nx | ny) != t[x]) continue;
    	if (lx && nx < a[x]) continue;
    	if (rx && nx > b[x]) continue;
    	if (ly && ny < c[x]) continue;
    	if (ry && ny > d[x]) continue;
    	if (nx & ny) res += dfs(x - 1, lx && a[x] == nx, rx && b[x] == nx, ly && c[x] == ny, ry && d[x] == ny);
    	else res = max(ans, dfs(x - 1, lx && a[x] == nx, rx && b[x] == nx, ly && c[x] == ny, ry && d[x] == ny));
    }
    return res;
}

int main() {
    memset(f, -1, sizeof f);
    work(t, read());
    work(a, read());
    work(b, read());
    work(c, read());
    work(d, read());
    printf("%lld\n", dfs(mx, 1, 1, 1, 1));
    return 0;
}