ARC098F Donation
AtCoder Luogu 分析 设 $c_i=\max\left\{0,a_i-b_i\right\}$，则相当于要求任意在 $u$ 点的时刻手中都有至少 $c_u$ 円。 然后可以发现两个结论： 每个点只会在最后一次访问时被捐赠。 $c_i$ 大的会优先捐赠。 那么我们大概是这样捐赠的：首先选一个点 $u$，假设删掉 $u$ 后形成了 $tot$ 个连通块，则先捐赠掉 $tot-1$...
分类 题解 下的文章
- 首页
- 题解
CF1067D Computer Game
Codeforces Luogu 分析 显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏，然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。 考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益，枚举每个游戏可以得到转移 于是只要快速找到决策点改变的位置即可...
CF1139D Steps to One
Codeforces Luogu 分析 直接算即可。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h>...
CF573E Bear and Bowling
Codeforces Luogu 分析 考虑一个贪心，即每次取贡献最大的一个，这里的贡献是 $k_i\times a_i+b_i$，其中 $k_i$ 表示前面选了的数量，$b_i$ 表示后面选了的 $a_i$ 的和。 那么我们相当于要维护一些直线，支持区间斜率加、截距加和求全局最大值。 考虑分块，对每块维护一个上凸壳，散块修改后重构、整块打标记即可。注意要把当前选出来的数删掉。 代码 // ...
洛谷4698 [CEOI2011]Hotel
Luogu LOJ 分析 先考虑没有 $o$ 的限制怎么做。可以想到贪心，把房间按容量小到大排序、订单按人数从小到大排序，然后依次枚举每个房间，选择能容纳的租金最高的那个订单。正确性比较显然。 现在加入这个限制，可以考虑 WQS 二分。设 $f(x)$ 表示接受 $x$ 个订单的最大收入，感性理解可以知道 $f(x)$ 是凸的。二分斜率 $m$，则我们要求最大的 $b=f(x)-mx$，而这...
洛谷5996 [PA2014]Muzeum
Luogu 分析 不难看出一个最大权闭合子图的模型，然而直接求最大流显然过不了，于是可以考虑模拟最大流。 首先把这个坐标系变换一下。如果警卫 $a$ 能看到手办 $b$，则应有 于是可以把 $(h\times x+w\times y,h\times x-w\times y)$ 作为每个点的坐标，这样子警卫 $a$ 能看到手办 $b$ 当且仅当 $x_b\leq x_a,y_a\leq y_...
CF1093F Vasya and Array
Codeforces Luogu 分析 设 $dp_{i,j}$ 表示前 $i$ 个数，第 $i$ 位填 $j$ 的方案数，$s_i$ 表示 $\sum_{j=1}^k dp_{i,j}$，$len_{i,j}$ 表示第 $i$ 位往前最多有多少位为 $j$。 转移时讨论一下。当 $len_{i,j}<l$ 时 $dp_{i,j}=s_{i-1}$；否则要减去超长的那一部分，即为 $d...
洛谷6280 [USACO20OPEN]Exercise G
Luogu 分析 显然一个置换的步数就是它所有环长的 $\operatorname{lcm}$。于是问题变为求有多少个数 $n$ 的某个拆分中所有数的 $\operatorname{lcm}$。 考虑 DP。设 $dp_{i,j}$ 表示 $i$ 拆成若干个最大质因子 $\leq p_j$ 且不为 $1$ 的数时的答案，不难得到转移 答案即为 $1+\sum_{i=1}^n dp_{n,|...
CF700D Huffman Coding on Segment
Codeforces Luogu 分析 考虑莫队，维护区间内每个数的出现次数，然后询问时建一棵 Huffman 树即可。然而暴力建树是 $\mathcal{O}(n)$ 的，显然过不了。 考虑根号分治，并维护出现次数为 $i$ 的数的个数，这样子对于出现次数 $\leq B$ 的数，可以直接 $\mathcal{O}(B)$ 扫一遍合并；对于出现次数 $>B$ 的数，显然只有 $\fr...
POI2012 简要题解
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...