如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。

M_sea的博客

——どうか悔いることなく 明日へ続く道 歩いて——

洛谷6089 [JSOI2015]非诚勿扰

LuoguBZOJ分析先考虑怎么求 $s$ 个候选人中选中了第 $x$ 个的概率。考虑本题怎么做。可以发现要求的是一个类似于逆序对的东西，因此直接树状数组即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================...

  • M_sea
  • 2020 年 02 月 04 日
  • 3 条评论

    • 洛谷6075 [JSOI2015]子集选取

    LuoguBZOJ分析我们可以对于每个数计算方案数，最后再根据乘法原理乘起来。考虑对于每个数如何构造一种合法方案：从左下角出发，每次可以往右走一步或往上走一步，一直走到边界，再将这条折线左上方填上这个数。那么每个数的方案数就不难计算了：一共要走 $k$ 步，每部有 $2$ 种方法，因此答案为 $2^k$。所以总的答案为 $2^{nk}$。代码// ======================...

  • M_sea
  • 2020 年 02 月 04 日
  • 暂无评论

    • 洛谷6088 [JSOI2015]字符串树

    LuoguBZOJ分析对于每个询问，考虑差分。那么我们仅需要求出每个点到根的路径上有多少个串以 $S$ 为前缀。容易想到对于每个点维护一棵 Trie，将它到根的路径上所有字符串插入时将经过的节点权值加 $1$，询问仅需要跳到那个节点然后它的权值就是答案。这样子复杂度过高，可持久化一下即可。代码// =================================== // author...

  • M_sea
  • 2020 年 02 月 04 日
  • 暂无评论

    • 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$ 个 #...

  • M_sea
  • 2020 年 02 月 03 日
  • 暂无评论

    • BZOJ5172 [Jsoi2014]学生选课

    BZOJ分析显然二分答案，考虑 check()。注意到每个学生仅有 2 种选择，因此可以考虑 2-SAT。对于每一个学生，枚举所有排名在 $[mid+1,n]$ 内的学生并连边，然后缩点判断即可。具体的连边方法可以看代码。代码// =================================== // author: M_sea // website: http://m-sea...

  • M_sea
  • 2020 年 02 月 02 日
  • 暂无评论

    • BZOJ5038 [Jsoi2014]打兔子

    BZOJ分析首先特判 $k\geq\left\lceil\frac{n}{2}\right\rceil$ 的情况，此时可以消灭所有兔子。但是上面的特判有一个例外：当 $n=3,k=2$ 时只能消灭两块菜地中的兔子，显然打最多的两块。考虑剩下的情况。容易发现，最优解中不会存在相邻的两块菜地都开过枪。考虑一个 DP：设 $dp_{i,j,0/1}$ 表示前 $i$ 块菜地，开了 $j$ 枪，当前...

  • M_sea
  • 2020 年 02 月 02 日
  • 暂无评论

    • BZOJ5173 [Jsoi2014]矩形并

    BZOJ分析考虑对于每个矩形，求出其它矩形与它的交的面积之和。我们把其它矩形都加上 $1$，然后统计该矩形内的和即可。进一步可以得到这样一个做法：首先把所有矩形都加上 $1$，然后对于每个矩形统计它内部的和，减去它的面积即为所求。最后加起来除以 $n(n-1)$ 即为答案。那么问题就在于怎么支持矩形加、矩形求和了。有一个在线的做法是二维树状数组，但空间无法承受。因此可以考虑离线，用扫描线替代...

  • M_sea
  • 2020 年 02 月 02 日
  • 暂无评论

    • BZOJ5034 [Jsoi2014]歌剧表演

    BZOJ分析知道每个信息后，我们都可以确定一些人对应一些姓名。考虑把所有人划分成若干个集合，使得每个集合内的人两两无法分辨。具体维护起来并不难：一开始所有人构成一个集合；对于每次输入的信息 $a_1,a_2,\cdots,a_k$，将其划分为若干段，满足每段内所在的集合相同，然后将每段单独成一个集合。每个信息处理完后，如果存在一个大小为 $1$ 的集合，那么他就已经确定了。具体实现时用 st...

  • M_sea
  • 2020 年 01 月 31 日
  • 暂无评论

    • BZOJ5031 [Jsoi2014]支线剧情2

    BZOJ分析容易想到树形 DP。设 $f_u$ 为 $u$ 处有一个存档点，接下来不存档，访问完以 $u$ 为根的子树中所有剧情的最短时间。不难得到转移（这里的 $s_u$ 表示以 $u$ 为根的子树中叶子节点的个数）再设 $dp_u$ 为 $u$ 处有一个存档点，接下来可以存档，访问完以 $u$ 为根的子树中所有剧情的最短时间。$dp_u$ 的转移有些复杂。首先每个子节点 $v$ 可以不存...

  • M_sea
  • 2020 年 01 月 31 日
  • 暂无评论

    • 洛谷4041 [AHOI2014/JSOI2014]奇怪的计算器

    Luogu分析我们把输入的值从小到大排序，构成序列 $a$。那么可以发现在操作后 $a$ 序列仍为不降序列。也就是说，每做完一个操作后，$<L$ 的数一定是一个前缀，$>R$ 的数一定是一个后缀，而这个前后缀可以直接在线段树上二分得到。那么我们只需要写一棵支持区间加、区间减、区间乘、区间加上 $k\times c_i$，区间赋值的线段树就好了。关于线段树的写法，从题解中看到一个奇...

  • M_sea
  • 2020 年 01 月 31 日
  • 暂无评论