1981(div2)

A. Turtle and Piggy Are Playing a Game

乌龟和小猪在玩数字游戏。

首先，小乌龟会选择一个整数 $x$ ，使得 $l \leq x \leq r$ ，其中 $l, r$ 是给定的。还可以保证有 $2 l \leq r$ 。

然后，小猪会一直进行下面的运算，直到 $x$ 变成 $1$ ：

选择一个整数 $p$ ，使得 $p \geq 2$ 和 $p ∣ x$ （即 $x$ 是 $p$ 的倍数）。
将 $x$ 设为 $\frac{x}{p}$ ，得分将增加 $1$ 。

最初的得分是 $0$ 。小乌龟和小猪都想获得最高分。请帮助他们计算最高得分。

void solve() {
    int l, r;cin >> l >> r;
    cout << __lg(r) << '\n';
}

B. Turtle and an Infinite Sequence

有一个无限长的序列 $a_{0}, a_{1}, a_{2}, \dots$ 。最初的 $a_{i} = i$ 为每个非负整数 $i$ .

每过一秒，序列中的每个元素都会同时变化。每一个正整数 $i$ 的 $a_{i}$ 将变为 $a_{i - 1} ∣ a_{i} ∣ a_{i + 1}$ 。 $a_{0}$ 将变为 $a_{0} ∣ a_{1}$ 。

乌龟要找出 $m$ 秒后 $a_{n}$ 的值。特别是，如果 $m = 0$ ，那么他需要找到 $a_{n}$ 的初始值。他已经厌倦了计算这么多的值，请帮助他！

结果即为 $[max (0, n - m), n + m]$ 的二进制或。

void solve() {
    int n, m;cin >> n >> m;

    int l = max(n - m, 0), r = n + m;
    if (!m) {
        cout << n << '\n';return;
    }
    cout << (l | (1 << (__lg(l ^ r) + 1)) - 1) << '\n';

    // int ans = 0;
    // for (int i = 0;i <= 30;i++) {
    //     int a = l >> i;
    //     int b = r >> i;
    //     if (a & 1)ans |= 1 << i;
    //     if (a < b)ans |= 1 << i;
    // }
    // cout << ans << '\n';
}

C. Turtle and an Incomplete Sequence

补全 $a_{i} = - 1$ 的位置，使得对于从 $1$ 到 $n - 1$ 的每一个整数 $i$ ， $a_{i} = ⌊ \frac{a_{i + 1}}{2} ⌋$ 或 $a_{i + 1} = ⌊ \frac{a_{i}}{2} ⌋$ 都成立。若无解，则输出 $- 1$

这个题目可以算是大模拟或者思维题。

jiangly 思路：

先将两边的 $- 1$ 给补了，对于中间的若干个块，对于每个块，分别用 $i, j$ 代表 $[i + 1, j - 1]$ 区间都为 $- 1$ ，从两边到中间填充，若最终到中间了相邻两个不满足条件则输出 $- 1$ ，否则继续填充下一个块。

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (count(a.begin(), a.end(), -1) == n) {
        for (int i = 0; i < n; i++) {
            a[i] = i % 2 + 1;
        }
    } else {
        for (int i = 0, j = -1; i <= n; i++) {
            if (i == n || a[i] != -1) {
                if (j == -1) {
                    for (int k = i - 1; k >= 0; k--) {
                        a[k] = a[k + 1] == 1 ? 2 : a[k + 1] / 2;
                    }
                } else if (i == n) {
                    for (int k = j + 1; k < n; k++) {
                        a[k] = a[k - 1] == 1 ? 2 : a[k - 1] / 2;
                    }
                } else {
                    int l = j, r = i;
                    while (l + 1 < r) {
                        if (a[l] > a[r]) {
                            a[l + 1] = a[l] == 1 ? 2 : a[l] / 2;
                            l++;
                        } else {
                            a[r - 1] = a[r] == 1 ? 2 : a[r] / 2;
                            r--;
                        }
                    }
                    if (a[l] != a[r] / 2 && a[r] != a[l] / 2) {
                        cout << -1 << "\n";
                        return;
                    }
                }
                j = i;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }
}

官方题解：

将每次变换看作完全二叉树上的移动，则可以看作最短路问题，

$x \to y$ 的路径为 $x \to LCA (x, y) \to y$ ，设之间 $- 1$ 的个数为 $m$ ，若之间经过的节点数为 $l$ ，那么当 $l > m$ 或者 $l$ 和 $m$ 的奇偶性不同的时候无解，否则先将前面空闲的填了，之后两个数循环即可。

代码：
同样先把前后都填充了，然后对于每一个块，单独处理。

先计算出这个块两端的路线是怎样的。按照思路处理即可。

path 函数即在满二叉树上进行操作：

auto path = [](int x, int y)->vector<int> {
	vector<int> l, r;
	while (__lg(x) > __lg(y)) {
		l.push_back(x);x >>= 1;
	}
	while (__lg(y) > __lg(x)) {
		r.push_back(y);y >>= 1;
	}
	while (x != y) {
		l.push_back(x);
		r.push_back(y);
		x >>= 1;y >>= 1;
	}
	l.push_back(x);
	reverse(r.begin(), r.end());
	for (auto x : r)l.push_back(x);
	return l;
	};

void solve() {
    int n;cin >> n;
    vector<int> a(n + 1), v;
    int s = 0, e = 0;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        if (a[i] != -1) {
            if (!s)s = i;
            e = i;
            v.push_back(i);
        }
    }
    if (count(a.begin(), a.end(), -1) == n) {
        for (int i = 1;i <= n;i++) {
            cout << i % 2 + 1 << " \n"[i == n];
        }
        return;
    }
    for (int i = s - 1;i >= 1;i--) {
        a[i] = (a[i + 1] == 1) ? 2 : a[i + 1] / 2;
    }
    for (int i = e + 1;i <= n;i++) {
        a[i] = (a[i - 1] == 1) ? 2 : a[i - 1] / 2;
    }

    for (int i = 1;i < v.size();i++) {
        int l = v[i - 1], r = v[i];
        vector<int> p = path(a[l], a[r]);
        if ((p.size() & 1) != ((r - l + 1) & 1) || r - l + 1 < p.size()) {
            cout << "-1\n";return;
        }
        for (int j = 0;j < p.size();j++) {
            a[l + j] = p[j];
        }
        for (int j = l + p.size(), o = 1;j <= r;j++, o ^= 1) {
            a[j] = (o ? a[j - 1] * 2 : a[j - 1] / 2);
        }
    }

    for (int i = 1;i <= n;i++) {
        cout << a[i] << " \n"[i == n];
    }
}

