340

A - Arithmetic Progression

给出等差数列的 $a_1,a_n,d$，给出这个数列

void solve() {
    int a, b, d;
    cin >> a >> b >> d;
    for (int i = a;i <= b;i += d) {
        cout << i << " ";
    }
}

B - Append

你有一个空序列 $A$。给出了 $Q$ 个查询，你需要按照给出的顺序处理它们。这些查询有以下两种类型：

• 1 x：将 $x$ 追加到 $A$ 的末尾。
• 2 k: 从 $A$ 的末尾找到 $k$ 的值。当给出这个查询时，可以保证 $A$ 的长度至少是 $k$。

void solve() {
    int q;cin >> q;
    vector<int> a;
    while (q--) {
        int op;cin >> op;
        if (op == 1) {
            int x;cin >> x;
            a.push_back(x);
        } else {
            int k;cin >> k;
            cout << a[a.size()  - k] << '\n';
        }
    }
}

C - Divide and Divide

给出一个 $N(2\le N\le {10}^{17})$

重复下面的一系列操作，直到所有不小于 $2$ 的整数都从黑板上移除：

可以证明，无论操作的顺序如何，他支付的总金额是不变的。

• 选择写在黑板上的一个不小于 $2$ 的整数 $x$。
• 擦去黑板上出现的一个 $x$。然后，在黑板上写下两个新的整数 $\lfloor {\displaystyle \frac{x}{2}}\rfloor$ 和 $\lceil {\displaystyle \frac{x}{2}}\rceil$。
• 高桥必须支付 $x$ 日元才能完成这一系列操作。

当不能再进行操作时(即全部都是 1)，高桥支付的总金额是多少？

Solution

坑点：

• ceil (n*1.0/2) 有精度误差最好换成 (n+1)/2
• 数据较大时，不要使用 pow() 函数，有精度丢失，肯定会 wa，更推荐快速幂

本来我的思路是写一个递推: f[n]=f[n/2]+f[(n+1)/2]+n (但是由于 $N$ 实在太大了，存不下)

注意到一个有趣的规律(是可行的)：

设 $2^k\le n-1$ ($k=k_{max}$ ) 则答案形式:

$2\times 2^0+3\times 2^1+4\times 2^2+5\times 2^3+\cdots +(k+1)\times 2^{k-1}+[(k+2)\times 2^k]+(n-2^k)\times (k+2)$

void solve() {
    ll n, k = -1;cin >> n;
    for (ll i = 1;i < n;i += qpow(2, k))k++;
    ll ans = 0;
    for (ll i = 0;i < k;i++) {
        ans += (i + 2) * qpow(2, i);
    }
    ans += (n - qpow(2, k)) * (k + 2);
    cout << ans << '\n';
}

递归的话，需要存储一下 (记忆化搜索)

(PS: 学会 lambda 表达式的递归调用(可以看 Jiangly ))

#define int long long
unordered_map<int, int> memo;
int f(int n) {
    if (n == 1) return 0;
    if (memo.count(n)) return memo[n];
    return memo[n] = f(n / 2) + f(((n + 1) / 2)) + n;
}

unordered_map 也可以换为 map

D - Super Takahashi Bros.

游戏由编号为 $1,2,\dots ,N$ 的 $N$ 个阶段组成。最初，只有阶段 $1$ 可以玩。

对于每个可以下棋的阶段 $i$ ( $1\le i\le N-1$ )，你都可以在阶段 $i$ 执行以下两个操作中的一个：

• 花费 $A_i$ 秒清除阶段 $i$。进入 $i+1$ 阶段。
• 花费 $B_i$ 秒清除阶段 $i$。进入 $X_i$ 阶段。

忽略通关时间以外的其他时间，至少需要多少秒才能进入关卡 $N$？

Solution

最短路

求从 1-n 的最短路。用的邻接表存图

