350

A - Past ABCs

判断 S 是否是在本次比赛开始之前在 AtCoder 上举行并结束的比赛的缩写。

void solve() {
    string s;cin >> s;
    int x = stoi(s.substr(3, 3));
    if (x != 316 && x <= 349&&x>=1)cout << "Yes\n";else cout << "No\n";
}

B - Dentist Aoki

void solve() {
    int n, q;cin >> n >> q;vector<int> a(n + 1);
    for (int i = 1;i <= q;i++) {
        int x;cin >> x;a[x]++;
    }
    int cnt = n;
    for (int i = 1;i <= n;i++) {
        if (a[i]) {
            if (a[i] % 2) {
                cnt--;
            }
        }
    }
    cout << cnt << '\n';
}

C - Sort

给你一个 $(1, 2, \dots, N)$ 的排列组合 $A = (A_{1}, \dots, A_{N})$ 。
请在 $0$ 和 $N - 1$ 之间（包括首尾两次）进行以下运算，将 $A$ 变换为 $(1, 2, \dots, N)$ ：

运算：选择任意一对整数 $(i, j)$ ，使得 $1 \leq i < j \leq N$ .交换 $A$ 的 $i$ -th 和 $j$ -th 位置上的元素。

可以证明，在给定的约束条件下，总是可以把 $A$ 变换成 $(1, 2, \dots, N)$ 。

这是我第二次遇到这个题目，和上次犯了一样的错误，不知道更新 mp

void solve() {
    int n;cin >> n;vector<int> a(n + 1);map<int, int>mp;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];mp[a[i]] = i;
    }
    vector<pair<int, int>> s;
    for (int i = 1;i <= n;i++) {
        if (a[i] != i) {
            mp[a[i]] = mp[i];
            swap(a[i], a[mp[i]]);
            s.emplace_back(i, mp[i]);
            mp[i] = i;
        }
    }
    cout << s.size() << '\n';
    for (auto [x, y] : s)cout << x << " " << y << '\n';
}

D - New Friends

有一个由 $N$ 用户使用的 SNS，标有从 $1$ 到 $N$ 的编号。

在这个 SNS 中，两个用户可以互相成为**好友。
好友关系是双向的；如果用户 X 是用户 Y 的好友，则用户 Y 始终是用户 X 的好友。

目前，SNS 上有 $M$ 对好友关系，其中 $i$ 对由用户 $A_{i}$ 和 $B_{i}$ 组成。

请确定以下操作的最大执行次数：

操作：选择三个用户 X、Y 和 Z，使得 X 和 Y 是好友，Y 和 Z 是好友，但 X 和 Z 不是好友。让 X 和 Z 成为好友。

这个题目一眼就可看出答案: 对于每个连通块：连通块的大小*(连通块大小-1)/2-连通块的边数。
令连通块为 $Connected-Block \to C$ ，大小： $size()$ 边数： $edge_num$

即： $\frac{1}{2} \sum C.size()*(C.size()-1)-edge_num$

#define int long long
void solve() {
    int n, m;cin >> n >> m;vector<vector<int>>g(n + 1);
    vector<int> vis(n + 1);
    for (int i = 1;i <= m;i++) {
        int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);
    }
    int ans = 0, res = 0, cnt = 0;

    auto dfs = [&](auto self, int v) ->void {
        vis[v] = 1;res++;
        cnt += g[v].size();
        for (auto i : g[v]) {
            if (vis[i])continue;
            self(self, i);
        }
        };

    for (int i = 1;i <= n;i++) {
        if (!vis[i]) {
            res = 0, cnt = 0;
            dfs(dfs, i);
            ans += res * (res - 1) / 2 - cnt / 2;
        }
    }
    cout << ans << '\n';
}

E - Toward 0

给你一个整数 $N$ 。您可以进行以下两种运算：

支付 $X$ 日元，将 $N$ 替换为 $⌊ \frac{N}{A} ⌋$ 。
支付 $Y$ 日元，掷出一个骰子（骰子），该骰子以相等的概率显示一个介于 $1$ 和 $6$ 之间的整数。让 $b$ 成为掷骰子的结果，用 $⌊ \frac{N}{b} ⌋$ 代替 $N$ 。

这里， $⌊ s ⌋$ 表示小于或等于 $s$ 的最大整数。例如， $⌊ 3 ⌋ = 3$ 和 $⌊ 2.5 ⌋ = 2$ 。

求在最优化选择操作时， $N$ 变为 $0$ 之前支付的最小预期成本。
每次操作的掷骰子结果与其他掷骰子结果无关，可以在观察前面操作的结果后选择操作。

Solution

期望/记忆化搜索

这个问题可以通过记忆化递归来解决。

问题 1

首先考虑下面的问题。

设置与原始问题相同。但是，操作只有一种。

