Creator's World

“偷学不能算偷……偷学！……oier的事，能算偷么？”接着就是难懂的话，什么“I AK IOI”，什么“fAKe”之类，引得众人都哄笑起来：机房内外充满了快活的空气。

$4.14$

P1472 [USACO2.3]奶牛家谱 Cow Pedigrees

dp $+$ 二叉树。

设 $f_{i,j}$ 为前 $i$ 个点前 $j$ 层的方案数，转移即可。

$4.13$

P2822 [NOIP2016 提高组] 组合数问题

组合数。

就是 $O(n^2)$ 求组合数，$k|\binom{i}{j}$ 其实只要在递推中对 $k$ 取模即可。最后还要做一下 前缀和。

P3166 [CQOI2014]数三角形

组合数 $+\gcd +$ 容斥。

首先三角形不能共线，而共线一共有三种情况：共竖线、共横线、共斜线。考虑 容斥，把所有三角形减去共线的三角形即可。

所有三角形共有 $C_{n \times m}^3$，共横竖线的一共有 $n\times C_m^3 + m \times C_n^3$，关键是斜线怎么处理的问题。

观察一下，发现与 $\gcd$ 有关，枚举 $i,j$，找到原点到 $i,j$ 斜线上有多少点，再平移即可，还要 $\times 2$。

P5520 [yLOI2019] 青原樱

插空法。

首先 $m$ 棵树之间有 $m-1$ 个空，剩下的 $n-(m-1)$ 个位置可以放 $m$ 棵树，直接暴力计算排列数 $A_{n-m+1}^m$ 即可。

$4.12$

P1072 [NOIP2009 提高组] Hankson 的趣味题

$\gcd +$ 数论。

很显然是让我们求满足以下条件的 $x$ 的个数。

$\begin{cases} \gcd(x,a_0)=a_1\\ \operatorname{lcm}(x,b_0)=b_1 \end{cases}$

然后怒推一波式子之后就变成了

$\begin{cases} \gcd(\frac{x}{a_1},\frac{a_0}{a_1})=1 \\ \gcd(\frac{b_1}{x},\frac{b_1}{b_0})=1\end{cases}$

然后枚举 $b_1$ 的因此即可，时间复杂度 $O(\sqrt{b_1})$。

CF1436D Bandit in a City

树形 dp。

一开始想了个假的贪心，结果没细想就开写了，码了半天发现假了。果然还是要细想，特别是 贪心， 尽量卡死自己。

树形 dp 也很好想，主要是发现性质就好了。

CF1436C Binary Search

组合计数。

其实最关键的就是转换题意，也就是题目到底要让我们做什么。观察程序后发现就是求有多少序列满足二分查找后在 $pos$ 找到 $x$，那么直接推公式即可。

$4.11$

CF1438D Powerful Ksenia

构造 $+$ 位运算。

首先要抓住异或的性质：相同的数异或后不变。

因为并没有要求次数最少，因此我们只需构造出一组解即可。接下来对 $n$ 为奇数 $/$ 偶数时分别构造即可。

奇数时手玩一下即可发现规律。

偶数我们要在变的东西中抓住什么东西不变：所有数的异或和不变，因此只需对 $n-1$ 按奇数构造即可。

CF1438E Yurii Can Do Everything

位运算 $+$ 剪枝。

其实本题没有什么高深的算法，只是一个最简单的暴力结合异或的性质剪枝，使时间复杂度正确罢了。

$O(n^2)$ 的暴力都会写，预处理前缀和，枚举左右端点统计答案。

再考虑如何优化。突破点一定是在 异或 之上。我们可以想到异或的性质：$a$ 异或上任何一个 $\leq a$ 的数一定小于 $2^{k+1}$，$k$ 为 $a$ 在二进制下的最高位。

而对于每一个 $k$，$a_i$ 最多访问 $2$ 次，因为若有第三个 $k$，那么中间和一定 $\geq 2^{k+1}$，时间复杂度为 $n\log a_i$。

为了避免遗漏，要扫两边，从左到右、从右到左。

P5514 [MtOI2019]永夜的报应

位运算。

异或有一个非常重要的性质，做题经常用到：a ^ b <= a + b，因为异或其实是 不进位的加法。

那么只要分成一组就行了。

P5535 【XR-3】小道消息

数论。

题目都给了 伯特兰-切比雪夫定理，但不管这个定理，我们手玩一下也可以发现，答案似乎只有 $1$ 和 $2$ 两种可能，感性认知一下：若 $k+1$ 是个质数且没有倍数的话第一天就可以传给所有人，否则的话第一天传给所有质数，然后第二天就可以转给所有人。

判断质数可以用 Miller_Rabin 算法。

伯特兰-切比雪夫定理：

若整数 $n>3$，则至少存在一个质数 $p$，满足 $n<p<2n-2$。

P5435 基于值域预处理的快速 GCD

rt。

感觉挺妙的，具体看 这篇博客 吧。

不过码好后一直 T 后面几个点，拼命调之后发现把 $\gcd$ 函数的类型从 ll 改为 int 即可，就很玄学，可能因为 ll 常数大吧，之后卡时间的时候能不写 ll 就不写。

P1414 又是毕业季II

$\gcd$。

首先肯定考虑最暴力的想法：枚举。

