题意
给出长度为n ( n < = 40 )由数字构成的字符串和a , b请将该字符串分为两部分A , B使得A变为数字后可以整除a，B可以整除b，并且A , B至少有一位。最小化A , B的位数之差，输出方案。
思路
看到n的范围后想到了搜索，会有很多重复的状态所以做一个标记，如果已经遇到过这个状态就不再继续向下搜了。
搜索的时候维护当前A m o d a 的值m a，B m o d b的值m b，A的位数c n t a和当前枚举到第u位。终止条件为u = = n，看此时能否满足整除条件并且1 < = c n t a
代码
#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std; typedef long long ll; int n, a, b, ans, col[55], dp[55][55][55][55]; string s; int st[55]; void dfs(int u, int ma, int mb, int cnta) { if (u == n) { if (!ma && !mb && cnta >= 1 && cnta < n) { if (abs(n - cnta - cnta) < ans) { ans = abs(n - cnta - cnta); for (int i = 0; i < n; i++) col[i] = st[i]; } } return; } if (dp[u][ma][mb][cnta]) return; dp[u][ma][mb][cnta] = 1; st[u] = 0; dfs(u + 1, (ma*10 + s[u] - '0') % a, mb, cnta + 1); st[u] = 1; dfs(u + 1, ma, (mb*10 + s[u] - '0') % b, cnta); } int main() { int _; cin >> _; while (_--) { cin >> n >> a >> b; cin >> s; ans = 1e9; memset(dp, 0, sizeof dp); dfs(0, 0, 0, 0); if (ans == 1e9) puts("-1"); else { for (int i = 0; i < s.size(); i++) if (col[i]) cout << "B"; else cout << "R"; puts(""); } } return 0; } /* 4 5 3 13 02165 4 2 1 1357 8 1 1 12345678 2 7 9 90 */
