分块，为你我陷入疯狂！
阅读更多
折腾。
我认为本场 NOI Online 是正确的，客观的，合理的，明晰的，真实的，辩证的，深刻的，通达的，优美的，巧妙的，精辟的，雅正的，机智的，全面的，明白晓畅的，不偏不倚的，恰如其分的，滴水不漏的，不容质疑的，切中要害的，一针见血的，淋漓尽致的，深谙事理的，真知灼见的，发蒙振聩的，微言大义的，金声玉振的，形而上学的，透过现象看本质的，知其然而知其所以然的，可供世人仿效的，千古颠扑不破的。
一个出了两个数点题，却没有一个 DP/字符串/数学 的 round。
在晚宴上，主办方为大家提供了 $n−1$ 种不同的寿司，编号 $1,2,3,\ldots,n-1$，其中第种寿司的美味度为 $i+1$。（即寿司的美味度为从 $2$ 到 $n$）
现在小 G 和小 W 希望每人选一些寿司种类来品尝，他们规定一种品尝方案为不和谐的当且仅当：小 G 品尝的寿司种类中存在一种美味度为 $x$ 的寿司，小 W 品尝的寿司中存在一种美味度为 $y$ 的寿司，而 $x$ 与 $y$ 不互质。
现在小 G 和小 W 希望统计一共有多少种和谐的品尝寿司的方案（对给定的正整数 $p$ 取模）。注意一个人可以不吃任何寿司。
$n \leq 300,p \leq 10^{10}$
班上 $2n$ 个学生分成了 $n$ 组，每组两个人。其中 $1$ 号和 $2$ 号为一组，$3$ 号和 $4$ 号为一组，……，$2n-1$ 号和 $2n$ 号为一组。
每个人决定是否愿意和队友合作，对于第 $i$ 个学生，选择“愿意”会产生 $c_i$ 的不满，选择“不愿意”会产生 $d_i$ 的不满。
如果两名队友都选择“愿意”，那么根据实际情况他们可以合作或者不合作。但是如果有一名队友选择“不愿意”，那么他们只能不合作。
如果一个学生 $i$ 选择了“愿意”但是他的队友选择了“不愿意”，那么他会因为队友产生 $e_i$ 的不满。
学生中还有 $m$ 个单向的喜欢关系，一个关系形如“$A$ 喜欢 $B$”。在这样一个关系中，有两种情况（其中 $i$ 表示第 $i$ 个关系，且保证 $A$ 和 $B$ 不在同一组）：
- 如果 $A$ 没有和队友合作，且 $B$ 选择了“愿意”，$A$ 会有产生 $a_i$ 的不满
- 如果 $A$ 表决了“不愿意”，但 $B$ 成功与队友合作，那么 $A$ 会产生 $b_i$ 的不满。
问所有情况下最小的不满之和是多少。
$n \leq 5000,m \leq 10000$
做了 NOI2018 归程 学到的东西。
给定一个点编号在 $[L,R]$ 范围内的完全图，边 $(u,v)$ 的权值为 $\mathrm{lcm}(u, v)$，请你求出这张图的最小生成树权值和。
$L,R \leq 10^6,R - L \leq 10^5$
CF1039D You Are Given a Tree 解题报告
有一棵 $n$ 个节点的树。
其中一个简单路径的集合被称为 $k$ 合法当且仅当：
树的每个节点至多属于其中一条路径，且每条路径恰好包含 $k$ 个点。
对于 $k\in [1,n]$，求出 $k$ 合法路径集合的最多路径数
即：设 $k$ 合法路径集合为 $S$，求最大的 $|S|$。$n \leq 10^5$
最初给定 $n$ 个物品以及背包容量 $k$，有 $q$ 次操作，操作有三种：
1 v w在背包里添加一个体积为 $v$ 价值为 $w$ 的物品2 x删除编号为 $x$ 的物品3查询背包总和，以 $\sum\limits_{m=1}^{k}{s(m)*p^{m-1}\ \bmod\ q}$ 的形式输出$n \leq 5000,k \leq 1000,q \leq 30000$ ，保证操作 $1$ 的个数不超过 $10000$，且至少有一个操作 $3$。