[Codeforces Round #748 (Div. 3)](https://codeforces.com/contest/1593) F. Red-Black Number 記憶化搜尋

題意

給出\(n\)位的十進制數和數字\(A，B\),要求把給出的十進制數的每一位染上黑色或紅色，使得紅色部分按順序組成的十進制數（可能有前導0）以及黑色部分按順序組成的十進制數（可能有前導0)能分别被\(A,B\)整除,并且紅色的位數和黑色的位數差的絕對值最小。

\(2\le n \le 40,1\le A,B\le 40\)，無解輸出-1

題解

#include<bits/stdc++.h>
using namespace std;
const int maxn = 40 + 7;
#define ll long long
int n, m, k, tot, ans, A, B;
char s[maxn], aa[maxn], fa[maxn];
int rd() {
	int s = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') {s = s * 10 + c - '0'; c = getchar();}
	return s * f;
}
int vis[maxn][maxn][maxn][maxn];
void dfs(int cur, int x, int y, int a) {
	vis[cur][x][y][a]++;
	if (cur == n + 1) {
		if (x != 0 || y != 0 || a == 0 || a == n || ans <= abs(n-a-a)) 
			return;
		ans = abs(n-a-a);
		for (int i = 1; i <= n; i++) aa[i] = fa[i];
		return;
	}
	if (vis[cur+1][(x*10+s[cur]-'0'+A)%A][y][a+1] < tot) {
		fa[cur] = 'R';
		dfs(cur+1, (x*10+s[cur]-'0'+A)%A, y, a+1);
	}
	//if (flag) return;
	if (vis[cur+1][x][(y*10+s[cur]-'0'+B)%B][a] < tot) {
		fa[cur] = 'B';
		dfs(cur+1, x, (y*10+s[cur]-'0'+B)%B, a);
	}
	//if (flag) return;
	//aa[cur] = -1;
}
int main() {
	int T = rd();
	//memset(aa, -1, sizeof(aa));
	while (T--) {
		tot++;
		memset(aa, -1, sizeof(aa));
		memset(vis, 0, sizeof(vis));
		n = rd(), A = rd(), B = rd();
		scanf("%s", s+1);
		s[0] = '0';
		ans = 99999;
		dfs(1, 0, 0, 0);
		if (ans == 99999) {
			puts("-1");
		} else {
			for (int i = 1; i <= n; i++) {
				putchar(aa[i]);
			}
			putchar('\n');
		}
	}
	return 0;
}