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

题意

给出(n)位的十进制数和数字(A,B),要求把给出的十进制数的每一位染上黑色或红色,使得红色部分按顺序组成的十进制数(可能有前导0)以及黑色部分按顺序组成的十进制数(可能有前导0)能分别被(A,B)整除,并且红色的位数和黑色的位数差的绝对值最小。

(2le n le 40,1le A,Ble 40),无解输出-1

题解

注意到(A,B)都很小,考虑从(A,B)入手

可以用类似快读的写法,中间加个取模就能动态维护当前选出的数字组成的数能否被整除。 把取模后的结果加入到状态中,则能够得到一个四维的状态(cur, x, y, cnt),表示当前在处理从高到低第cur位,黑色的数字组成的数取模后为x, 红色的数字组成的数取模后为y,选了cnt个黑色数字。

每一个状态只需要访问一次,那么就得到了时空复杂度均为(O(n^4))的算法。

#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('
');
		}
	}
	return 0;
}
原文地址:https://www.cnblogs.com/YjmStr/p/15417522.html