肯定会超时，转换思路。发现每个数可以拆成若干个因子，若干个数的 $\gcd$ 就是这若干个数中共同出现的因子。那么读入时将每个数分解因数，再存下来即可。时间复杂度 $O(n\log INF)$。

$4.10$

从今天开始新的都记在最前面

CF915F Imbalance Value of a Tree

并查集。

一道比较套路的题，知道模型后就很简单。

设 $f{i,j}$ 为 $i$ 到 $j$ 的最大边权，$g_{i,j}$ 为 $i$ 到 $j$ 的最小边权，显然可以将原式转化为 $\sum_{i=1}^{n}\sum_{j=i}^{n}f_{i,j}-g_{i,j}$。而如何求两点路径上的最大 $/$ 最小权值可以用 并查集来维护。

而本题求的是 点权，因此需要将其转化为边权，对于一条边其边权只需取两端点权值的 $\max$ 和 $\min$ 即可，因为对自己取 $\max$ 或 $\min$ 并不会有影响。

AT2439 「JOI 2015/2016 决赛」铁路票价（鉄道運賃）

最短路。

其实增加边权相当于 删边，因为一个点不可能通过加权的边。类似 P1197 [JSOI2008]星球大战，反着考虑，将删边转化为加边，判断是否通过这一次加边使得可行。

P1710 地铁涨价

双倍经验。

CF845C Two TVs

贪心。

简单的贪心，注意读题，特别是 边界！这题的 $l,r$ 是从 $0$ 开始的。

CF785D Anton and School - 2

组合计数。

一道挺有意思的题。显然是单独考虑每个括号对答案的贡献，为了避免重复只考虑左括号。

对于一个左括号来说，若其左边有 $a$ 个左括号（包括自己），右边有 $b$ 个右括号，则其对答案的贡献为

$C_{a-1}^0 \times C_b^1 + C_{a-1}^1 \times C_b^2\times \cdots$

即

$\sum_{i=0}^{\min(a-1,b-1)}C_{a-1}^i\times C_b^{i+1}$

根据神奇的 范德蒙德卷积

$\sum_{i=0}^kC_n^i\times C_m^{k-i}=C_{n+m}^k$

可以将原式转化为

$\sum_{i=0}^{\min(a-1,b-1)}C_{a-1}^{a-i-1}\times C_b^{i+1}=C_{a+b-1}^a$

然后预处理括号个数、阶乘、逆元即可。

CF739B Alyona and a tree

树上差分 $+$ 倍增。

首先对于 $u$ 来说 $dis_{v,u}\leq a_u$，显然我们要找到最大的满足条件的 $dis_{v,u}$，这可以用 倍增 来做。从 $u$ 到 $v$ 这一段上的点显然都满足条件，不可能每一个都加，因此我们需要 树上差分。

CF732B Cormen — The Best Friend Of a Man

贪心。

简单的贪心，显然给后一个数加更优，因为给其加了后对答案有贡献。

P5322 [BJOI2019]排兵布阵

背包 dp。

其实是简单的背包 dp，但是时间复杂度为 $O(snm)$，差不多有 $2e8$ 的程度，结果却能过。说明常数小的能过 $1e8$ 左右的程序，所以要大胆写，大不了能骗分。

还要注意一些细节，比如说 枚举顺序。

CF891A Pride

$\gcd$ $+$ 模拟。

首先对于原序列中就有 $1$ 的情况，显然有 $ans=n-num \_ one$。

若原序列中没有 $1$，显然要通过取 $\gcd$ 使得产生 $1$。因此我们直接模拟即可。

CF1438C Engineer Artem

思维题。

最关键的是 $+1$ 的特殊性质：改变数字奇偶性。而奇数和偶数一定不相同，构造奇、偶相交即可。

---

$3.12$

P6032 选择客栈 加强版

第一眼看去就是求 $RMQ$ 问题，用 $ST$ 表求解。可惜会卡空间，只有 $90$ 分。

正解是 递推（我也说不上来到底是啥），是常见的处理两个端点的问题。将枚举两个端点的 $O(n^2)$ 算法优化为 $O(n)$。此种类型常见的套路为：只需枚举其中一个端点，另一个端点在移动过程中有信息是不需要重新计算的。这种题目要仔细观察题目信息，思考在移动中是否可以 减少重复计算。

P7414 [USACO21FEB] Modern Art 3 G

区间 $dp$，写了篇题解：题解

P5993 [PA2014]Iloczyn

简单题。

$3.13$

P3393 逃离僵尸岛

简单的 最短路，唯一有不同的是危险城市的处理。一开始用 $dfs$ 超时了两个点，后来用 $bfs$ 就过了。看来 $bfs$ 在图中的速度比 $dfs$ 快。

P3661 [USACO17FEB]Why Did the Cow Cross the Road I S

一道贪心题。贪心是一眼就能看出来的，关键是怎么贪。一开始将牛和鸡升序排序，结果只有 $50$ 分。后来降序排列，就过了。因为发现越大的点只有大的区间才能满足，就莫名其妙过去了。

严谨的证明可以看题解。不过也是数据太水，本应用数据结构优化才能过，不过懒得写了。

所以贪心题不能大胆假设，从不证明。还是需要用 举反例 或 推理 来保证其正确性。

P1078 [NOIP2012 普及组] 文化之旅

