M_sea 发布的文章
- 首页
- M_sea
CF1446D2 Frequency Problem (Hard Version)
Codeforces分析先判掉只有一种数的情况，答案显然为 $0$。再判掉原序列中有两种出现次数都是最多的数的情况，答案显然为 $n$。那么现在出现次数最多的数唯一。找到这个数，设为 $x$，那么有结论：答案段出现次数最多的数一定是 $x$。这是因为如果某一段出现次数最多的数不是 $x$，那么我们可以每次把这一段增长 $1$，根据介值定理，此过程中一定会有 $x$ 的出现次数等于原来最多的出...
CF1264D2 Beautiful Bracket Sequence (hard version)
CodeforcesLuogu分析考虑枚举一个分界点，如果左边的 ( 和右边的 ) 相等，那么深度就是左边的 ( 数。设 $l$ 为左边的 ( 数、$f$ 为左边的 ? 数、$r$ 为右边的 ) 数、$g$ 为右边的 ? 数，枚举深度，方案数为时间复杂度 $\mathcal{O}(n)$。代码// ==================================== // autho...
洛谷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...