D. Turtle and Multiplication

给一个整数 $n (2 \leq n \leq 10^{6})$ ，构造一个由满足以下条件的整数组成的数列 $a_{1}, a_{2}, \dots, a_{n}$ ：

对于所有 $1 \leq i \leq n$ ， $1 \leq a_{i} \leq 3 \cdot 10^{5}$ 。
对于所有 $1 \leq i < j \leq n - 1$ , $a_{i} \cdot a_{i + 1} \neq a_{j} \cdot a_{j + 1}$ .

在所有这些序列中，小猪要求乌龟找出具有最少个不同元素的序列。

Solution

欧拉路径/Hierholzer 算法

需要学习欧拉图相关知识, 注：这个部分比较冷门

欧拉图问题

要使得 $a_{i} \cdot a_{i + 1} \neq a_{j} \cdot a_{j + 1}$ ，只要 $a_{i}$ 都取素数。这样只要满足 $(a_{i}, a_{i + 1}), (a_{j}, a_{j + 1})$ 是不同的即可(即经过不重复的边)。

将 $(a_{i}, a_{i + 1})$ 看作是图的一条边，则问题变为找到点数最小的无向完全图(加上自环 $(a_{i} = a_{i + 1})$ )，使得这个图存在一条经过 $(n - 1)$ 条边且不经过重复边的路径。

若完全图的点数为 $m$ 。(这时确定了点数，需要使得边数尽可能大)

若 $m$ 为奇数，则每个点的度数都是偶数，则一定存在欧拉路径，路径则为边数 $\frac{m (m + 1)}{2}$
若 $m$ 为偶数，则每个点的度数都为奇数，这个时候需要删除一些边至少保证有欧拉通路，最多只能剩下两个奇数度数的点，所以至少要删除 $\frac{m}{2} - 1$ 条边，路径长度为 $\frac{m (m + 1)}{2} - \frac{m}{2} + 1 = \frac{m^{2}}{2} + 1$

若当 $n = 10^{6}$ 时， $m \approx 1415$ ，第 $m$ 个素数是 $11807 \leq 3 \times 10^{5}$ ，满足要求。

所以这时只需要确定最小的 $m$ ，再跑一遍欧拉通路即可。

对于最小的 $m$ ，满足：

m \equiv 1 (mod 2) {\begin{cases} n - 1 & \leq \frac{m (m + 1)}{2} \\ n - 1 & > \frac{(m - 1) m}{2} \end{cases} m \equiv 0 (mod 2) {\begin{cases} n - 1 & \leq \frac{m^{2}}{2} + 1 \\ n - 1 & > \frac{(m - 1)^{2}}{2} + 1 \end{cases}

代码：

void solve() {
    int n;
    cin >> n;

    int m = 1;
    while (n - 1 > (m % 2 == 1 ? m * (m + 1) / 2 : m * m / 2 + 1)) {
        m++;
    }

    vector<int> a;
    a.reserve(n);

    vector<vector<int>> g(m, vector<int>(m, 1));
    vector<int> cur(m);
    if (m % 2 == 0) {
        for (int i = 1; i < m - 1; i += 2) {
            g[i][i + 1] = g[i + 1][i] = 0;
        }
    }

    auto dfs = [&](auto&& self, int x) -> void {
        for (int& i = cur[x]; i < m; i++) {
            if (g[x][i]) {
                g[x][i] = g[i][x] = 0;
                self(self, i);
            }
        }
        a.push_back(primes[x]);
        };
    dfs(dfs, 0);

    a.resize(n);
    for (int i = 0; i < n; i++) {
        cout << a[i] << " \n"[i == n - 1];
    }
}

这里需要用到筛法；
!模板整理

E. Turtle and Intersected Segments

乌龟刚刚收到了 $n$ 个片段和 $a_{1}, a_{2}, \dots, a_{n}$ 个序列。第 $i$ 个片段是 $[l_{i}, r_{i}]$ 。

乌龟将创建一个无向图 $G$ 。如果图段 $i$ 和图段 $j$ 相交，那么乌龟将在 $i$ 和 $j$ 之间添加一条无向边，权重为 $| a_{i} - a_{j} |$ ，每 $i \neq j$ 。

Turtle 希望你计算图 $G$ 的最小生成树的边的权重之和，或者报告图 $G$ 没有生成树。

当且仅当 $max (l_{1}, l_{2}) \leq min (r_{1}, r_{2})$ 时，我们说两条线段 $[l_{1}, r_{1}]$ 和 $[l_{2}, r_{2}]$ 相交。

扫描线+最小生成树

(挖坑...)