LOJ6053 简单的函数
LOJ分析注意到如果令 $f(2)=1$，那么当 $j=1$ 时这部分贡献会比正确的值少 $2$，于是此时直接把算出来的结果加上 $2$ 即可。代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =========================...
M_sea 发布的文章
- 首页
- M_sea
洛谷6083 [JSOI2015]symmetry
LuoguBZOJ分析在原方阵的基础上构造出 $6$ 个方阵，分别为原方阵沿 $4$ 条轴对称之后的方阵、旋转 $90^\circ$ 后的方阵、旋转 $180^\circ$ 后的方阵。然后对这 $7$ 个方阵做一遍哈希。现在一个暴力做法是，枚举边长和左上角的坐标，然后利用哈希判断它是否满足某些条件。这样子是 $\mathcal{O}(n^3)$ 的，并跑不过。考虑到如果存在一个边长为 $k$...
洛谷5770 [JSOI2016]无界单词
LuoguLOJBZOJ分析容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $...
洛谷5545 [JSOI2016]炸弹攻击2
LuoguLOJBZOJ分析枚举发射源，并将防御塔和敌人极角排序。按极角序枚举每个防御塔，则它可以和与它极角相差 $\pi$ 以内的所有防御塔组成能量墙并产生范围内敌人数的贡献。极角排序后预处理前缀和即可 $\mathcal{O}(n)$ 计算。总时间复杂度 $\mathcal{O}(n^2\log n)$。代码// =================================== /...
洛谷4044 [AHOI2014/JSOI2014]保龄球
LuoguLOJBZOJ分析太神了...看了好久才看懂...先考虑一些性质：如果上一轮是全中，那么一定放第一轮最小的补中（可以让第一轮最大的补中放在其它补中后），或者总分最大的失误。如果上一轮是补中，那么一定放第一轮最大的。可以发，我们要么取第一轮最小的补中，要么取第一轮最大的补中。考虑最优解大概是什么样子，可以发现是全中补中交替放，最后再放失误，而第一个失误要么是第一轮最大的，要么是总分最...
洛谷5771 [JSOI2016]反质数序列
LuoguLOJBZOJ分析一个想法是如果 $a_i+a_j$ 不为质数，则 $i,j$ 之间连一条边，于是问题变为求最大团。直接做似乎不太可行。因为最大团等于补图的最大独立集，因此考虑求补图的最大独立集。考虑如果补图中 $i,j$ 有一条边，则 $a_i+a_j$ 为质数，即要么 $a_i=a_j=1$，要么一奇一偶。也就是说，补图中除去 $a_i=1$ 的点的部分是一个二分图，而二分图...
洛谷5774 [JSOI2016]病毒感染
LuoguLOJBZOJ分析首先那个条件的意思是如果往回走到了某个未被治愈的村庄，则必须治愈它。考虑 DP。设 $dp_{i}$ 表示前 $i$ 个村庄已经被治愈且此时在 $i$ 的最小死亡人数。转移枚举往回走到的位置，可以得到边界为 $w_{i,i}=s_n-s_i$。最后答案即为 $dp_n$。总时间复杂度 $\mathcal{O}(n^2)$。代码// ================...
洛谷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...
洛谷5544 [JSOI2016]炸弹攻击
LuoguLOJBZOJ分析搜了一圈似乎都写的随机算法，那就写个退火吧 /cy对于每次随机出来的坐标 $(x,y)$，考虑如何计算答案。首先选择的半径显然越大越好，枚举所有建筑即可算出这个最大的半径，再枚举所有敌人即可算出答案。然而直接蒯个退火来并过不去，可以把“以一定概率接受”去掉，或者把每次随机出的那个向量的模搞小一点。代码// =============================...
洛谷4324 [JSOI2016]扭动的回文串
LuoguLOJBZOJ分析第一、二种情况不难求出，Manacher 即可。下面考虑第三种情况。枚举中点 $i$，则“扭动的回文串”由三段组成：在 A 或 B 中的由 $i$ 扩展出的回文串，在 A 中往左扩展出的串，在 B 中往右扩展出的串。显然后两段应相反，于是二分+哈希即可求出后两段的最长长度。代码// =================================== // ...