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

M_sea的博客

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

洛谷5770 [JSOI2016]无界单词

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

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

    • 洛谷5545 [JSOI2016]炸弹攻击2

    LuoguLOJBZOJ分析枚举发射源，并将防御塔和敌人极角排序。按极角序枚举每个防御塔，则它可以和与它极角相差 $\pi$ 以内的所有防御塔组成能量墙并产生范围内敌人数的贡献。极角排序后预处理前缀和即可 $\mathcal{O}(n)$ 计算。总时间复杂度 $\mathcal{O}(n^2\log n)$。代码// =================================== /...

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

    • 洛谷4044 [AHOI2014/JSOI2014]保龄球

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

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

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

    LuoguLOJBZOJ分析一个想法是如果 $a_i+a_j$ 不为质数，则 $i,j$ 之间连一条边，于是问题变为求最大团。直接做似乎不太可行。因为最大团等于补图的最大独立集，因此考虑求补图的最大独立集。考虑如果补图中 $i,j$ 有一条边，则 $a_i+a_j$ 为质数，即要么 $a_i=a_j=1$，要么一奇一偶。也就是说，补图中除去 $a_i=1$ 的点的部分是一个二分图，而二分图...

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

    • 洛谷5774 [JSOI2016]病毒感染

    LuoguLOJBZOJ分析首先那个条件的意思是如果往回走到了某个未被治愈的村庄，则必须治愈它。考虑 DP。设 $dp_{i}$ 表示前 $i$ 个村庄已经被治愈且此时在 $i$ 的最小死亡人数。转移枚举往回走到的位置，可以得到边界为 $w_{i,i}=s_n-s_i$。最后答案即为 $dp_n$。总时间复杂度 $\mathcal{O}(n^2)$。代码// ================...

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

    • 洛谷5769 [JSOI2016]飞机调度

    LuoguLOJBZOJ分析先求出一个 $dis_{i,j}$，表示 从 $i$ 飞到 $j$ 并能再次起飞的最短时间。一开始令 $dis_{i,j}=t_{i,j}+p_j$，然后 Floyd 即可。考虑如何判断一架飞机 $x_i\to y_i$ 后能否 $x_j\to y_j$。不难得到判断条件如果一架飞机 $x_i\to y_i$ 后能 $x_j\to y_j$，则从 $i$ 向 $j...

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

    • 洛谷5544 [JSOI2016]炸弹攻击

    LuoguLOJBZOJ分析搜了一圈似乎都写的随机算法，那就写个爬山吧 /kel对于每次随机出来的坐标 $(x,y)$，考虑如何计算答案。首先选择的半径显然越大越好，枚举所有建筑即可算出这个最大的半径，再枚举所有敌人即可算出答案。另外我的爬山是直接在退火的基础上改的。因为这题值域比较小，所以把初温和末温都调小一点会比较好。代码// ==============================...

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

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

    LuoguLOJBZOJ分析第一、二种情况不难求出，Manacher 即可。下面考虑第三种情况。枚举中点 $i$，则“扭动的回文串”由三段组成：在 A 或 B 中的由 $i$ 扩展出的回文串，在 A 中往左扩展出的串，在 B 中往右扩展出的串。显然后两段应相反，于是二分+哈希即可求出后两段的最长长度。代码// =================================== // ...

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

    • 洛谷4322 [JSOI2016]最佳团体

    LuoguLOJBZOJ分析分数规划问题，考虑二分答案，推一推式子可以得到将 $p_i-mid\times s_i$ 作为价值，树形背包即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // ==========================...

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

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

    LuoguLOJBZOJ分析先考虑一个 $\mathcal{O}(n^2)$ 的做法。先求出以每个节点为根，整棵树的哈希值。直接 DFS $n$ 次即可。然后，把 $A$ 的这 $n$ 个哈希值存到 map 中，然后枚举 $B$ 的每一个叶子节点，查一下删掉它后的哈希值是否在 map 中即可。这个算法的主要瓶颈在于求哈希值那一部分，考虑用换根 DP 优化这个过程。异或满足可减性，很容易抵消掉...

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