FXJFXJ
0%

340

发表于 更新于 分类于 阅读次数：
本文字数： 3.5k 阅读时长 ≈ 13 分钟

A - Arithmetic Progression

给出等差数列的 \(a_{1},a_{n},d\)，给出这个数列 

1
2
3
4
5
6
7
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\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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\leq N\leq 10^{17})\)

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

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

  • 选择写在黑板上的一个不小于 \(2\) 的整数 \(x\)。
  • 擦去黑板上出现的一个 \(x\)。然后，在黑板上写下两个新的整数 \(\left \lfloor \dfrac{x}{2} \right\rfloor\) 和 \(\left\lceil \dfrac{x}{2} \right\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\) 实在太大了，存不下)

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

\(n\) 1 2 3 4 5 6 7 8 9 10 \(\dots\)
ans 0 2 5 8 12 16 20 24 29 34 \(\dots\)
dif|ans 0 2 3 3 4 4 4 4 5 5 \(\dots\)
dif|dif|ans) 0 2 1 0 1 0 0 0 1 0 \(\dots\)

从 3 开始 dif|ans 每隔 \(2^{k}\) 多一个 1

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

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

1
2
3
4
5
6
7
8
9
10
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 ))

1
2
3
4
5
6
7
#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,\ldots,N\) 的 \(N\) 个阶段组成。最初，只有阶段 \(1\) 可以玩。

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

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

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

Solution

最短路

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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,\ldots,M\) 进行以下操作：

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

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

Solution

线段树(待更 \(\dots\))

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

区间修改一般还是线段树

官方题解：

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

  • 从箱子 \(B_i\) 中取出所有的球并拿在手中。
  • 让 \(X\) 表示手中的球的数量。将 \(\left\lfloor\frac{X}{N}\right\rfloor\) 个球放入每个箱子中。
  • 让 \(X\) 表示手中剩余的球的数量。将一个球放入箱子 \(B_i+1\) 到箱子 \(B_i+X\) 中。 （如果 \(B_i+X\geq 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} \leq A, B \leq 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)\) 定义为 \(\vert a \vert\) 和 \(\vert b \vert\) 的最大公约数。）

扩展欧几里得算法，给定一个整数对 \((a, b)\) 作为输入，找到一个整数对 \((x, y)\)，使得 \(ax + by = \pm \mathrm{gcd}(a, b)\)，时间复杂度为 \(\mathrm{O}(\log \min(|a|, |b|))\)。（这里，整数对 \(x, y\) 保证是满足 \(\max(|x|, |y|) \leq \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\leq 2\) (保证 \(\frac{2}{g}\) 是整数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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。

image

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

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

辅助树的性质

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

\[ A(X) = \lbrace \mathrm{lca}(x, y) \vert x \in X, y \in X \rbrace \]

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

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

性质 1

\(\vert A(X) \vert \leq 2 \vert X \vert - 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) \neq l\)，那么 \(\mathrm{lca}(x_1, x_n) = \mathrm{lca}(x_2, x_n)\)。

（引理证明）我们用反证法证明。假设存在 \(n\) 使得 \(\mathrm{lca}(x_1, x_n) \neq l\) 且 \(\mathrm{lca}(x_1, x_n) \neq \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)\) 可以表示为

\[ \begin{aligned} &A(\lbrace x_1, \dots, x_m\rbrace) \\ &A(\lbrace x_2, \dots, x_m\rbrace) \cup \lbrace x_1, \mathrm{lca}(x_1, x_2) \rbrace. \end{aligned} \]

这个方程意味着

\[ \vert A(X)\vert \leq \vert A(\lbrace x_2, \dots, x_m\rbrace)\vert + 2; \]

通过对顶点集大小进行归纳，可以证明 \(\vert A(X) \vert \leq 2 \vert X \vert - 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 \lbrace \mathrm{lca}(x_i, x_{i+1}) \vert 1 \leq i \lt m \rbrace. \]

（证明）

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

\[ \begin{aligned} &A(\lbrace x_1, \dots, x_m\rbrace) \\ &= A(\lbrace x_2, \dots, x_m\rbrace) \cup \lbrace x_1, \mathrm{lca}(x_1, x_2) \rbrace. \end{aligned} \]

​)}​

，得出

\[ \begin{aligned} &A(\lbrace x_1, \dots, x_m\rbrace) \\ &= A(\lbrace x_2, \dots, x_m\rbrace) \cup \lbrace x_1, \mathrm{lca}(x_1, x_2) \rbrace \\ &= A(\lbrace x_3, \dots, x_m\rbrace) \cup \lbrace x_1, \mathrm{lca}(x_1, x_2), x_2, \mathrm{lca}(x_2, x_3) \rbrace \\ &\vdots \\ &= A(\lbrace x_m \rbrace) \cup \lbrace x_1, \mathrm{lca}(x_1, x_2), x_2, \dots, x_{m-1}, \mathrm{lca}(x_{m-1}, x_m) \rbrace \\ &= \lbrace x_1, \mathrm{lca}(x_1, x_2), x_2, \dots, x_{m-1}, \mathrm{lca}(x_{m-1}, x_m), x_m \rbrace, \\ \end{aligned} \]

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

利用性质 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)\) 的速度解决问题，这已经足够快了。

  • 本文作者： FXJFXJ
  • 本文链接： https://fxj.wiki/posts/449f4180/
  • 版权声明： 本博客所有文章除特别声明外，均采用 ZERO 许可协议。转载请注明出处！