A.小红的 01 背包
能装多少装多少就行
$code:$
void solve() {
int v, x, y;
std::cin >> v >> x >> y;
std::cout << v / x * y << '\n';
}
B.小红的 dfs
枚举每一行，然后对于第一行为 $dfs$ 的情况, 只存在第一列也为 $dfs$ 满足，其他行同理枚举一遍即可
void solve() {
char g[3][3];
for(int i = 0; i < 3; i ++) {
for(int j = 0; j < 3; j ++ ) {
std::cin >> g[i][j];
}
}
int ans = 9, v = 0;
if(g[0][0] != 'd') v ++;
if(g[0][1] != 'f') v ++;
if(g[0][2] != 's') v ++;
if(g[1][0] != 'f') v ++;
if(g[2][0] != 's') v ++;
ans = std::min(ans, v);
v = 0;
if(g[1][0] != 'd') v ++;
if(g[1][1] != 'f') v ++;
if(g[1][2] != 's') v ++;
if(g[0][1] != 'd') v ++;
if(g[2][1] != 's') v ++;
ans = std::min(ans, v);
v = 0;
if(g[2][0] != 'd') v ++;
if(g[2][1] != 'f') v ++;
if(g[2][2] != 's') v ++;
if(g[0][2] != 'd') v ++;
if(g[1][2] != 'f') v ++;
ans = std::min(ans, v);
std::cout << ans << '\n';
}
C.小红的排列生成
先将其排序, 然后构造排列 $1, 2, 3, …, n$ , 统计代价即可
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for(int i = 0; i < n; i ++ ) {
std::cin >> a[i];
}
std::sort(a.begin(), a.end());
i64 s = 0;
for(int i = 0; i < n; i ++ ) {
s += std::abs(a[i] - i - 1);
}
std::cout << s << '\n';
}
D.小红的二进制树
由题意, 从一点往子节点走，要其形成的二进制数为奇数，即最后一位为1, 故统计子树中的一的个数即可
void solve() {
int n;
std::string s;
std::cin >> n >> s;
std::vector<int> w(n);
for(int i = 0; i < n; i ++ ) {
w[i] = s[i] - '0';
}
auto c = w;
std::vector<std::vector<int>> adj(n);
for(int i = 0; i < n - 1; i ++ ) {
int u, v;
std::cin >> u >> v;
u --, v --;
adj[u].push_back(v);
adj[v].push_back(u);
}
auto dfs = [&](auto self, int u, int fa) -> void {
for(auto v : adj[u]) {
if(v != fa) {
self(self, v, u);
w[u] += w[v];
}
}
};
dfs(dfs, 0, -1);
for(int i = 0; i < n; i ++ ) {
std::cout << w[i] - c[i] << '\n';
}
}
E.小红的回文数
我们对每一个数的出现次数为奇数还是偶数进行状态统计, $0$ 表示为偶数, $1$ 表示为奇数, 总共有 $10$ 个数, 我们只需要用一个 $2^{10}$ 的数即可统计其状态, 然后能构造成回文串的话, 当且仅当只有一位为 $1$ 或者全为 $0$, 然后我们记录之前的状态, 然后我们从前往后统计, 选择当前位置 $i$, 然后枚举前面位置 $j$ , 只需要 $i$ 的状态与 $j$ 的状态相同或只有 $1$ 位有区别即可, 枚举肯定超时, 开一个桶记录即可, 然后计算贡献
void solve() {
std::map<int, int> mp;
mp[0] = 1;
std::string s;
std::cin >> s;
i64 ans = 0, st = 0;
for(int i = 0, n = s.size(); i < n; i ++ ) {
int v = s[i] - '0';
st ^= (1 << v);
for(int j = 0; j < 10; j ++ ) {
ans += mp[st ^ (1 << j)];
}
ans += mp[st];
mp[st] ++;
}
std::cout << ans << '\n';
}
F.小红的矩阵修改
观察到 $n$ 非常的小, 每一位也就只有三种情况, 这很容易想到状压$dp$, 枚举每一位填什么即可, 复杂度也不高
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<char>> g(n, std::vector<char>(m));
for(int i = 0; i < n; i ++ ) {
for(int j = 0; j < m; j ++ ) {
std::cin >> g[i][j];
if(g[i][j] == 'r') g[i][j] = 0;
if(g[i][j] == 'e') g[i][j] = 1;
if(g[i][j] == 'd') g[i][j] = 2;
}
}
auto check = [&](const std::vector<int> &o) -> bool {
for(int i = 1; i < n; i ++ ) {
if(o[i] == o[i - 1]) {
return false;
}
}
return true;
};
//
std::vector<std::vector<int>> st;
//
for(int i = 0, r = pow(3, n); i < r; i ++ ) {
int k = i;
std::vector<int> v;
while(k) {
v.push_back(k % 3);
k /= 3;
}
while(v.size() < n) v.push_back(0);
std::reverse(v.begin(), v.end());
if(check(v)) {
st.push_back(v);
}
}
auto get = [&](int pos, const std::vector<int> &a) -> int {
int cnt = 0;
for(int i = 0; i < n; i ++ ) {
if(a[i] != g[i][pos]) {
cnt ++;
}
}
return cnt;
};
auto ok = [&](const std::vector<int> &a, const std::vector<int> &b) -> int {
for(int i = 0; i < n; i ++ ) {
if(a[i] == b[i]) {
return false;
}
}
return true;
};
// 3 ^ 4
std::map<std::vector<int>, i64> dp, _dp;
for(auto v : st) {
dp[v] = get(0, v);
}
for(int i = 1; i < m; i ++ ) {
_dp.clear();
for(auto [x, y] : dp) {
for(auto v : st) {
int w = get(i, v);
if(ok(x, v)) {
if(!_dp.count(v)) {
_dp[v] = y + w;
} else {
_dp[v] = std::min(_dp[v], y + w);
}
}
}
}
dp = _dp;
}
i64 ans = 1e9;
for(auto [x, y] : dp) {
ans = std::min(ans, y);
}
std::cout << ans << '\n';
}