dp：ICPC2025沈阳D

LED Display Renovation - Problem - QOJ.ac

image-20261010202136642

感觉这种题就是思维难度不高，但是细节很多，考场上很难在短时间内写出来，反正对目前的我来说场上写出来很难，赛后补不难

我们考虑设三个dp：

  • f(i,j,0/1)f(i,j,0/1)（有两项 xx 和 cntcnt）：前 ii 位，用 jj 次，是否可以表示出全空下：最多表示出多少个数，同时有多少个方案。
  • F(i,j)F(i,j)：前 ii 位用 jj 次，有多少种方案可以前面全空
  • G(i,j)G(i,j)：前 ii 位用 jj 次，有多少种方案可以让前面全空且表示不出来任何数

对于每一位，我们就暴力枚举 272^7 种修复方案，然后判断是否可以表示出0，是否可以表示出空，是否可以表示出1-9中多少个数。

F(i,j)F(i,j) 的转移是容易的，空就可以转移。

G(i,j)G(i,j) 可以从 F(i−1,k)F(i-1,k) 转移过来，同理。

对于 f(i,j,0/1)f(i,j,0/1)，有两种转移方式：

  1. 从上一个 ff 转移过来，方案数为0-9中可以表示出来的数。
  2. 从上一个 f(,,0)f(,,0) 转移过来，方案为1-9中可以表示出来的数。
  3. 从上一个 GG 转移过来，方案为1-9中可以表示出来的数。
  4. 如果当前是第一位，也可以表示出0

至于为什么 ff 和 GG 要分开算，我也不知道。我是写着完错了对拍打补丁打补丁打补丁才搞出这么多个dp的，理论上应该是有更巧妙的做法的。

需要特判的是表示不出来任何的数，此时的方案为 ∑i=0k(ni)\sum_{i=0}^k\binom n i （这个东西调了我好久）

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include<bits/stdc++.h>
#include<cassert>
using namespace std;bool Mbe;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
int arr[11][7] = {
    {2, 2, 2, 1, 2, 2, 2}, // 0: 原 1110111
    {1, 1, 2, 1, 1, 2, 1}, // 1: 原 0010010
    {2, 1, 2, 2, 2, 1, 2}, // 2: 原 1011101
    {2, 1, 2, 2, 1, 2, 2}, // 3: 原 1011011
    {1, 2, 2, 2, 1, 2, 1}, // 4: 原 0111010
    {2, 2, 1, 2, 1, 2, 2}, // 5: 原 1101011
    {2, 2, 1, 2, 2, 2, 2}, // 6: 原 1101111
    {2, 1, 2, 1, 1, 2, 1}, // 7: 原 1010010
    {2, 2, 2, 2, 2, 2, 2}, // 8: 原 1111111
    {2, 2, 2, 2, 1, 2, 2},  // 9: 原 1111011
    {1, 1, 1, 1, 1, 1, 1}  // all lights are off
};
//#define M
//#define mo
//#define N
struct node {
	int x, cnt; 
	void print() {
		#ifdef LOCAL
			debug("%lld %lld\n", x, cnt); 
		#else
			printf("%lld %lld\n", x, cnt); 
		#endif
	}
	void clear() {
		x = cnt = 0; 
	}
}f[11][100][2], G[11][100], F[11][100], ans; 
node max(node A, node B) {
	if(B.cnt == 0) return A; 
	if(A.cnt == 0) return B; 
	if(A.x > B.x) return A; 
	if(B.x > A.x) return B; 
	return {A.x, A.cnt + B.cnt}; 
}
node operator + (node A, int x) {
	return {A.x + x, A.cnt}; 
}
node operator * (node A, int x) {
	return {A.x * x, A.cnt}; 
}
node operator + (node A, node B) {
	A.x = 0; B.x = 0;  
	assert(A.x == 0 && B.x == 0); 
	return {0, A.cnt + B.cnt}; 
}
int n, m, i, j, k, T;
char ST[10][100]; 
int C[150][150], SC[150][150]; 
int o, o1, S; 
vector<int>a[10]; 
int kn, km; 

void Work(int k, int line, int j) {
	for(int i = 1; i <= n; ++i, j += 5) 
		if(ST[line][j] == '0') a[i][k] = 1; 
		else if(ST[line][j] == '1') a[i][k] = 2; 
		else if(ST[line][j] == 'W') a[i][k] = 3; 
		else debug("%c[%d]\n", ST[line][j], j), assert(0); 
}