#define int long long
#define pll pair<int,int>
void solve() {
    int n;cin >> n;
    vector<pll> e[n + 1];
    vector<ll> dis(n + 1, INTMAX_MAX), vis(n + 1, 0);
    for (int i = 1;i < n;i++) {
        int a, b, x;cin >> a >> b >> x;
        e[i].push_back({i + 1,a});
        e[i].push_back({x,b});
    }
    priority_queue<pll>q;
    q.push({0,1});
    dis[1] = 0;
    while (q.size()) {
        auto u = q.top().second;q.pop();
        if (vis[u])continue;
        vis[u] = 1;
        for (auto [v, w] : e[u]) {
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                q.push({-dis[v],v});
            }
        }
    }
    cout << dis[n] << ' ';
}

E - Mancala 2

有 $N$ 个编号为 $0$ 至 $N-1$ 的盒子。最初，$i$ 盒里有 $A_i$ 个球。

高桥将依次对 $i=1,2,\dots ,M$ 进行以下操作：

• 将变量 $C$ 设为 $0$。
• 从盒子 $B_i$ 中取出所有的球并握在手中。
• 在手拿至少一个球的同时，重复下面的过程：
  • 将 $C$ 的值增加 $1$。
  • 将手中的一个球放入盒子 $(B_i+C)modN$。

完成所有操作后，确定每个盒子中的球数。

Solution

线段树(待更 $\dots$)

我本来是想用差分来做：先记录本来 $a[b[i]]$ 与 $n$ 的关系，倍数部分 $0-(n-1)$ 都加 1 即 $dif[0]+=1$，对于余数部分在 $a[b[i]]$ 后面 $a[b[i]]\mathrm{\%}n$ 个数加 1，关键在于在变化过程中 $a[i]$ 数组在变化，$dif[i]$ 数组需要随时更新，所以我感觉是不可行的。

区间修改一般还是线段树

官方题解：

考虑将 N 个球放入箱子的操作，该过程可以重新表述如下：

• 从箱子 $B_i$ 中取出所有的球并拿在手中。
• 让 $X$ 表示手中的球的数量。将 $\lfloor \frac{X}{N}\rfloor$ 个球放入每个箱子中。
• 让 $X$ 表示手中剩余的球的数量。将一个球放入箱子 $B_i+1$ 到箱子 $B_i+X$ 中。
  （如果 $B_i+X\ge N$，“箱子 $B_i+1$ 到箱子 $B_i+X$”表示箱子 $B_i+1$ 到箱子 $N-1$，以及箱子 $0$ 到箱子 $B_i+X-N$。)

必须对表示每个箱子中球数量的数组进行点更新和段增加等操作。使用类似懒惰段树的数据结构，它们可以在 $O(\log N)$ 的时间内处理，总共可以在 $O((M+N)\log N)$ 的时间内解决整个原始问题。

待我学习线段树 $\dots$

F - S = 1

给你整数 $X$ 和 $Y$ ($x,y$ 不同时为 $0$)。
请找出一对满足以下所有条件的整数 $(A,B)$。不存在则输出 -1。

• $-{10}^{18}\le A,B\le {10}^{18}$
• 顶点位于 $xy$ 平面上点 $(0,0),(X,Y),(A,B)$ 的三角形的面积为 $1$.

Solution

易得：$(X,Y),(A,B)$ 构成的直线方程：$(Y-B)x-(X-A)y+BX-AY=0$

则到 $(0,0)$ 的距离为：$\frac{\mid BX-AY\mid }{\sqrt{(x-a{)}^2+(y-b{)}^2}}$

则三角形的面积：$\frac{\mid BX-AY\mid }{2}=1$

$\to \mid BX-AY\mid =2$

设 $g=gcd(X,Y)$。（注意：$gcd(a,b)$ 定义为 $|a|$ 和 $|b|$ 的最大公约数。）

扩展欧几里得算法，给定一个整数对 $(a,b)$ 作为输入，找到一个整数对 $(x,y)$，使得 $ax+by=\pm \gcd (a,b)$，时间复杂度为 $\mathrm{O}(\log min(|a|,|b|))$。（这里，整数对 $x,y$ 保证是满足 $max(|x|,|y|)\le max(|a|,|b|)$ 的整数。）