支付 Y 日元。掷一个骰子，结果是一个从 2 到 6 的整数，等概率出现。将 N 替换为 $⌊ \frac{N}{b} ⌋$ 。

我们将期望值记为 $f (N)$ 。这样，

$f (N) = Y + \frac{1}{5} f (⌊ \frac{N}{2} ⌋) + \frac{1}{5} f (⌊ \frac{N}{3} ⌋) + \frac{1}{5} f (⌊ \frac{N}{4} ⌋) + \frac{1}{5} f (⌊ \frac{N}{5} ⌋) + \frac{1}{5} f (⌊ \frac{N}{6} ⌋)$

因此，我们可以通过记忆化递归来计算。（关于计算复杂度，稍后会提到）

问题 2

接下来考虑下一个问题。

设置与原始问题相同。但是，操作只有一种。

支付 Y 日元。掷一个骰子，结果是一个从 1 到 6 的整数，等概率出现。将 N 替换为 $⌊ \frac{N}{b} ⌋$ 。

我们将期望值记为 $f (N)$ 。这样，

$f (N) = Y + \frac{1}{6} f (⌊ \frac{N}{1} ⌋) + \frac{1}{6} f (⌊ \frac{N}{2} ⌋) + \frac{1}{6} f (⌊ \frac{N}{3} ⌋) + \frac{1}{6} f (⌊ \frac{N}{4} ⌋) + \frac{1}{6} f (⌊ \frac{N}{5} ⌋) + \frac{1}{6} f (⌊ \frac{N}{6} ⌋)$

右边也包含了 $f (N)$ ，看起来无法通过递归计算，但我们可以通过将左边移项并乘以 $\frac{6}{5}$ 来得到

$f (N) = \frac{6}{5} Y + \frac{1}{5} f (⌊ \frac{N}{2} ⌋) + \frac{1}{5} f (⌊ \frac{N}{3} ⌋) + \frac{1}{5} f (⌊ \frac{N}{4} ⌋) + \frac{1}{5} f (⌊ \frac{N}{5} ⌋) + \frac{1}{5} f (⌊ \frac{N}{6} ⌋)$

因此，我们可以通过记忆化递归来计算。（关于计算复杂度，稍后会提到）

原始问题

考虑原始问题。将期望值记为 $f (N)$ 。由于有 2 种操作，我们选择较小的期望值是最优的。

$f (N) = min (X + f (⌊ \frac{N}{A} ⌋), \frac{6}{5} Y + \frac{1}{5} f (⌊ \frac{N}{2} ⌋) + \frac{1}{5} f (⌊ \frac{N}{3} ⌋) + \frac{1}{5} f (⌊ \frac{N}{4} ⌋) + \frac{1}{5} f (⌊ \frac{N}{5} ⌋) + \frac{1}{5} f (⌊ \frac{N}{6} ⌋))$

因此，我们可以通过记忆化递归来计算。

为了计算 $f (N)$ ，我们需要注意 $⌊ \frac{⌊ \frac{N}{a} ⌋}{b} ⌋ = ⌊ \frac{N}{a b} ⌋$ ，因此 f (N) 只出现在能够写成 $m = 2^{p} 3^{q} 5^{r}$ 的整数 m 的地方。

这样的 m 最多有 $O ((\log N)^{3})$ 个，因此总体计算复杂度为 $O ((\log N)^{3})$ 。

摘要

与官方解释相同，我们将寻找的期望值记为 $f (N)$ 。另外，问题中的两种操作分别称为操作 A 和操作 B。

如果直接对原问题进行模型建立，可以得到以下方程：

f (N) = min (X + f (⌊ \frac{N}{A} ⌋), Y + \frac{1}{6} \sum_{i = 1}^{6} f (⌊ \frac{N}{i} ⌋)) .

在官方解释中可能有些含糊，但是由于存在 $min$ ，不能简单地通过代数变换去除右边的 $f (N)$ 。

因此，我们可以将问题中的两种操作替换为以下两种操作，以便更容易讨论。通过这种替换，我们可以得到与官方解释相同的方程。

支付 $X$ 日元。将 $N$ 替换为 $⌊ N / A ⌋$ 。（不变）
“支付 $Y$ 日元，掷一个均匀分布的骰子，直到出现 2 到 6 之间的整数为止”。将出现的整数 $b$ 用于将 $N$ 替换为 $⌊ N / b ⌋$ 。

如果操作 B 是最小化期望值的最佳操作，则即使进行操作 A，也不会带来额外收益。因此，即使通过上述替换，期望值也不会改变。

后一操作的期望值

关于后一操作的期望值，我们可以通过以下方法进行建模。

直到出现 2 以上的数为止所支付的金额的期望值