tuple<int, int, int> calc(vector<int>s) {
	int i, j, k1 = 0, k2 = 0, k3 = 0; 
	for(i = 0; i <= 10; ++i) {
		for(j = 0; j < 7; ++j) 
			if((s[j] & arr[i][j]) != arr[i][j]) break; 
		if(j == 7) {
			if(i == 0) ++k1; 
			else if(1 <= i && i <= 9) ++k2; 
			else if(i == 10) ++k3; 
		}
	}
	return {k1, k2, k3}; 
}

bool Med; signed main() {
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	  atexit([]{fprintf(stderr,"%.lfms\n%lfMB\n",clock()*1000./CLOCKS_PER_SEC,(&Mbe-&Med)/1024./1024);});
	#endif
	srand(time(NULL));
	T = read(); int TT = 0; 
	C[0][0] = 1; 
	for(i = 1; i <= 7 * 21; ++i) 
		for(j = 0; j <= i; ++j) 
			C[i][j] = C[i - 1][j] + C[i - 1][j - 1], 
			SC[i][j] = SC[i][j - 1] + C[i][j]; 
	while(T--) {
		++TT; 
		n = read(); m = read(); 
		if(TT == 1) kn = n, km = m; 
		for(i = 1; i <= 7; ++i) scanf("%s", ST[i] + 1); 
		for(i = 0; i <= n; ++i) {
			a[i].resize(7); 
			for(j = 0; j <= m; ++j) 
				f[i][j][0].clear(), f[i][j][1].clear(), 
				G[i][j].clear(), F[i][j].clear(); 	
		}
		Work(0, 1, 2); Work(1, 2, 1); Work(2, 2, 4); 
		Work(3, 4, 2); Work(4, 5, 1); Work(5, 5, 4); 
		Work(6, 7, 2); 
		G[0][0] = {0, 1}; F[0][0] = {0, 1}; 
		for(i = 1; i <= n; ++i) {
			for(j = 0; j <= m; ++j) 
			for(o1 = 0; o1 <= 1; ++o1) {
				for(S = 0; S < (1 << 7); ++S) {
					k = __builtin_popcount(S); 
					vector<int>b = a[i]; 
					for(int bit = 0; bit < 7; ++bit) 
						if((S >> bit) & 1) b[bit] = 3; 
					auto [x0, x, o2] = calc(b); 
					int nj = j + k;
					if(j + k > m) continue; 
					int no = (o1 & o2); 
					node t; t.clear(); 
					t = f[i - 1][j][o1] * (x + x0);  
					if(i == n) x += x0; 
					if(o1) t = t + x; //can have no leading zero
					f[i][nj][no] = max(f[i][nj][no], t); 
					if(o1 && x) 
						f[i][nj][no] = max(f[i][nj][no], G[i - 1][j] + x); 
					if(o2 == 1 && o1 == 1) {
						F[i][nj] = F[i][nj] + F[i - 1][j]; 
						if(x == 0) 
							G[i][nj] = G[i][nj] + F[i - 1][j]; 
					}
				}
			} 
			for(j = 0; j <= m; ++j) 
				for(o = 0; o <= 1; ++o) {
					if(!f[i][j][o].cnt) f[i][j][o].x = 0;  
					else if(!f[i][j][o].x) f[i][j][o].cnt = 0;  
					else debug("f[%lld][%lld][%lld] = %lld %lld\n", i, j, o, f[i][j][o].x, f[i][j][o].cnt); 
				}
			for(j = 0; j <= m; ++j) {
				if(!G[i][j].cnt) G[i][j].x = 0; 
				else debug("G[%lld][%lld] = %lld %lld\n", i, j, G[i][j].x, G[i][j].cnt); 
				
			}
			debug("\n"); 
		}
		ans.clear(); 
		for(j = 0; j <= m; ++j) 
			for(o = 0; o <= 1; ++o) 
				if(f[n][j][o].cnt)
				ans = max(ans, f[n][j][o]); 
		if(ans.x == 0) {			
			printf("0 %lld\n", SC[7 * n][m]); 
		}
		else ans.print(); 
			
	}
	
	return 0;
}