通过将 $(Y,-X)$ 作为扩展欧几里得算法的输入，可以获得一对 $(c,d)$，找到 $\mid cY-dY\mid =g$ 的一组可行整数解

将 $(c,d)\times \frac{2}{g}\to \mid AY-BY\mid =2$ $,g\le 2$ (保证 $\frac{2}{g}$ 是整数)

pair<ll, ll> extgcd(ll a, ll b) {
    if (!b) return {1, 0};
    ll x, y;
    tie(y, x) = extgcd(b, a % b);
    y -= a / b * x;
    return {x, y};
}
void solve() {
    ll x, y;cin >> x >> y;
    if (abs(__gcd(x, y)) > 2) {
        cout << "-1\n";return;
    }
    auto [c, d] = extgcd(y, -x);
    c *= 2 / abs(__gcd(x, y)), d *= 2 / abs(__gcd(x, y));
    cout << c << " " << d << '\n';
}

G - Leaf Color

有一棵树 $T$ 有 $N$ 个顶点，编号从 $1$ 到 $N$。连接顶点 $u_i$ 和 $v_i$ 的是 $i$ 边。此外，顶点 $i$ 被涂上了颜色 $A_i$。
求满足以下条件的顶点集合 $T$ 的（非空）子集 $S$ 的个数，以 $998244353$ 为模：

• $T$ 的子图 $G$ 由 $S$ 引导，满足以下所有条件：
  • $G$ 是一棵树。
  • 所有阶数为 $1$ 的顶点颜色相同。

什么是诱导子图？假设 $S$ 是图 $G$ 的一个顶点子集。$G$ 的诱导子图 $S$ 是一个顶点集为 $S$，边集由 $G$ 中所有端点都在 $S$ 中的边组成的图。

Solution

虚数(辅助树)+DP

(待更 $\dots$)

G_哔哩哔哩_bilibili

官方题解：

这个问题有几种解决方案；在这篇社论中，我们介绍一种叫做辅助树的技术。

本社论的方法

我们首先解释解决这个问题的方法。
固定度为 1 的顶点的颜色 $c$。然后可以用树 DP（动态规划）以 $\mathrm{O}(N)$ 的时间解决固定颜色的问题。（虽然不容易，但对于蓝色编程者来说是一个很好的练习，所以我们建议你思考一下。）然而，解决所有颜色的问题需要 $\mathrm{O}(N^2)$ 的时间，这会导致超时错误（Time Limit Exceeded，TLE）。
固定颜色 $c$ 的问题所需的时间为 $\mathrm{O}(N)$，因为树有 $N$ 个顶点，实际上包括一些本质上不必要的顶点，比如永远不会使用的顶点；在为颜色 $c$ 执行 DP 时关心这些顶点是浪费时间。我们能否以某种方式压缩树呢？
考虑一下在压缩时我们需要保留哪些顶点。除了颜色为 $c$ 的顶点外，似乎有必要保留作为颜色为 $c$ 的顶点的 LCA（最低公共祖先）的顶点。（在这里，我们把树 $T$ 视为以顶点 $1$ 为根的有根树。）当这些顶点被选择后，就在每对祖先-后裔顶点之间添加一条边，这样左边的树就变成了下面的右边的树。我们似乎可以在右侧的树上执行 DP。

（图示：当顶点 $6,7,8,14$ 和 $15$ 被涂上颜色 $c$ 时的压缩）

我们把通过压缩树保持指定顶点的 LCA 关系而得到的树称为通过压缩树获得的辅助树。（这在日本和中国等地通常称为辅助树、虚拟树或压缩树。在这篇社论中，我们简单地称之为辅助树。）

• 关于这个树的名字，也可以参考以下文章。Auxiliary Tree に関する Kyopro Encyclopedia of Algorithms の記事（“竞赛编程”算法百科全书中关于辅助树的日文文章）

辅助树的性质

辅助树的正式定义如下。给定一个有根树 $T$ 和一个顶点集 $X$，辅助树是一个顶点集 $A(X)$，其中

并且在 $T$ 中存在一对顶点，其中一个是另一个的祖先。

