洛谷6093 [JSOI2015]套娃
LuoguBZOJ分析禁 止 套 娃当所有套娃都不套套娃时，答案为 $\sum in_i\times b_i$。而把 $i$ 套进 $j$ 里面，答案会减少 $out_i\times b_j$。对于每个套娃，我们一定会选能选的 $out_i$ 最大的套在它里面。我们把所有套娃按 $b_i$ 从大到小排序，然后依次选择能选的 $out_j$ 最大的套娃套在它里面，这样子就能得到最优解。证明：假...
M_sea 发布的文章
- 首页
- M_sea
洛谷6082 [JSOI2015]salesman
LuoguBZOJ分析首先，一个点能停留 $s$ 次，等价于可以进入它的 $s-1$ 棵子树。先考虑第一问。 $dp_{i}$ 表示以 $i$ 为根的子树的最大收益，转移时在所有 $dp$ 值非负的子树选最大的那些进入即可。再考虑第二问。设 $f_i$ 表示以 $i$ 为根的子树中最大收益是否唯一。如果当前子树最大收益不唯一，那么有以下可能：一棵子树最大收益不唯一。选了一棵最大收益为 $0$...
洛谷6089 [JSOI2015]非诚勿扰
LuoguBZOJ分析先考虑怎么求 $s$ 个候选人中选中了第 $x$ 个的概率。考虑本题怎么做。可以发现要求的是一个类似于逆序对的东西，因此直接树状数组即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================...
洛谷6075 [JSOI2015]子集选取
LuoguBZOJ分析我们可以对于每个数计算方案数，最后再根据乘法原理乘起来。考虑对于每个数如何构造一种合法方案：从左下角出发，每次可以往右走一步或往上走一步，一直走到边界，再将这条折线左上方填上这个数。那么每个数的方案数就不难计算了：一共要走 $k$ 步，每部有 $2$ 种方法，因此答案为 $2^k$。所以总的答案为 $2^{nk}$。代码// ======================...
洛谷6088 [JSOI2015]字符串树
LuoguBZOJ分析对于每个询问，考虑差分。那么我们仅需要求出每个点到根的路径上有多少个串以 $S$ 为前缀。容易想到对于每个点维护一棵 Trie，将它到根的路径上所有字符串插入时将经过的节点权值加 $1$，询问仅需要跳到那个节点然后它的权值就是答案。这样子复杂度过高，可持久化一下即可。代码// =================================== // author...
BZOJ5036 [Jsoi2014]回文串
BZOJ分析首先在每两个字符中插入 #，然后跑 Manacher。记 Manacher 求出的数组为 $f$。考虑每个询问。我们首先扩展到插入 # 后的串，即令 $l\leftarrow 2\times l-1$，$r\leftarrow 2\times r+1$。设新串中的答案为 $ans'$，则原答案为 $\frac{ans'-(r-l+2)}{2}$，意思是去掉 $r-l+2$ 个 #...
BZOJ5172 [Jsoi2014]学生选课
BZOJ分析显然二分答案，考虑 check()。注意到每个学生仅有 2 种选择，因此可以考虑 2-SAT。对于每一个学生，枚举所有排名在 $[mid+1,n]$ 内的学生并连边，然后缩点判断即可。具体的连边方法可以看代码。代码// =================================== // author: M_sea // website: http://m-sea...
BZOJ5038 [Jsoi2014]打兔子
BZOJ分析首先特判 $k\geq\left\lceil\frac{n}{2}\right\rceil$ 的情况，此时可以消灭所有兔子。但是上面的特判有一个例外：当 $n=3,k=2$ 时只能消灭两块菜地中的兔子，显然打最多的两块。考虑剩下的情况。容易发现，最优解中不会存在相邻的两块菜地都开过枪。考虑一个 DP：设 $dp_{i,j,0/1}$ 表示前 $i$ 块菜地，开了 $j$ 枪，当前...
BZOJ5173 [Jsoi2014]矩形并
BZOJ分析考虑对于每个矩形，求出其它矩形与它的交的面积之和。我们把其它矩形都加上 $1$，然后统计该矩形内的和即可。进一步可以得到这样一个做法：首先把所有矩形都加上 $1$，然后对于每个矩形统计它内部的和，减去它的面积即为所求。最后加起来除以 $n(n-1)$ 即为答案。那么问题就在于怎么支持矩形加、矩形求和了。有一个在线的做法是二维树状数组，但空间无法承受。因此可以考虑离线，用扫描线替代...
BZOJ5034 [Jsoi2014]歌剧表演
BZOJ分析知道每个信息后，我们都可以确定一些人对应一些姓名。考虑把所有人划分成若干个集合，使得每个集合内的人两两无法分辨。具体维护起来并不难：一开始所有人构成一个集合；对于每次输入的信息 $a_1,a_2,\cdots,a_k$，将其划分为若干段，满足每段内所在的集合相同，然后将每段单独成一个集合。每个信息处理完后，如果存在一个大小为 $1$ 的集合，那么他就已经确定了。具体实现时用 st...