洛谷6962 [NEERC2017]Knapsack Cryptosystem
Luogu Gym 分析 一个做法是直接 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$ 大时去...
分类 题解 下的文章
- 首页
- 题解
洛谷6982 [NEERC2015]Jump
Luogu Gym 分析 我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了，稍后再来考虑怎么问。 规定一个串对应的集合就是它所有 $1$ 的下标集合，下面不再区分串和集合。 假设问出来的串是 $I$，考虑求出 $A=S\oplus I$。 考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$，即 $|A\oplus...
洛谷6967 [NEERC2016]Delight for a Cat
Luogu Gym 分析 考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭，可以列出线性规划 用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =======...
CF464D World of Darkraft - 2
Codeforces Luogu 分析 显然装备之间没有区别，我们只要计算一种装备的期望，然后乘上 $k$ 即可。 考虑倒推。设 $dp_{i,j}$ 表示剩余 $i$ 个怪物、装备等级为 $j$ 期望获得的金币数，转移有三种： 选到了其它装备：概率为 $\frac{k-1}{k}$，期望收益为 $dp_{i-1,j}$。 选到了等级为 $j+1$ 的当前装备：概率为 $\frac{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...
洛谷2519 [HAOI2011]Problem A
Luogu 分析 每个人的话相当于 $[a_i+1,n-b_i]$ 中的人排名相同。 那么如果两个人的话不同且对应的区间无交，他们就可能都说了真话。 把相同的区间缩在一起，问题变成每个区间有一个权值，选出若干个无交的区间使得权值和最大。 这个可以直接 DP，把所有区间按右端点排序后，二分找到最后的左端点小于当前右端点的位置，然后转移即可。 注意把 $a_i+1>n-b_i$ 的人掉，这...
洛谷4351 [CERC2015]Frightful Formula
Luogu Gym 分析 先考虑 $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+...
洛谷6920 [ICPC2016 WF]Clock Breaking
Luogu Gym 分析 竟然一遍 A 了，写篇题解纪念一下。 如果一个灯管一直都是 X 或者一直都是 .，那它就有可能恒亮或恒灭。 枚举起始时间，那么如果一个不可能恒亮或恒灭的灯管没有正常发光，那么这个起始时间就不合法。 如果对于某个起始时间，某个灯管都正常发光，那它就有可能是正常工作的。 如果一个灯管的可能性超过 $2$ 种，那么就输出 ?，否则输出对应的东西即可。 难点主要在于码，但是...