我们介绍辅助树的一个性质。

性质 1

$|A(X)|\le 2|X|-1$。

（证明）对树 $T$ 的 DFS（深度优先搜索）进行任意一种先序遍历。设 $x_1,x_2,\dots ,x_m$ 是按先序排列的 $X$ 中的顶点。
设 $l=\mathrm{lca}(x_1,x_2)$；那么我们有以下事实：

引理 1

对于大于或等于 3 的整数 $n$，如果 $\mathrm{lca}(x_1,x_n)\ne l$，那么 $\mathrm{lca}(x_1,x_n)=\mathrm{lca}(x_2,x_n)$。

（引理证明）我们用反证法证明。假设存在 $n$ 使得 $\mathrm{lca}(x_1,x_n)\ne l$ 且 $\mathrm{lca}(x_1,x_n)\ne \mathrm{lca}(x_2,x_n)$。如果 $\mathrm{lca}(x_1,x_n)=m$，那么 $m$ 是 $l$ 的后代或祖先，但如果是祖先，那么 $\mathrm{lca}(x_1,x_n)=\mathrm{lca}(x_2,x_n)=m$，这是不会发生的。所以 $m$ 是 $l$ 的后代，但是这样一来，先序应该按照以下顺序出现：$x_1,x_n,x_2$。这违反了 $x$ 的定义。因此，这是一个矛盾。（引理证明结束）

正如引理所示，$\mathrm{lca}(x_1,x_n)$ 是下列之一：（1）$x_1$ 本身，（2）$\mathrm{lca}(x_1,x_2)$，和（3）$\mathrm{lca}(x_2,x_n)$。因此，$A(x)$ 可以表示为

这个方程意味着

通过对顶点集大小进行归纳，可以证明 $|A(X)|\le 2|X|-1$。（证明结束）

此性质意味着辅助树有 $\mathrm{O}(|X|)$ 个顶点，可以由指定的顶点集大小乘以一个常数来限制。我们利用这一事实来减少原问题的计算复杂度。

辅助树的构造

给定一个顶点集 $X$，可以在 $\mathrm{O}(|X|(\log |X|+\log N))$ 的时间内构造辅助树（如果原始树有 $N$ 个顶点的话，还需要对树 $T$ 进行 $\mathrm{O}(N\log N)$ 的预计算）。

我们解释一下构造的过程。我们利用以下性质：

性质 2 对树 $T$ 的 DFS 进行任意一种先序遍历。设 $x_1,x_2,\dots ,x_m$ 是按先序排列的 $X$ 中的顶点。
那么 $A(X)$ 有以下属性：

$$A(X)=X\cup \{\mathrm{lca}(x_i,x_{i+1})|1\le i<m\}.$$

（证明）

利用上面性质 1 的证明中展示的方程

​)}​

，得出

这就是我们想要的。（证明结束）

利用性质 2，可以按照如下方式构造 $A(X)$ 的顶点集的先序遍历：

• 预先计算加倍或 HLD（重链剖分），以便快速得到 $T$ 上任意两个顶点的 LCA。
• 取 $X$ 中顶点的先序遍历 $x_1,x_2,\dots ,x_m$。
• 得到 $\mathrm{lca}(x_1,x_2),\dots$，和 $\mathrm{lca}(x_{m-1},x_m)$。
• 对 $x_1,x_2,\dots ,x_m,\mathrm{lca}(x_1,x_2),\dots ,\mathrm{lca}(x_{m-1},x_m)$ 按照先序排列排序并去除重复项。

一旦获得发生的顶点，剩下的就是在维护一个栈的同时扫描这个序列。（我们不详细解释。有关实际过程，请参见 yaketake08的文章（日文），专栏“ソート2 回の方法”。（译者注：也可以参考 yaketake08的文章（日文），专栏“ソート2 回の方法”。））

基于到目前为止介绍的技术，可以从每种颜色的顶点集生成辅助树并执行树 DP，从而以总共 $\mathrm{O}(N\log N)$ 的速度解决问题，这已经足够快了。