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

M_sea的博客

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

洛谷4044 [AHOI2014/JSOI2014]保龄球

Luogu分析太神了...看了好久才看懂...先考虑一些性质：如果上一轮是全中，那么一定放第一轮最小的补中（可以让第一轮最大的补中放在其它补中后），或者总分最大的失误。如果上一轮是补中，那么一定放第一轮最大的。可以发，我们要么取第一轮最小的补中，要么取第一轮最大的补中。考虑最优解大概是什么样子，可以发现是全中补中交替放，最后再放失误，而第一个失误要么是第一轮最大的，要么是总分最大的。但是由于...

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

    • 洛谷5771 [JSOI2016]反质数序列

    Luogu分析考虑建图。如果 $x_i+x_j$ 不为质数则连一条边。则问题变为求最大团。这张图似乎没有什么优秀的性质，因此考虑求补图最大独立集。容易发现补图上除了 $x_i=1$ 的点，剩下的部分是二分图（因为只有奇数和偶数间连边），而二分图最大独立集是很好求的。考虑有 $x_i=1$ 的点怎么办。容易发现我们至多选择一个 $x_i=1$ 的点，因此只保留一个即可。这样子整张补图都为二分图...

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

    • 洛谷5774 [JSOI2016]病毒感染

    Luogu分析首先那个规定的意思是如果往左走就要把左边所有没治愈的村庄治愈。可以发现整个过程可以划分成若干段，每段以任意顺序治愈后回到该段的起点，再治愈下一段。考虑 DP。设 $dp_i$ 表示治愈前 $i$ 个村庄的最小死亡人数。记 $s$ 为 $a$ 的前缀和，$w_{i,j}$ 为从 $i$ 出发治愈 $[i,j]$ 中所有村庄再回到 $i$ 的最小死亡人数，容易得到转移边界为 $w_...

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

    • 洛谷5770 [JSOI2016]无界单词

    Luogu分析容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $s$，如果 $...

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

    • 洛谷5769 [JSOI2016]飞机调度

    Luogu分析预处理出一个 $dis_{i,j}$ 表示从 $i$ 起飞到 $j$ 并能再次起飞的最短时间。将 $T_{i,j}+p_j$ 作为 $dis_{i,j}$ 的初始值然后 Floyd 即可。那么如果 $d_i+t_{x_i,y_i}+p_{y_i}+dis_{y_i,x_j}\leq d_j$ ，说明 $i$ 航线的飞机能给 $j$ 航线用。考虑建立一个图论模型。如果 $i$ 航...

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

    • 洛谷5544 [JSOI2016]炸弹攻击

    Luogu分析想一想没有什么思路，可以考虑写退火。然后由于种种原因，正常写法的退火不太能过，把“以一定概率接受”去掉就能过了。事实上网上大部分题解的“以一定概率接受”都等价于“不接受”。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ====...

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

    • 洛谷5503 [JSOI2016]灯塔

    Luogu分析一个决策单调性做法移一下项发现我们要对每个 $i$ 求出显然 $\left\lceil\sqrt{|i-j|}\right\rceil$ 的取值只有 $\mathcal{O}(\sqrt{n})$ 级别，可以枚举它的取值，用 ST 表求出对应区间的最大值即可。代码// =================================== // author: M_sea ...

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

    • 洛谷4324 [JSOI2016]扭动的回文串

    Luogu分析先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一段是 $...

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

    • 洛谷4323 [JSOI2016]独特的树叶

    Luogu分析先考虑一个 $\mathcal{O}(n^2)$ 的做法。先求出以每个节点为根，整棵树的哈希值。然后，把 $A$ 的所有 $n$ 个哈希值丢到一个 map 里去，然后枚举 $B$ 的每一个叶子节点，判断删掉后的哈希值是否在 map 中即可。这个算法的主要瓶颈在于 $\mathcal{O}(n^2)$ 求哈希值，我们考虑优化这个过程。异或满足可减性，很容易抵消掉。所以我们设哈希函...

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

    • 洛谷4322 [JSOI2016]最佳团体

    Luogu分析二分答案 $mid$。考虑 check()。将 $p_i-mid\times s_i$ 作为价值跑树形背包即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==================================...

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