2023 国庆集训 Day 2B 笔记

· · 个人记录

更佳的阅读体验:2023 国庆集训 Day 2B 笔记,本文同步发表于 洛谷博客。

以下内容为个人总结,如有错误或您有不同见解,欢迎指出。

搜索

NOIP2009 提高组 - 靶形数独

Example 2

有 q 次询问,每次询问一个数 x,询问 x 每次除以一个约数直到最后变为 1 有多少种方式,比如 x = 6,有(6 \to 1)、(6 \to 3 \to 1)、(6 \to 2 \to 1) 三种。x \le 10^{15},q \le 10^4。

SDOI2015 - 排序

二分

最大平均子段和

给定一个长度为 n 的序列 a_1,a_2,\cdots,a_n 和 k,求一个长度大于 k 的区间 [l, r] 使得 \frac{a_l+\cdots+a_r}{r - l + 1} 最大。n \le 10^5,输出小数,精度 10^{-6}。

LOJ 2776 - 蠕虫之忧

Subtask 1

Subtask 2

Subtask 3

Example 3

你在玩一个游戏,游戏中的一个关卡是这样的:

有一张 n 个节点和 m 条边的有向图,每条边有一个长度,你的角色一开始在 1 号点移动速度为 1 单位长度每秒,每次到达一个点会带权选择一个随机的出边走出去,在边上移动的时候会消耗对应长度的时间。你的目的是在 L 的时间内到达 n 号点,你可以选择在任意时间重开这一关。

求在现实世界过关所需要的最小期望时间,输出实数。n \le 100,m \le 200,其他所有数在 10^9 以内。

分治

Example 1

给定一个排列,随机做 k 次交换两个数,求最后期望逆序对数。n \le 5 \times 10^5,k \le 10^9。

Example 2:随机点分治

给定一棵树 T,每次并非选重心而是随机选择一个点进行分治,求期望复杂度。n \le 10^5。

点分治:ZJOI2016 - 旅行者

CDQ 分治

贪心

Example 1

有 n 个怪物,每个怪物 a_i 和 b_i,当你打一个怪物的时候会先减少 a_i 血再加 b_i 血,中途血量不能小于 0,请问最少初始需要多少血才能打赢所有怪物。n \le 10^5。

IOI 2019 - 排列鞋子

正确性证明

快速幂

NOI2020 - 美食家

二维 RMQ

Example 1

给定一个 n \times m 的矩阵和 q 次询问,每次询问一个子矩阵的最小值。n, m \le 300,q \le 10^7。

LCA

Tarjan 算法

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct edge {
    int to, nxt;
} e[N << 1];
int n, m, id, h[N], fa[N], ans[N];
vector<pair<int, int> > q[N];
bool vis[N];

void add(int u, int v) {
    e[++id] = (edge){v, h[u]};
    h[u] = id;
}

int getroot(int u) {
    return u == fa[u] ? u : fa[u] = getroot(fa[u]);
}

void dfs(int u, int f) {
    vis[u] = true;
    for (int i = h[u]; i; i = e[i].nxt)
        if (e[i].to != f) dfs(e[i].to);
    for (int i = 0; i < q[u].size(); ++i) {
        int to = q[u][i].first, id = q[u][i].second;
        if (vis[to]) ans[id] = getroot(to);
    } fa[u] = f;
}

int main() {
    cin >> n;
    for (int i = 1, u, v; i < n; ++i)
        cin >> u >> v, add(u, v), add(v, u);
    for (int i = 1; i <= n; ++i) fa[i] = i;
    cin >> q;
    for (int i = 1, u, v; i <= q; ++i) {
        cin >> u >> v;
        q[u].emplace_back(make_pair(v, i));
        q[v].emplace_back(make_paur(u, i));
    } dfs(1, 0);
    for (int i = 1; i <= q; ++i) cout << ans[i];
    return 0;
}

求 LCA 加强版

给定一棵 n 个点的树和 q 次询问,每次给定 u,v 和 w,求以 w 为根的情况下 u, v 的 LCA。n,q \le 10^5。