D - Minimum number of steps

Description

将只含 $a$ 、 $b$ 的字符串中的 $ab$ 全部替换为 $bba$ 需要多少次操作

Solution

字符串最终会变为 $bbbb....aaa....$ 。将 $ab$ 替换为 $bba$ 后 $a$ 的个数不变，前面的结果对后面没有影响，所以 $b$ 前有多少 $a$ 就要操作 $2^{num_a} - 1$ 次。

Code

Minimum number of steps

using namespace std;

#define LL long long
#define MOD 1000000000 + 7

char str[1000005];

int main() {
    while (~scanf("%s", str)) {
        LL ans = 0, x = 1;
        for (int i = 0; str[i] != '\0'; i++) {
            if (str[i] == 'a') {
                x *= 2;
                x %= MOD;
            } else {
                ans += x - 1;
                ans %= MOD;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

E - Ice cream coloring

Description

题目链接

Solution

首先按照题意，同一个节点上的 $ice cream$ 构成完全图，它们必须染上不同的颜色。注意题目中有这样一句话：“Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph”，也就是说对于树上的一个节点 $u$ ，与其相邻的节点才有和它相同的 $ice cream$ ，否则会产生环，那么树上 $dfs$ 染色不会产生染色冲突。
如何染色：对于一个树上节点，从 1 开始将这个节点上的 $ice cream$ 染色，如果某种类型的 $ice cream$ 被染过色则跳过(可用 $std::set$ 等判断)。最后没有被染色的 $ice cream$ 的颜色都赋为 1。

Code

Ice cream coloring

#include <bits/stdc++.h>

using namespace std;

constexpr int MAXN = 3e5 + 5;

int n, m, c[MAXN], cnt = 1;
vector<int> G[MAXN], s[MAXN];

void dfs(int cur, int fa) {
    int color = 1;

    set<int> tmp;
    for (auto& i : s[cur])
        if (c[i]) tmp.insert(c[i]);
    
    for (auto& i : s[cur]) {
        if (c[i]) continue;
        while (tmp.count(color)) color++;
        c[i] = color++;
        cnt = max(cnt, c[i]);
    }

    for (auto& to : G[cur]) {
        if (to == fa) continue;
        dfs(to, cur);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int sz;
        cin >> sz;
        for (int j = 1; j <= sz; j++) {
            int tmp;
            cin >> tmp;
            s[i].push_back(tmp);
        }
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; i++)
        if (!c[i]) c[i] = 1;
    cout << cnt << "\n";
    for (int i = 1; i <= m; i++) cout << c[i] << " ";
    return 0;
}

F - Expected diameter of a tree

Description

给出一个森林，m 次询问，每次给出节点 $a$ , $b$ ，将 $a$ 所在的树与 $b$ 所在的树连一条边，求连接后的树的直径的期望(每次操作相互独立)。

Solution

先预处理出每个点属于哪一棵树，每棵树的 $size$ 、直径，以及树上每个点到最远点的距离 (可以证明，树上一点的最远点一定是树的直径的端点)。

可以二次 $dfs$ 求出树的直径和端点，再从端点出发，求出到每一点的最远距离 $dis[]$ 。

然后枚举 $a$ 所在树的点 $i$ ，二分 $b$ 所在树的点 $j$ ，求出 $dis_i + dis_j + 1 > max(diameter_{belong_i}, diameter_{belong_j})$ (需要提前将 $dis[]$ 排序)。

然后小于 $j$ 的部分，树的直径都是 $max(diameter_{belong_i}, diameter_{belong_j})$ ，剩余部分的直径和通过前缀和求出 (前缀和需要 $dis[]$ 排序后预处理)。

但这样的时间复杂度为 $O(nmlog_n)$ ，可用 $map$ 记忆化，时间复杂度 $O(m\sqrt{n}log_n)$ (按两个块中小的那一个块的大小大于 $\sqrt{n}$ 和小于 $\sqrt{n}$ 讨论一下即可)。

Code

Expected diameter of a tree

#include <bits/stdc++.h>
 
using namespace std;
 
constexpr int MAXN = 3e5 + 5;
 
int n, m, q, diameter;
array<int, MAXN> sz, belong, dis, dia;
vector<int> G[MAXN], vec[MAXN];
vector<long long> sum[MAXN];

void dfs1(int cur, int fa, int& p) { //二次 dfs 求直径 p 是端点
    for (auto& to : G[cur]) {
        if (to == fa) continue;
        dis[to] = dis[cur] + 1;
        if (dis[to] > diameter) diameter = dis[to], p = to;
        dfs1(to, cur, p);
    }
}
 
void dfs2(int cur, int fa, int tot) { //求树的 sz，以及每个节点属于哪一棵树
    sz[tot]++, belong[cur] = tot;
    for (auto& to : G[cur]) {
        if (to == fa) continue;
        dfs2(to, cur, tot);
    }
}
 
void dfs3(int cur, int fa, int d) { //求点到最远点的距离
    dis[cur] = max(dis[cur], d);
    for (auto& to : G[cur]) {
        if (to == fa) continue;
        dfs3(to, cur, d + 1);
    }
}
 
map<pair<int, int>, double> mp;
void query(int u, int v) {
    if (u == v) {
        cout << "-1\n";
        return;
    }
    if (sz[u] > sz[v]) swap(u, v);
 
    if (mp.count({u, v})) {
        cout << mp[{u, v}] << "\n";
        return;
    }
    double res = 0;
    int tmp = max(dia[u], dia[v]);
    for (auto& i : vec[u]) {
        int pos = upper_bound(vec[v].begin(), vec[v].end(), tmp - 1 - i) - vec[v].begin();
        res += 1LL * tmp * pos;
        res += 1LL * (i + 1) * (sum[v].size() - pos);
        res += sum[v][sum[v].size() - 1] - (pos ? sum[v][pos - 1] : 0);
    }
    res /= 1LL * sz[u] * sz[v];
    cout << (mp[{u, v}] = res) << "\n";
}
 
void init() {
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        if (!belong[i]) {
            int st = i, ed = i;
            diameter = 0, dis[i] = 0, dfs1(i, 0, st);
            diameter = 0, dis[st] = 0, dfs1(st, 0, ed);
            dfs2(i, 0, ++tot), dia[tot] = diameter;
            dfs3(st, 0, 0), dfs3(ed, 0, 0); //预处理出直径、dis
        }
    }
    for (int i = 1; i <= n; i++) vec[belong[i]].push_back(dis[i]);
    for (int i = 1; i <= tot; i++) { //排序求前缀和
        sort(vec[i].begin(), vec[i].end());
        sum[i].resize(vec[i].size());
        sum[i][0] = vec[i][0];
        for (int j = 1; j < vec[i].size(); j++)
            sum[i][j] = sum[i][j - 1] + vec[i][j];
    }
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cout << setprecision(6) << fixed;
    cin >> n >> m >> q;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    init();
    for (int i = 1, u, v; i <= q; i++) {
        cin >> u >> v;
        query(belong[u], belong[v]);
    }
    return 0;
}