当初觉得难得遥不可及的题目，现在看来居然这么水（可能是因为数据水）。$n \leq 100$ 怎么做都行。直接上 $dfs$ 即可，当然加了一些剪枝，有些 记忆化搜索 的影子。

$3.14$

今天日期是圆周率诶

P6538 [COCI2013-2014#1] LOPOV

一道简单的套路题，一眼看去就是贪心。不过用二分只能得到 $80$ 分的高分。需要进行优化。看到删除、排序、二分查找这些功能，想到用 multiset 优化即可。

P2117 小Z的矩阵

还是一道锻炼思维能力的题目。一开始按照题意模拟，理所当然的超时。后来在优化过程中，发现了 对角线 的特殊性，不过当时忽略了 对 $2$ 取余 的重要性质，一时没看出来。最后对着样例模拟下去，发现似乎答案只与对角线上的数字相关，大胆猜测结论，做了出来。

其实也是显然的，$a_{i,j} \times a_{j,i}$ 和 $a_{j,i} \times a_{i,j}$ 显然是相等的，两个相等的数相加一定是偶数，在 $\bmod 2$ 情况下一定等于 $0$，所以答案只与对角线相关。可惜一开时没抓住题目关键的性质，白费许多时间。

P2401 不等数列

这是一道需要思维能力的 dp。可能对于某些人很简单，但我 dp 一直都不是很行，这题也想了很长的时间才想出来。个人觉得这题不错，写篇题解吧（虽然已经不能发了，但写给自己看吧）。题解。

$3.15$

P4822 [BJWC2012]冻结

一道 分层图 的模板图，具体可以看我的博客 分层图

P6149 [USACO20FEB] Triangles S

这题真的是把我勾巴都写断了。写了快两天，一直都是超时，拼命想怎么优化，最后写了个 vector 还加了 O2 才终于过了。不过跟深刻地感受到了算法优化的精髓：减少重复计算。

发现正解真的是发挥人类智慧，到时候再看吧，咕咕~~

$3.16$

AT4720 [ABC123D] Cake 123

就挺巧的，刚好这道题就是讲过的 堆优化贪心。像这样在每一行取一个数，求前 $K$ 大的方案数的题目就是贪心求解即可。类似的题目之前讲过。作业题讲解。不说了，我要水一篇题解了（还是一血）

$3.17$

P1736 创意吃鱼法

事实上这题本质上还是简单的 dp 模型：求矩阵中满足条件的最大正方形，但由于其加入的一些限制，变得更复杂些，不过只要细心还是简单的。

首先很重要的是 读题：本题的最大正方形需要满足 只有对角线上有 $1$，其他部分都为 $0$。看到这个条件显然会想到用 二维前缀和 维护每个正方形 $1$ 的个数，如果其等于对角线上的 $1$ 的个数就合法。

但还没有结束，这里的对角线有 四条！因此需要依次处理，我的方法有些麻烦，每次重新计算前缀和，再重新进行转移。

AT3882 [ARC090B] People on a Line

事实上只是一道 差分约束 的板子题，主要用到的思想是：

$x_i-x_j=d_k$

可以转化为

$x_i-x_j \leq d_k$

$x_i-x_j \geq d_k$

而第二个式子可以化为

$x_j-x_i \leq -d_k$

根据上面的式子差分约束即可。注意本题一个点可以有多个人，否则的话还要加一个式子：

$0\leq sum_{i+1}-sum_i \leq 1$

但当我们用 SPFA 来判断负环时却发现 T 飞了（果然 SPFA 死了），我们需要用 dfs 判断负环的方式才能过。其主要思想为：我们将 $u$ 标记为以访问过，在遍历相邻的节点 $v$，若 $v$ 的最短路可以通过 已访问过的 $u$ 来更新时，说明有负环。注意，在后面要 将 $u$ 的标记取消。代码如下：

bool dfs(int u)
{
	ins[u]=true;
	
	for(int i=he[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(dis[v]>dis[u]+e[i].dis)
		{
			if(ins[v])
				return true;
			dis[v]=dis[u]+e[i].dis;
			if(dfs(v))
				return true;
		}
	}
	
	ins[u]=false;
	
	return false;
}

$3.18$

P1854 花店橱窗布置

一道 线性 dp。可借鉴的思想是 转化数学模型，比较麻烦的点是 输出方案。

转化数学模型。题目里什么花瓶什么花的，事实上我们将其繁琐的语言转化为抽象的数学模型会好做一些。根据题意我们会发现，说白了就是在一个 $n \times m$ 的矩阵中，每行取一个数字，每行取的数要比上一行取的数的位置要 靠后，问最后能取到的数字和最大是多少。设 $f_{i,j}$ 为前 $i$ 行前 $j$ 列取到的最大数字和。易得转移方程：

$f_{i,j}=\max_{k=1}^{k<j}(f_{i-1,k}+a_{i,j},f_{i,j})$

输出方案。在一些题目中会让你输出方案，这会有一些麻烦。不过只要在转移时记录一下每行是由哪里转移而来的即可。

！CF1388C Uncle Bogdan and Country Happiness

挺妙的一道 思维题。一开始没想清楚就开写，写了个繁琐的模拟？（还是要想清楚再写）

看了正解后才发现只是发现性质求解即可。首先无解的情况还是好想的：设原序列 $a$ 升序排列后为序列 $b$，若 $a_i!=b_i$ 且 $a_i \ \bmod \ b_1!=0$ 的话，输出 “NO”。显然，若一个数不是最小值的倍数就无法移动，若它还不是该在的位置，那它就永远动不了。

再看为什么除此之外的都可以满足条件。若一个序列不满足上面无解的条件，也就是所有数都是最小值的倍数。若只有两个数，那么肯定可以直接交换。否则的话，一定有用两个以上的最小值的倍数，一定可以进行任意交换，假设最小值为 $a$，其两个倍数为 $b$、$c$，一定可以进行：

$a,b,c$

$c,b,a$

$c,a,b$

$a,c,b$

发现最小值的位置不变，但交换了两个值。对于所有数都可以进行如上操作。

！CF1388D Captain Flint and Treasure

一道 图论 题。如何想到图论还是需要一点思维转换的，转化之后就是 dfs 解决的事。不过本题还要 输出方案数。

我的想法：求最值就用 dfs，先建有向图，对于每个点，遍历其的相邻节点，用动态规划求出每个点最大的值，最后相加即为答案。至于输出方案，可以用 拓扑 来做。不过样例都能过，但就是会 wa，不知道为啥，太难调了。

正解：先建有向图，再从每一个根节点出发，求出每个节点的 最终值（若子节点的最终值大于 $0$ 就加上子节点的最终值）。输出方案时先讲该节点 最终值大于 $0$ 的子节点 递归 输出，再输出该节点，再输出其他节点。因为先将大于 $0$ 的子节点输出显然更优。

$3.19$

P2854 [USACO06DEC]Cow Roller Coaster S

一道 线性 dp，和 P1280 尼克的任务 有些相似，但又有不同。

一开始看到满足条件的最大值，居然想到二分？但最优解还很有可能是用 dp、贪心等解决。后来发现不符合单调性。

然后写了个 dp。设 $f_{i,j}$ 表示长度为 $i$，成本为 $j$ 时的最大有趣值，易得转移方程

$f_{i,j}=\max(f_{i,j},f_{i-len_k,j-cost_k}+fun_k)$

$k$ 为终点为 $i$ 的铁轨的编号，读入时预处理一下即可。

但写完后发现伪了。因为本题不同之处：每根铁轨必须 首尾相连，若到达不了输出 $-1$（翻译没提到，差评）。因此我们初始化 $f$ 数组为 $-1$，$f_{0,0}=0$，转移时若上个状态等于 $-1$，说明并没有首尾连接，是不合法的。最后在 $f_{l,i}(1 \leq i \leq b)$ 中取最大值即为答案。

$3.20$

P3057 [USACO12NOV]Distant Pastures S

一道 图论题，转化一下就变成了最短路，从每一个点出发跑一遍 dijkstra 就行了。比较有意思的是：这是一个矩阵，要将每一格的坐标压缩为一个数。还有，数组一定要开大！否则会出现随机 RE 和 WA。

P1987 摇钱树

一道 贪心 $+$ dp 的题目。

首先能想到贪心策略：按树每天掉落金币数从大到小排，而不是按初始金币排序。这其实可以理解，假设我们已经想好要选哪几棵树，那么不管怎么选，这几棵树的 初始总金币数 一定不变，可以将其想像成一个整体，因此我们要尽量先选 每天掉落金币多 的树，防止金币数变更少。

我一看，有点像是后悔贪心，结果码了半天，过了样例，却只能过一个点。限于水品有限吧，之后看能不能用后悔贪心做。

正解 dp 其实还是好想的。类似于 $背包$，可以用 滚动数组，设 $f_i$ 表示选了 $i$ 棵树的最大金币数，可得转移方程

$f_i=\max(f_i,\max(0,f_{i-1}+a_i.start-(i-1)\times a_i.reduce))$

注意这里树的金币数可能是负数，要处理一下。

AT5337 [ABC153D] Caracal vs Monster

稍微手玩一下就可以发现规律：血量为 $n$ 的怪物需要打 $\sum_{i=0}^{log_2n}2^i$ 次。

$3.21$

P2921 [USACO08DEC]Trick or Treat on the Farm G

一道 强连通分量 题。

手玩一下样例就会发现，走回之前走过的隔间其实就是在一个环中，因此可以用 Tarjan 来找强连通分量。

最后统计答案时，在一个大小大于 $1$ 的强连通分量中的点答案就为该分量的大小；若是自环，答案为 $1$；否则的话，要从该点出发直到到达一个分量，在这里没用 dfs 结果不知道怎么错了，用 dfs 就行了。

P1266 速度限制

一道 最短路 题。

但不同于普通的最短题目的是，本题求的是最短 时间，而不是路径长度。最大的问题是：一条路径若没有限速要求，其需按原先的速度前进。这就说明一条相同的道路可能可以用不同的速度经过，若直接转移有 后效性，因此可以用类似 分层图 的方法做。

设 $dis_{i,j}$ 表示 到 $i$ 点速度为 $j$ 时的最短时间，然后跑最短路即可。

P3938 斐波那契

结论/思维 题。

一开始以为是求 LCA，但加上斐波那契数列怎么也做不出来。

但手玩一下样例，发现子节点编号减去父亲节点编号等于第一个小于子节点编号的斐波那契数，于是大胆猜测结论，就过了。

所以对于这类题目，先手玩小数据，发现规律就行了。

P3275 [SCOI2011]糖果

一道 差分约束 题。

对于 $x_a>x_b$ 的情况，实际上就等于 $x_a \geq x_b+1$，可转化为 $x_a-x_b\geq 1$。

还有要认真读题：每个同学至少要有一个糖果。最后找出所有 $dis$ 的最小值 $minn$，若 $minn \leq 0$，把所有 $dis$ 加上 $1-minn$，不会改变相对大小关系。

不开 long long 见祖宗。

$3.22$

P2294 [HNOI2005]狡猾的商人

一道 差分约束 题。

不过本题建立差分约束模型还是比较有意思的。从 $s$ 到 $t$ 的总收入为 $v$，可以运用 前缀和 的思想，假设 $pre_i$ 为 $i$ 的前缀和，可得式子 $pre_t-pre_{s-1} \geq v$。但仅有这个式子还不够，从上述条件我们还可以得到 $pre_{s-1}-pre_t\leq v$.。

不过本题不能以 $0$ 为 超级源点，因为 $s-1$ 有可能就是 $0$。

P4185 [USACO18JAN]MooTube G

一道 离线 $+$ 并查集 题。

简化题意：

有一棵 $n$ 个点的树，有 $q$ 次询问，每次询问给出 $k$ 和 $v$，问有多少个点，满足从 $v$ 出发经过的边权中的最小值不小于 $k$。

首先最暴力的想法：对于每次询问，dfs 搜索得到答案。显然会超时。

再考虑优化：发现实际上可以用 并查集 来维护 满足条件的连通块大小，类似于 最大生成树，最后答案就是 $v$ 所在的连通块的大小。但由于每次都要重新计算一遍，实际上还是没有优化。

再考虑 离线 做法。可以先将每一次询问的 $k$ 和 $v$ 都存下来，再按 $k$ 从大到小 排序，再维护连通块大小，这样就不需要每次都重新算了。为什么呢？因为 $k$ 从大到小排，若 $k$ 大可以满足，那么 $k$ 小的一定可以满足。

P6111 [USACO18JAN]MooTube S

上题的弱化版，可以直接用 dfs 做。双倍经验。

CF1213G Path Queries

与上题类似，但也有不同。

本题求的是 最大权值不大于 $k$，因此要 从小到大 排序。同时本题是从所有点出发的总路径条数，可以发现每个连通块对答案的贡献为 $(size_x-1) \times size_x /2$，在并查集合并时先减去要合并的连通块对答案贡献，再加上新连通块对答案贡献。

P1260 工程规划

一道 差分约束 题。

做多了这种题，其实差分约束还是比较容易看出来的：首先题目中可以得出不等式，有的是直接告诉你的，有些则是要进行转换（比如用 前缀和）；然后再连边，跑 spfa 即可。

最常用的的式子就是 $x_a-x_b=c$，从 $b$ 向 $a$ 连一条边权为 $c$ 的边。

差分约束一般有三种应用：求不等式组解的 最大值、最小值、是否有解。

对于 最大值，有 $x_a-x_b=c$，从 $b$ 向 $a$ 连一条边权为 $c$ 的边，跑以 $0$ 为起点的 最短路 即可。

对于 最小值，变形为 $x_a-x_b\geq c$，跑 最长路。

P6145 [USACO20FEB]Timeline G

一道 差分约束 题。

事实上本题的难度可能要大一些（可能因为差分约束不是正解），需要一些思维转换。

首先我们要先了解差分约束的本质：为什么它能转化为 最短路 问题。

先看最原始的差分约束式子

$x_a-x_b\leq c$

可以转化为

$x_a\leq x_b+c$

假如对于一个 $x_a$ 来说有多个 $x_b$，那么有

$x_a=\min(x_b+c)$

再看最短路的式子

$dis_v=\min(dis_u+e_i.dis)$

是不是非常相似？最短路中的 $u$ 相当于差分约束中的 $b$，$v$ 相当于差分约束中的 $a$。而最短路中是 $u$ 向 $v$ 连一条长度为 $e_i.dis$ 的边，因此我们在差分约束中连一条从 $b$ 向 $a$ 长度为 $c$ 的边。

再来看本题的式子。对于

$x_b-x_a\geq c$

由于我们求的是 最小值，因此要跑 最长路（反着来的），而最长路的式子为

$dis_v\geq dis_u+e_i.dis$

即

$dis_v-dis_u\geq e_i.dis$

所以我们连从 $a$ 向 $b$ 长度为 $c$ 的边即可。

本题还有限制 $x_i\geq s_i$，相当于 $x_i-x_0\geq s_i$，连从 $0$ 向 $i$ 长度为 $s_i$ 的边即可。

P4878 [USACO05DEC]Layout G

一道 差分约束 题。

本题的要求有些不同，求 $1$ 到 $n$ 的最大距离，因此还要从 $1$ 出发跑 spfa。同时若 $dis_n=INF$，说明 差分约束约束不了 $n$，即题目说的 $1$ 和 $n$ 可以相距无穷大。

还有本题题目说每头牛按顺序排列，因此还要建 $i+1$ 到 $i$ 长度为 $0$ 的边。

P2085 最小函数值

一道 堆优化贪心。

首先读题，发现题目规定 $a,b,c,x>0$，说明每个函数值都是 递增 且 非负 的。

而对于 $n$ 个函数其最小的 $m$ 个值，我们可以发现，每次取最小的那个函数值，然后将该函数值的自变量 $x$ 加 $1$，在将新的函数值加入堆。

P1972 [SDOI2009]HH的项链

一道 树状数组 $+$ 离线。

发现 离线 的思想有时候就是神来之笔，用得好的话可以快速解决题目。一般像这种 给出几组询问 的，思考许久之后仍没思路，就可以考虑将查询离线下来做（比如今天做的那道并查集的题目，也是用离线做的）。

题目要求对于每组询问 $[l,r]$，问区间 $[l,r]$ 中有多少 不同的数。若有多组询问 $[l,r]$ 的 $r$ 相等，对于在区间内重复出现的数字，我们只关心它在 $r$ 上的位置。比如说有序列 $1,1,4,5,1,4$，对于所有 $r=6$ 的询问，一定会有一个 $4$。因此我们考虑将询问离线下来，按照 $r$ 值 从小到大 排序，这样就能避免重复计算了。

再考虑用 树状数组 来做，我们用其来表示一个数字第一次出现的位置。具体来说，对于每一个区间，当扫到一个位置时，该位置数字是第一次出现的话，就在树状数组中这个位置加上 $1$，否则的话就把原先的位置减去 $1$，再在新位置加上 $1$。

本题体现了树状数组不仅能用来简单的单点修改、区间查询，通过转换之后能够用来做更多的事。

$3.23$

P1966 [NOIP2013 提高组] 火柴排队

很有意思的一道题，离散化 $+$ 逆序对，而逆序对可以用 树状数组 求。

题意：

有两个长度为 $n$ 的序列，每个序列中相邻的两个数可以交换。问最少交换几次，使 $\sum(a_i-b_i)^2$ 最小。

思路：

接下来我们一层一层的转化问题。

首先我们肯定会思考怎么使 $\sum(a_i-b_i)^2$ 最小。这还是比较好想到的， $(a_i-b_i)^2$ 要最小，$a_i-b_i$ 一定要最小，显然越相似的数的差越小。因此我们得到结论：要将两个序列中大小顺序相同的数放在一起才能使答案最小，比如说第一个序列中第 $2$ 大的要和第二个序列中第 $2$ 大的放在一起，以此类推。

那么我们将问题转化为：如何将两个序列中大小顺序相同的数放在一起。因为我们只关心数之间的 相对大小，对其具体值并不在意，因此很容易想到 离散化。因为题目规定两个序列不会重复，因此不用考虑去重。假设序列 $a$ 为 $1,4,3,5,2$，根据其数值大小离散化后为 $1,5,3,2,4$（第一个位置 $1$ 表示第一小的元素在原序列第一个位置，第二个位置 $5$ 表示第二小的元素在原序列第五个位置，以此类推）；序列 $b$ 为 $2,5,4,1,3$，离散化后为 $4,1,5,3,2$。在将两个序列离散化之后，我们只需要通过交换相邻的数使得 两个序列对应位置数字相同。

那么接下来该怎么做呢？这里的方法与之前做过的一道题 UVA10635 Prince and Princess
有点像，我还写了题解 题解。由于两个序列中元素是 不会重复 的，所以其位置与数字一定是对应的，因此我们可以对两个序列进行 映射。具体来说，我们设 $p_{b_i}=a_i$，对于上面的例子来说，

$a_i:1,5,3,2,4$

$b_i:4,1,5,3,2$

$p_i:5,4,2,1,3$

映射之后，使得 $a$ 和 $b$ 相等也就转化为交换 $p$ 中的相邻元素，是 $p$ 变为 升序 序列。而如何求出交换相邻元素使得一个序列称为升序序列，就需要用到 逆序对 了（我之前也不知道，涨知识了），因为实际上交换之后也就相当于消除一个逆序对，所以求最小交换次数也就是求 逆序对对数。

而求 逆序对对数，除了 归并排序 之外，还有 树状数组 的方法。方法如下：树状数组初始化全为 $0$；从 $n$ 到 $1$ 枚举，对于枚举到的数，其对答案贡献为 $query(p_i)$；然后 $modify(q_i,1)$。可以画图模拟加深理解。

P4378 [USACO18OPEN]Out of Sorts S

逆序对。

本题题目求 冒泡排序需要跑几趟，这也可以用逆序对求解。对于每一趟，消去每一位上 $1$ 个逆序对，趟数就是每个位置上的数产生逆序对的最大值。

提供一种离散化的方法，这样做可以处理重复元素：

for(int i=1;i<=n;i++)
	a[i].val=read(),a[i].id=i;

sort(a+1,a+1+n,cmp);
	
for(int i=1;i<=n;i++)
	rank[a[i].id]=i;

$3.24$

P2679 [NOIP2015 提高组] 子串

线性 $\text{dp}$。

本题还是非常有意思的，一眼看去还真想不出来。下面将会按照思考的顺序来逐步讲解。

首先看到这样一道求 方案数 的题目，第一想法应该就是 dp。然后本题特殊的是的是 可以从 $\text{A}$ 中选择 $k$ 段拼起来，设 $f_{i,j,k}$ 表示 $\text{A}$ 中前 $i$ 个字符选出 $k$ 段与 $\text{B}$ 串前 $j$ 个字符完全相等的方案数，易得转移方程

$f_{i,j,k}=f_{i-1,j-1,k}+f_{i-1,j-1,k-1}$

但显然无法处理第 $i$ 个字符不用和与前一个字符合成一个子串的情况。而为了处理这样的情况，我们假设 $f_{i,j,k,0/1}$ 表示 $\text{A}$ 中前 $i$ 个字符选出 $k$ 段 $text{A}$ 中第 $i$ 个字符选 $/$ 不选与 $\text{B}$ 串前 $j$ 个字符完全相等的方案数，这样就可以进行转移了

$f_{i,j,k,0}=f_{i-1,j-1,k-1,0}+f_{i-1,j-1,k-1,1}$

$f_{i,j,k,1}=f_{i-1,j-1,k,1}+f_{i-1,j-1,k-1,0}+f_{i-1,j-1,k-1,1} (a_i=b_j)$

$=0(a_i\ne b_j)$

但是显然数组装不下，那么考虑 滚动数组，具体实现的话只要用 & 即可，记得 清空。

$3.25$

P4588 [TJOI2018]数学计算

一道很有意思的 线段树。

首先本题初看之下是不会想到线段树，有两种操作，一种是把 $x$（初始为 $1$）乘上 $m$，另一种是将 $x$ 除以第 $m$ 次操作乘上的数。

这不是直接按照提议模拟就好了吗？但是本题需要对一个数 取模，同时还有 除法 操作，而模数不一定是质数，不一定有逆元，也就无法处理。

再考虑其他做法。我们将 $p$ 次操作看做一个区间，每次 $1$ 操作修改区间一个位置的值，每次都查询整个区间的乘积。单点修改，区间查询，这不就是线段树吗！

我们先将整个区间设为 $1$（因为是乘法操作），如果是 $1$ 操作就将 $i$ 这个位置修改为 $m$，否则的话将 $x$ 位置修改为 $1$，每次都直接查询整个区间的值即可。

对于一些题目，可以通过转换将其变为 线段树 题。

CF1467B Hills And Valleys

模拟/贪心。

一开始想了个假做法，但是伪了。有想法之后还是要多 举反例，想清楚各种情况之后再写，不要没想好就写。

正解首先要明白一个贪心性质：对于一个数来说，将其变为与左右两边相同的数一定更有，因为这样一定能减少个数。那么之后就暴力枚举每一个数，将其修改后减少的值，注意细节即可。

CF1444A Division

数论/分解质因数。

首先最暴力的想法就是枚举。但观察一下就能发现：若 $p$ 不能被 $q$ 整除，则答案就是 $p$。

那么问题是 $p$ 能被 $q$ 整除的情况怎么处理。首先有一个性质：对 $q$ 进行 质因数分解 得 $p_1^{a_1} \times p_2^{a_2}\times \ldots p_i^{a_i}\times \ldots$，$x$ 不能被 $q$ 整除当且仅当 至少存在一个 $a_i$ 在 $x$ 中出现次数少于在 $q$ 中出现次数。是不是很神奇，但想想真是这样的。

有了这么一个性质之后，就可以对 $q$ 进行质因数分解，构造一个 $x$，使得 $p_i$ 的次数为 $a_i-1$，其他全部拉满。形式化的说，设 $p$ 除尽 $p_i$ 后剩下的东西为 $t$，最优解为 $\max \{p_i^{a_i-1} \times t \}$。

CF1444B Divide and Sum

结论/找规律。

只要手玩一下就能发现规律了，多找几组保证正确性，就大胆猜测结论就能过。感觉还是 C 题难一点。

证明的话看题解吧。

$3.26$

P1438 无聊的数列

线段树。

区间修改无无疑是线段树了。对于 等差数列 我们容易想到 查分。设差分数组为 $sum_i$，对区间 $[l,r]$ 加上一个等差数列，相当于

$sum_l+=k$

$sum_i+=d(l+1\leq i \leq r)$

$sum_{r+1}+=-(k+(r-l)\times d)$

然后查询 $a_p$ 的值，只需输出 $a_p \sum_{i=1}^p sum_i$ 即可。然后普通的区间查询和修改即可。

P6476 [NOI Online #2 提高组] 涂色游戏

数论/结论。

首先容易发现最长的连续颜色一定是由 间隔小的数 提供的。

然后假设 $p<q$，且 $p$ 与 $q$ 互质，那么会发现最长的区间一定是在 $kq$ 与 $(k+1)q$ 之间，区间长度即 $(q-2)/p+1$，判断一下即可。

$3.27$

P3369 【模板】普通平衡树

平衡树（×）

权值线段树（√）

平衡树用权值线段树做不是很正常吗。

不过有一说一，权值线段树和平衡树时间复杂度一样，码量还更小，而且作用基本相似。

简单来说最大的作用就是 查询排名为 $x$ 的数。

$3.28$

ABC 197 E Tourist

线性 dp。

考场上想到正解，但没时间做了。

想到取完所有球后一定在该种球的最左边或最右边之后就变成了和 P3842 [TJOI2007]线段 类似的题目了。

P1637 三元上升子序列

线段树。

想到每个数对答案的贡献为在它之前比它小的数的个数乘上在它之后比它大的数的个数，然后用 权值线段树 维护即可。

P2422 良好的感觉

单调栈。

首先有个 贪心 的思想：若 $a_i$ 为最小值时，向两边拓展的越远越好。因此我们记录每个数左边第一个小于等于它的数与右边第一个小于等于它的数，而求形似此类显然可以用 单调栈来维护。用 前缀和 预处理即可

$3.29$

P6492 [COCI2010-2011#6] STEP

线段树。

这是线段树的经典模型：维护区间的前后缀，这种模型的难点在于 区间的合并。

首先我们把 $L$ 看作 $0$，$R$ 看作 $1$，然后维护每个区间的左端点、右端点、前缀最长的合法连续子串、后缀最长的合法连续子串。最关键的合并环节就分类讨论一下就好。

P2184 贪婪大陆

线段树。

一道很好的题。使用线段树来维护 差分 的操作。事实上本题若没有修改操作就是一道普通的差分，加入修改操作就要用线段树。

我们建立两个线段树，一个存区间开始，一个存区间结尾。查询区间 $[l,r]$ 时，只需用差分的思想，输出 $query$_$start(1,r)-query$ _ $end(1,l-1)$

AT2328 [ABC054B] Template Matching

题解

AT2329 [ABC054C] One-stroke Path

题解

AT2330 [ABC054D] Mixing Experiment

题解

$3.20$

P2894 [USACO08FEB]Hotel G

线段树。

首先维护区间中的最长连续空房还是线段树的一种基本模型：维护 从最左端开始的最长连续空房、从最右端开始的最长连续空房，再合并就行了。

不过本题还需要输出满足条件的左端点，就可以用类似 权值线段树查找排名第 $k$ 的数 的方式来做，分别判断是否在左区间、中间、右区间。

P4145 上帝造题的七分钟2 / 花神游历各国

线段树。

本题看上去最麻烦的地方在于如何进行区间开根号的操作。但是通过一些玄学的方法（使用计算器），我们会发现：一个 $\leq 10^{12}$ 的数最多开 $6$ 次根号，因此我们可以直接暴力修改即可。

不过这样是会 T 的。我们还会发现 $1$ 开根号后还是 $1$，因此我们维护区间最大值，若一个区间最大值为 $1$，那就没必要修改了。

SP2713 GSS4 - Can you answer these queries IV

线段树。

双倍经验。

但本题不需要 memset 初始化，用了 memset 会 T 飞。

CF1422A Fence

题解

CF1422B Nice Matrix

题解

$3.31$

CF1422C Bargain

求贡献。

我开始想到了考虑每一位数对答案的贡献为多少，可以分为删前面的数和删后面的数。

删前面的数一共有 $i \times (i-1) / 2$，可以通过找规律发现（在不知道怎么计算时一定要找规律发现性质）。

删后面的数就有些不同，其对答案贡献与剩下的位数有关。剩一位有 $1$ 种情况，即 $10$；剩两位有 $2$ 种情况，即 $200$，以此类推。

CF1422D Returning Home

图论/最短路。

本题思维难度最大的地方是如何 优化存图。

首先本题的入手点就是 $m$ 个传送点,因为本题的点有 $10^9 \times 10^9$，显然不可能都考虑，而走传送点一定是不亏的，因此我们考虑对转送点建图。

首先我们想到的建图是：起始点连向每个传送点一条 $\min(abs(a_i.x-sx),abs(a_i.y-sy))$ 的边；每个传送点连向终点一条 $abs(a_i.x-ex)+abs(a_i.y-ey)$ 的边；传送点点连向其他传送点一条 $\min(abs(a_{i+1}.x-a_{i}.x),abs(a_{i+1}.y-a_i.y))$ 的边。但这么连空间复杂度为 $O(m^2)$ 的，显然会爆。

接下来我们考虑如何优化建边：减少无用边。我们可以发现，若点 $a$ 与点 $b$ 间有中间点，那么先走到中间点再走到 $b$ 一定不会更劣，$a$ 与 $b$ 间也就没必要建边了。因此我们按 $x$ 从小到大排，建相邻传送点的边；再按 $y$ 从小到大排，建相邻传送点的边。再跑 dijkstra 即可。

$4.4$

P3038 [USACO11DEC]Grass Planting G

树链剖分。

还是树链剖分的板子。不过本题要求的是 边权，其实也一样，将边权转化为子节点的权值即可。

同时为了防止重复计算，当 $x$ 和 $y$ 跳到同一条链上时，应该修改 $x+ 1$ 到 $y$ 这一段。

P3833 [SHOI2012]魔法树

树链剖分。

P4114 Qtree1

树链剖分。

又是一道查询 / 修改 边权 的题目。注意一下跳到同一条链上时要 $+1$。

$4.9$

CF6E Exposition

尺取法 $/$ multiset。

一看就是一道尺取法，因为求最长的满足条件的子序列。

而元素最大差值显然可以用 multiset 来维护。

不过一直 RE ，后来看了 CF 的数据才知道有个细节没注意，还是要考虑全面。

P3601 签到题

数论 / 欧拉函数 / 区间筛。