CF1264D2 Beautiful Bracket Sequence (hard version)
CodeforcesLuogu分析考虑枚举一个分界点，如果左边的 ( 和右边的 ) 相等，那么深度就是左边的 ( 数。设 $l$ 为左边的 ( 数、$f$ 为左边的 ? 数、$r$ 为右边的 ) 数、$g$ 为右边的 ? 数，枚举深度，方案数为时间复杂度 $\mathcal{O}(n)$。代码// ==================================== // autho...
如果有写的不好的文章欢迎评论，我会在有时间的时候重写一篇更好的。
M_sea 的博客
歩み続けて 辿り着く先へと洛谷6962 [NEERC2017]Knapsack Cryptosystem
LuoguGym分析一个做法是直接 meet in the middle，复杂度 $\mathcal{O}(2^{n/2})$，并不能过 $n\leq 64$。但是题目中还有一个奇妙的性质 $a_i > \sum_{j=1}^{i-1} a_j$，套用得到 $a_1<2^{65-n}$。发现随着 $n$ 增大 $a_i$ 的取值范围逐渐减小，这启发我们在 $n$ 大时去枚举 $a...
洛谷6982 [NEERC2015]Jump
LuoguGym分析我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了，稍后再来考虑怎么问。规定一个串对应的集合就是它所有 $1$ 的下标集合，下面不再区分串和集合。假设问出来的串是 $I$，考虑求出 $A=S\oplus I$。考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$，即 $|A\oplus\{u,v\...
洛谷6967 [NEERC2016]Delight for a Cat
LuoguGym分析考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭，可以列出线性规划用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==============...
CF464D World of Darkraft - 2
CodeforcesLuogu分析显然装备之间没有区别，我们只要计算一种装备的期望，然后乘上 $k$ 即可。考虑倒推。设 $dp_{i,j}$ 表示剩余 $i$ 个怪物、装备等级为 $j$ 期望获得的金币数，转移有三种：选到了其它装备：概率为 $\frac{k-1}{k}$，期望收益为 $dp_{i-1,j}$。选到了等级为 $j+1$ 的当前装备：概率为 $\frac{1}{k(j+1)}...
LOJ6252 「CodePlus 2017 11 月赛」大吉大利，晚上吃鸡！
LOJ分析先考虑第一个条件。设 $c_i$ 为经过 $i$ 的 $s\to t$ 的最短路数，那么应该有 $c_a+c_b=c_t$。再考虑第二个条件。我们可以对每个点求出最短路图上不能到达它的且它不能到达的点集，然后存到一个 bitset 里。这可以直接拓扑排序求出。枚举 $a$，合法的 $b$ 应该满足 $c_t-c_a=c_b$。开一个 map 存下每个 $c$ 对应的点集，再和之前预...
AGC016E Poor Turkeys
AtCoder分析考虑求出如果钦定 $i$ 活到最后，那么有哪些火鸡需要送死。倒着考虑每个人。如果 $x_i,y_i$ 后面都需要送死，那么 $i$ 必死；否则随便找一个后面不要送死的送死即可。可以发现 $i,j$ 可能同时活到最后当且仅当不存在一只火鸡既需要为 $i$ 送死、又需要为 $j$ 送死，可以用 bitset 加速判断。代码// =========================...
Comet OJ Contest #2 D 错综的光影所迷惑的思念是
Comet OJ分析可以发现一个点集的所有直径的中点都相同。为了方便我们把边也拆成点，这样子中点一定是一个点。枚举中点和半径，那么深度小于半径的点任意选，深度等于半径的必须有至少两棵子树中选了，容斥一下即可。代码// ==================================== // author: M_sea // website: https://m-sea-blog...
洛谷2519 [HAOI2011]Problem A
Luogu分析每个人的话相当于 $[a_i+1,n-b_i]$ 中的人排名相同。那么如果两个人的话不同且对应的区间无交，他们就可能都说了真话。把相同的区间缩在一起，问题变成每个区间有一个权值，选出若干个无交的区间使得权值和最大。这个可以直接 DP，把所有区间按右端点排序后，二分找到最后的左端点小于当前右端点的位置，然后转移即可。注意把 $a_i+1>n-b_i$ 的人掉，这些人一定说了...
洛谷4351 [CERC2015]Frightful Formula
LuoguGym分析先考虑 $c=0$ 的情况。我们计算每个 $l_i$ 和 $t_i$ 对 $(n,n)$ 的贡献。只考虑 $l_i$，那么相当于从 $(i,1)$ 走到 $(n,n)$，第一步必须往右，往右走一步乘 $a$，往下走一步乘 $b$，求所有路径的权值和。这个东西显然等于可以发现，当 $i+j\leq n-2$ 时，贡献就是 $c(a+b)^{i+j}$；当 $i+j>n...