链接：https://ac.nowcoder.com/acm/contest/127264
A – 小红的大小判断
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
int x;
cin >> x;
if (x > x * x)
cout << "left" << endl;
else if (x < x * x)
cout << "right" << endl;
else
cout << "equal" << endl;
}B – 小红的大小再判断
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
string s;
cin >> s;
string ss = s;
ranges::reverse(ss);
if (s > ss)
cout << "left" << endl;
else if (s < ss)
cout << "right" << endl;
else
cout << "equal" << endl;
}C – 小红的肥鹅健身房
算法：
模拟。
思路：
无。
关键代码：
void miyan()
{
int n, m, k;
cin >> n >> m >> k;
map<int, int> cnt;
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
int x;
cin >> x;
if (x)
++cnt[x];
}
}
priority_queue<pii, vector<pii>, greater<>> q;
for (auto &[x, y] : cnt)
q.push({x, y});
ll ans = 0, res = 0;
while (q.size())
{
auto [x, y] = q.top();
q.pop();
while (q.size() && q.top().first == x)
{
y += q.top().second;
q.pop();
}
if (y <= 1)
continue;
int t = y / 2;
ans += t;
if (x + 1 >= k)
res += t;
q.push({x + 1, t});
}
cout << ans << ' ' << res << endl;
}D – 小红的神秘密码解锁
算法：
贪心，递推。
思路：
经典转换：块的个数为 \(s[i] != s[i – 1]\) 的个数。
选择左端点 \(l\)：
- 如果 \(s[l] != s[l – 1]\)，翻转后 \(s[l] = s[l – 1]\)，块个数 \(-1\)，为配平个数，需要选择 \(s[r] = s[r + 1]\)，其在翻转后 \(s[r] != s[r + 1]\)，块个数 \(+1\)；
- 如果 \(s[l] = s[l – 1]\)，翻转后 \(s[l] != s[l – 1]\)，块个数 \(+1\)，为配平个数，需要选择 \(s[r] != s[r + 1]\)，其在翻转后 \(s[r] = s[r + 1]\)，块个数 \(-1\)；
- 如果 \(l = 1\)，其翻转后块个数不变，不难发现只有 \(r = n\) 时，才能与之匹配。
实现：
- 为简化操作实现，固定 \(r\)，找 \(l\)，\(l\) 可以由两个变量递推而来，具体看实现。
关键代码：
void miyan()
{
string s;
cin >> s;
int n = s.size();
s = ' ' + s;
ll ans = 1;
ll cnt1 = 0, cnt2 = 0;
for (int i = 2; i <= n; ++i)
{
if (s[i] == s[i - 1])
{
ans += cnt2;
++cnt1;
}
else
{
ans += cnt1;
++cnt2;
}
}
cout << ans << endl;
}E – 小红的多维空间冒险
算法：
组合数学。
思路：
要计算距离恰好为 \(\sqrt{k}\) 的无序节点对数量，从位差异角度分析推导如下：
- 距离公式化简： 两个 \(n\) 维 0-1 节点 \(u, v\) 的距离为 \(\text{dist}(u,v) = \sqrt{\sum_{j=1}^n (u_j-v_j)^2}\)。 由于 \(u_j, v_j \in \{0,1\}\)，当 \(u_j \neq v_j\) 时，\((u_j-v_j)^2=1\)；当 \(u_j = v_j\) 时，该项为 \(0\)。 因此 \(\text{dist}(u,v) = \sqrt{k}\) 的充要条件是：\(u\) 和 \(v\) 恰好有 \(k\) 位取值不同。
- 满足条件的节点对计数：
- 固定节点 \(u\)，共有 \(2^n\) 种选择；
- 从 \(n\) 位中选 \(k\) 位取反得到与 \(u\) 恰有 \(k\) 位不同的节点 \(v\)，有 \(\mathrm{C}(n,k)\) 种选法；
- 初始计数 \(2^n \cdot \mathrm{C}(n,k)\) 中，无序节点对 \((u,v)\) 和 \((v,u)\) 被重复计算，需除以 \(2\) 去重。
- 最终结论： 对于每个 \(k\)（\(1 \le k \le n\)），距离恰好为 \(\sqrt{k}\) 的无序节点对数量为： \(\mathrm{ans}(k) = \mathrm{C}(n,k) \times 2^{n-1}\)
关键代码：
ll qmi(ll a, ll b, ll p)
{
ll ans = 1 % p;
while (b)
{
if (b & 1)
ans = ans * a % p;
a = a * a % p;
b >>= 1;
}
return ans;
}
ll inv(ll a, ll p)
{
return qmi(a, p - 2, p);
}
vector<ll> fact(N), invf(N), C(N);
void init(int n)
{
fact[0] = 1;
for (int i = 1; i <= n; ++i)
fact[i] = fact[i - 1] * i % MOD;
invf[n] = inv(fact[n], MOD);
for (int i = n - 1; i >= 0; --i)
invf[i] = invf[i + 1] * (i + 1) % MOD;
for (int i = 1; i <= n; ++i)
C[i] = fact[n] * invf[i] % MOD * invf[n - i] % MOD;
}
void miyan()
{
ll n;
cin >> n;
init(n);
ll ans = qmi(2, n - 1, MOD);
for (int i = 1; i <= n; ++i)
cout << ans * C[i] % MOD << ' ';
cout << endl;
}F – 小红的魔法树探险
算法：
\(dfs\)，数学期望。
思路：
数学期望定义为：
\(\mathbb{E}[X] = \sum_{i} x_i \cdot p_i\)
其中 \(x_i\) 为可能结果，\(p_i\) 为这个结果的概率。
考虑 \(dfs\) 计算树的期望：
- 对于点 \(u\)，到达该节点的概率为 \(p_u\)，其度为 \(deg_u\)，那么 \(u\) 点下一步到达的 \(v\) 点的概率为 \(\frac{p_u}{deg}\)；
- 设到达 \(u\) 点时其魔力消散，那么其 \(x_i\) 就为到达该点遍历到的节点个数；
- 那么对于一个点 \(u\)，其魔力消散时期望的贡献就为 \(x_i \cdot p_i\)，答案就为这些贡献的和；
- 具体实现看代码。
关键代码：
ll qmi(ll a, ll b, ll p)
{
ll ans = 1 % p;
while (b)
{
if (b & 1)
ans = ans * a % p;
b >>= 1;
a = a * a % p;
}
return ans;
}
ll inv(ll q, ll mod)
{
return qmi(q, mod - 2, mod);
}
void miyan()
{
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for (int i = 1; i < n; ++i)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int> st(n + 1, 0);
ll ans = 0;
auto dfs = [&](auto &&self, int u, ll x, ll p) -> void
{
if (st[u])
{
ans = (ans + (x - 1) * p % MOD) % MOD;
return;
}
st[u] = 1;
p = p * inv(g[u].size(), MOD) % MOD;
for (auto v : g[u])
{
self(self, v, x + 1, p);
}
};
dfs(dfs, 1, 1, 1);
cout << ans << endl;
}