掷骰子 $i \geq 1$ 次并且直到出现 2 以上的数的概率，即第 $i$ 次仍然支付 $Y$ 日元掷骰子的概率为 $(1 / 6)^{i - 1}$ 。因此支付金额的期望值如下：

\sum_{i = 1}^{\infty} Y \cdot {(\frac{1}{6})}^{i - 1} = \frac{6}{5} Y .

参考：无穷等比数列的收敛和发散条件以及证明等 | 高中数学优美物语

a + a r + a r^{2} + \dots = \frac{a}{1 - r} (- 1 < r (Common radio) < 1)

出现 2 以上的数后的期望值

以 $1 / 5$ 的概率， $N$ 可以被替换为 $⌊ N / 2 ⌋, ⌊ N / 3 ⌋, ⌊ N / 4 ⌋, ⌊ N / 5 ⌋, ⌊ N / 6 ⌋$ 中的一个。因此，期望值为：

\frac{1}{5} \cdot f (⌊ \frac{N}{2} ⌋) + \frac{1}{5} \cdot f (⌊ \frac{N}{3} ⌋) + \frac{1}{5} \cdot f (⌊ \frac{N}{4} ⌋) + \frac{1}{5} \cdot f (⌊ \frac{N}{5} ⌋) + \frac{1}{5} \cdot f (⌊ \frac{N}{6} ⌋) .

将上述两个期望值相加，得到的结果与官方解释中 $min$ 内的第二项相匹配。

Code

转移方程：

#define int long long
map<int, double>mp;
int a, x, y;
double f(int n) {
    if (!n)return 0;
    if (mp.count(n))return mp[n];
    return mp[n] = min(x + f(n / a), 1.2 * y + 0.2 * (f(n / 2) + f(n / 3) + f(n / 4) + f(n / 5) + f(n / 6)));
}
void solve() {
    int n;cin >> n >> a >> x >> y;
    printf("%.10f", f(n));
}

F - Transpose

给你一个由大写和小写英文字母 (, 和 ) 组成的字符串 $S = S_{1} S_{2} S_{3} \dots S_{| S |}$ 。
字符串 $S$ 中的小括号已正确匹配。

重复下面的操作，直到不能再进行操作为止：

首先，选择一对满足以下所有条件的整数 $(l, r)$ ：
- $l < r$ , $S_{l} =$ (, $S_{r} =$ )
- 每个字符 $S_{l + 1}, S_{l + 2}, \dots, S_{r - 1}$ 都是大写或小写英文字母。
设为 $T = \overset{―}{S_{r - 1} S_{r - 2} \dots S_{l + 1}}$ 。
- 这里， $\overset{―}{x}$ 表示通过切换 $x$ 中每个字符的大小写（大写变为小写，反之亦然）得到的字符串。
然后，删除 $S$ 中的 $l$ 至 $r$ 字符，并在删除位置插入 $T$ 。

可以证明，使用上述操作可以删除字符串中的所有 ( s 和 ) s，而且最终的字符串与操作的方式和顺序无关。
确定最终字符串。

Solution

字符串翻转的技巧/splay (平衡二叉查找树)

暴力： $O (n^{2})$

void solve() {
    string s;cin >> s;stack<int> l;
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '(') {
            l.push(i);
        } else if (s[i] == ')') {
            int x = l.top();l.pop();
            reverse(s.begin() + x, s.begin() + i);
            for (int j = x;j < i;j++) s[j] = isupper(s[j]) ? tolower(s[j]) : toupper(s[j]);
        }
    }
    for (int i = 0;i < s.size();i++) {
        if (s[i] != '(' && s[i] != ')') {
            cout << s[i];
        }
    }
}

关键是在于如何将字符串更加高效率的翻转和大小写转化

此时需要记录每次与该括号匹配的位置，分左括号和右括号进行搜索，复杂度 $O (n)$

void solve() {
    string s;cin >> s;stack<int> l;
    vector<int> match(s.size(), -1);
    for (int i = 0;i < s.size();i++) {
        if (s[i] == '(') {
            l.push(i);
        } else if (s[i] == ')') {
            match[i] = l.top();
            match[l.top()] = i;l.pop();
        }
    }
    string ans;
    auto dfs = [&](auto self, int l, int r, bool rev)->void {
        if (!rev) {
            for (int i = l;i < r;i++) {
                if (s[i] == '(') {
                    self(self, i + 1, match[i], true);
                    i = match[i];
                } else {
                    ans += s[i];
                }
            }
        } else {
            for (int i = r - 1;i >= l;i--) {
                if (s[i] == ')') {
                    self(self, match[i] + 1, i, false);
                    i = match[i];
                } else {
                    ans += (s[i] = isupper(s[i]) ? tolower(s[i]) : toupper(s[i]));
                }
            }
        }
        };
    dfs(dfs, 0, s.size(), false);
    cout << ans << '\n';
}