洛谷5366 [SNOI2017]遗失的答案
LuoguLOJ分析首先特判掉 $G\nmid L$ 的情况。为了方便，将 $L$、$n$、$X$ 都除以 $G$。这样子问题转化为在 $[1,n]$ 中选若干个数，必须选 $X$，选出来的数 $\gcd$ 为 $1$、$\operatorname{lcm}$ 为 $L$ 的方案数。我们先不管那个必须选 $X$ 的条件，想一想怎么做。注意到值域只有 $10^8$，即最多只有 $8$ 个质因子...
M_sea 发布的文章
- 首页
- M_sea
LOJ2695 「POI2012」衣帽间 Cloakroom
LOJ分析考虑将所有询问离线并按左端点从小到大排序。则 $a_i\leq m$ 的限制我们可以通过将物品按左端点排序并依次加入来解决。考虑 DP。设 $dp_i$ 表示物品权值之和为 $i$ 时右端点最远能到哪。这样子对于每个询问我们只需要查询 $dp_k$ 是否大于 $m+s$ 即可。转移类似于 0/1 背包。代码// ===================================...
洛谷5405 [CTS2019]氪金手游
LuoguLOJ分析首先考虑原树为外向树的情况。此时 $u$ 子树中所有点选择时间都应比 $u$ 晚。考虑这个概率。设 $u$ 子树 $w_i$ 的和为 $s$，整棵树 $w_i$ 的和为 $S$，则 $u$ 子树中所有点选择时间都比 $u$ 晚的概率为这个概率只和子树有关，因此可以设 $dp_{i,j}$ 表示以 $i$ 为根的子树 $w_i$ 和为 $j$ 的概率，转移即为树形背包。现在...
ARC096D Sweet Alchemy
AtCoderLuogu分析考虑差分，则问题变为每次选择一棵子树，消耗 $\sum m_i$ 的材料，造出 $sz$ 个物品，且每棵不是原树的子树都只能选至多 $D$ 次。令每棵子树的 $m_i$ 之和为其代价，$sz$ 为其收益，则相当于一个多重背包。然而 $D$ 在 $10^9$ 级别，直接多重背包显然无法通过。考虑一个错误的贪心：设 $w_i$ 为收益，$v_i$ 为代价，按 $\fr...
洛谷4694 [PA2013]Raper
Luogu分析设 $f(x)$ 为造恰好 $k$ 张光盘的最小花费。感性理解可以发现 $f(x)$ 是一个下凸壳。考虑 WQS 二分。二分斜率 $m$，求切点相当于最小化 $y$ 轴上的截距，即求出最小的 $f(x)-mx$。这个最小值的意义就是可以随意造光盘，且每造一张光盘可以赚 $m$ 元时的最小花费（显然它一定非负）。考虑用堆解决这个问题。维护一个小根堆，每次将 $a_i$ 插入到堆中...
LOJ3271 「JOISC 2020 Day1」建筑装饰 4
LOJ分析设 $dp_{i,0/1,0/1}$ 表示前 $i$ 位，第 $i$ 位选 A / B 时所有满足条件的方案中最多能有多少个 A / B。转移分四种情况（$a_{i-1}\leq a_i$、$a_{i-1}\leq b_i$、$b_{i-1}\leq a_i$、$b_{i-1}\leq b_i$）即可。考虑从后往前构造方案。设 $sa$ 表示已选的 A 的数量，$sb$ 表示已选的...
洛谷5289 [十二省联考2019]皮配
LuoguLOJ分析首先注意到学校选择导师和选择派系是等价的。考虑 $k=0$ 的情况。则此时城市选择阵营与学校选择派系独立，可以分开处理。设 $f_{i,j}$ 表示前 $i$ 个城市有 $j$ 个人在蓝阵营的方案数，$g_{i,j}$ 表示前 $i$ 所学校有 $j$ 个人在鸭派系的方案数。转移即为 0/1 背包。统计答案时枚举第二维乘起来累加即可。考虑 $k\neq 0$ 的情况。注意...
CF724E Goods transportation
CodeforcesLuogu分析容易想到一个网络流做法，即源点向每个点连容量为 $p_i$ 的边，每个点向汇点连容量为 $s_i$ 的边，每个点向编号比它大的点连容量为 $c$ 的边，然后求最大流即可。发现最大流不好求，而图比较特殊，可以考虑 DP 求最小割。设 $dp_{i,j}$ 表示前 $i$ 个点有 $j$ 个点和源点相连的最小割。转移这样考虑：如果 $i$ 与源点相连，则断掉连向...
CF568E Longest Increasing Subsequence
CodeforcesLuogu分析考虑普通 LIS 问题的解法，即设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，转移时二分即可。考虑沿用到这道题中。设 $f_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值，$g_i$ 表示长度为 $i$ 的 LIS 的结尾的最小值所在位置；再设 $l_i$ 表示以 $i$ 结尾的 LIS 长度，$p_i$ 表示以 $i$ 结尾的 LI...
CF940F Machine Learning
CodeforcesLuogu分析考虑询问的最大值为多少。假设为 $k$，则序列中至少要有 $1+2+\cdots+k-1=\frac{k(k-1)}{2}$ 个数。因此答案是 $\mathcal{O}(\sqrt{n})$ 级别的。因此可以带修莫队，只需要维护每个数的出现次数和每个出现次数的出现次数即可。移动时注意把 add 写在前面避免负下标问题。代码// ===============...