JSOI 解题报告
[JSOI2010] 旅行
链接
题解
动态规划。
先把边按照边权从小到大排序，然后钦定前 $x$ 条边在路径上。
于是我们可以考虑设 $dp_{i,j,k}$ 表示到了点 $i$ 经过 $j$ 条被钦定的边使用魔法次数为 $k$ 的最短路，于是就可以转移了：
假设我们现在考虑到的边是 $u\rightarrow v$，那么
如果钦定了这条边：$dp_{u,j,k}+w_{j+1}\rightarrow dp_{v,j+1,k}$
如果没有钦定这条边：
使用魔法：$dp_{u,j,k}+w_{j+1}\rightarrow dp_{v,j+1,k+1}$
不使用魔法：$dp_{u,j,k}+\operatorname{dist}(u,v)\rightarrow dp_{v,j+1,k+1}$
每次转移用类似 $\texttt{Dijkstra}$ 的方法跑一遍即可。
代码
1 |
|
[JSOI2010] 找零钱的洁癖
链接
题解
网上有人说这道题是错题。
考虑搜索。当前考虑的硬币有正负两种贡献方式。
然而搜索可能会超时，需要设定一个不同值进队次数的阈值来保证不会搜索过多次，但是这样可能无法搜出结果。
考虑贪心，将硬币按照面值排序，从大往小选即可。（为什么呢，因为那些搜索没有跑出答案的数据硬笔面值全都是 $2$ 的幂，所以直接二进制贪心）
代码
1 |
|
[JSOI2010] 俄罗斯方块
链接
题解
毒瘤题。
注意到，$7$ 种方块通过旋转最多构造出 $19$ 中摆放方法。预处理一下相对高度和绝对高度即可。
然后方块数量很少，可以状压并且使用线段树维护。每一次直接暴力判断并且暴力修改该方块左右的一些高度即可。
代码
1 |
|
[JSOI2010] 挖宝藏
链接
题解
注意到挖到一个宝藏后挖的坑是个倒着的三角形，于是我们就可以把宝藏看作是一段区间，然后通过区间长度计算代价。
考虑 $\texttt{dp}$。将宝藏按右端点排序，设 $dp_i$ 表示挖 $1\sim i$ 号宝藏，且钦定必须挖 $i$ 的答案。
枚举一下之前的宝藏 $j$，分成 $3$ 种情况
$j$ 被包含在 $i$ 内：挖 $i$ 的同时可以把 $j$ 挖出来，提前预处理即可。
$j$ 与 $i$ 无交：$dp_j+val_i-cost_i\rightarrow dp_i$
$j$ 与 $i$ 有交：要容斥掉交的区间的代价，但是有可能有些宝藏被包含在这个区间内。因为右端点递增，拿个指针扫一下，没了。
代码
1 |
|
[JSOI2010] 游戏
链接
题解
什么神仙题啊。
考虑对链进行染色，如果链 $(x,y)$ 是良的就染成白色，否则就是黑色。
那么接下来就是完全图求同色三角形个数。
找一下角的个数 $x$，那么答案就是 $\binom{n}{3}-x$。
考虑快速判断某条链是否是良的，想到在模 $8$ 的意义下计算，于是就有
由于 $1=(001)_2,5=(101)_2$，所以考虑倒数第三位是否为 $0$。
而这一位可以由两个地方贡献过来：所有数和的倒数第三位和第偶数个数和的最后一位。
然而第一个已知，只要考虑第二个。
对数列讨论一下：
情况 $0$，所有数的二进制最后一位都为 $0$。
这时没有第二类贡献，直接算第一类即可。
情况 $1$，所有数的二进制最后一位都为 $1$。
这时第二类贡献为所有数最后一位贡献之和除以 $2$。
情况 $2$，剩下的所有情况。
使用类似于括号序列的方法即可。
然后树形 $\texttt{dp}$。设 $dp_{x,i,j,k}$ 表示当前在 $x$，路径上的和 $\bmod 8$ 为 $i$，最低位的和 $\bmod 4$ 为 $j$，情况为 $k$ 的子树中相应的点的个数。
换根 $\texttt{dp}$ 一下就好了。
代码
1 |
|
[JSOI2010] 排名
链接
题解
套路贪心题。
第一问建反图然后拓扑排序即可。
第二问直接从 $0$ 号同学（假想的虚拟人物，成绩最高）开始贪心即可。
代码
1 |
|
[JSOI2011] Apple 的美食
链接
题解
玄学题。
考虑先推柿子。
然后有一个结论：两个断点肯定只会在前 $100$ 和后 $100$ 个，暴力枚举即可。注意到 $n\leq 10^6$，不能暴力求，但是模数比 $20$ 小，所以可以求循环节。由于循环节可能达到 $n-1$，所以要 $\texttt{kmp}$ 求。
代码
1 |
|
[JSOI2011] 柠檬
链接
题解
斜率优化 $\texttt{dp}$ 入门题。
首先有个显然的性质：每一段的两端的数相同。
如果不同的话，那些不同的数也不会给这一段有贡献，反而把它们分到另外的段去期望对其他段产生贡献，才能使贡献最大化。
于是可以设 $dp_i$ 表示前面 $i$ 个数产生的最大贡献，$c_i$ 表示这个数是第几次出现，则有
可这是 $O(n^2)$ 的，跑不过,考虑斜率优化。
观察一下原来的式子，把与 $j$ 有关的放到 $y,x$ 项，与 $j$ 无关的放到 $k,b$ 项，则有
移项之后，有
于是，有
于是考虑用一个单调栈维护 $k$ 就行。
代码
1 |
|
[JSOI2011] 分特产
链接
题解
先考虑没有每个人至少一个的限制，那么答案就是可重组合，也就是
然后既然有了这个限制不太好处理的话。那么容斥做肯定可以。
考虑至少有 $t$ 个同学没有的情况，那么钦定前 $t$ 个同学没有特产，后面的有不有都无所谓，因为这里求的是至少 $t$ 个同学没有，所以答案为 $f(n-t)$
。
于是可以容斥出答案，就是这个：
代码
1 |
|
[JSOI2011] 棒棒糖
链接
题解
莫队。
考虑直接用莫队维护一下当前区间内颜色的集合。然后每一次询问考虑最多的颜色是否超过区间的一般就好了。
代码
1 |
|
[JSOI2011] 任务调度
链接
题解
左偏树模板题。
权值最小任务不唯一也就是说根与某个儿子的权值相等，利用这个性质即可。
剩下的操作都是基本操作，直接左偏树维护。
代码
1 |
|