牛客周赛 Round 20
1.小红的数位删除(二进制枚举)
输入1：
37 111
输出1：
0
说明：
111是37的倍数，所以小红不需要任何操作。
输入2：
1234 99
输出2：
2
说明：
第一个数删除数字'1'，变成234。第二个数删除数字'9'，变成9。234是9的倍数。
二进制枚举
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define y second
#define x first
using namespace std;
const int N = 1e5 + 7;
unordered_map<int, int> mpa, mpb;
int ans;
inline void get1(string s) {
int n = s.size();
for(int i = 1; i < (1 << n); i ++) {
int ans = 0, t = 0;
for(int j = 0; j < n; j ++)
if((i >> j) & 1)
ans = ans * 10 + s[j] - '0', t ++;
mpa[ans] = n - t;
}
}
inline void get2(string s) {
int n = s.size();
for(int i = 1; i < (1 << n); i ++) {
int ans = 0, t = 0;
for(int j = 0; j < n; j ++)
if((i >> j) & 1)
ans = ans * 10 + s[j] - '0', t ++;
mpb[ans] = n - t;
}
}
inline void solve() {
string s1, s2;
cin >> s1 >> s2;
get1(s1);
get2(s2);
ans = 1e6;
for(auto a : mpa)
for(auto b : mpb)
if(a.x % b.x == 0||b.x % a.x == 0)
ans = min(ans, a.y + b.y);
if(ans > 1e6 / 2) ans = -1;
cout << ans << '\n';
}
signed main() {
IOS;
int T = 1; // cin >> T;
while(T --)
solve();
return T ^ T;
}
2.小红的漂亮串(dfs)
输入1：
3
输出1：
1
输入2：
4
输出2：
52
dfs
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr)
#define mod 1000000007
using namespace std;
const int N = 1e5 + 10;
int f[N][4][4][2];
int n;
inline int dfs(int u, int u1, int u2, int flag) {
if(u == n) return flag;
if(f[u][u1][u2][flag]) return f[u][u1][u2][flag];
int ans = 0;
for(int i = 0; i < 26; i ++) {
if(u1 == 2&&u2 == 1&&i == 0) continue;
if(u1 == 0&&u2 == 1&&i == 2) ans = (ans + dfs(u + 1, u2, i > 2 ? 3 : i, 1)) % mod;
else ans = (ans + dfs(u + 1, u2, i > 2 ? 3 : i, flag)) % mod;
} return f[u][u1][u2][flag] = ans;
}
inline void solve() {
cin >> n;
cout << dfs(0, 3, 3, 0) << '\n';
}
signed main() {
IOS;
int T = 1; // cin >> T;
while(T --)
solve();
return T ^ T;
}