CF1276C Beautiful Rectangle
CodeforcesLuogu分析考虑枚举短边的长度 $r$。设数 $i$ 有 $cnt_i$ 个，那么我们至多能填个数到矩形中。因此当短边长度为 $r$ 时长边至多为 $\left\lfloor\frac{s_r}{r}\right\rfloor$。因为短边长度不超过 $\sqrt{n}$，因此我们可以在 $\mathcal{O}(n\sqrt{n})$ 的时间内求出答案。现在我们仅需要构...
分类 题解 下的文章
- 首页
- 题解
CF915F Imbalance Value of a Tree
CodeforcesLuogu分析容易发现，我们仅需要计算出每条链的最大值之和和最小值之和即可。而最小值之和可以通过把所有权值取相反数得到，因此我们只考虑求每条链的最大值之和。容易发现，这个东西等价于求每个点是多少条路径上的最大值。我们将所有点按权值从小到大排序并依次加入。加入点 $u$ 时，假设 $v$ 和 $u$ 相连且 $v$ 已被加入（即 $w_v\leq w_u$），则 $u$ 会...
洛谷4199 万径人踪灭
LuoguBZOJ分析下文中默认字符串的下标从 $0$ 开始。可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。后面的就是 manacher 板子，考虑怎么求前面的。设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量，则有后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1$，累加起来即可...
CF1254C Point Ordering
CodeforcesLuogu分析首先用 $A_1,A_2$ 两个点将凸包分为两部分。我们容易用 $n-2$ 次询问二求出其它的 $n-2$ 个点在左侧还是右侧。接着用 $n-2$ 次询问一，求出其他每个点与 $A_1,A_2$ 构成的三角形的面积。这时我们实际上已经得知了每个点到直线 $A_1A_2$ 的距离。我们把两侧的点分开处理。对于某一侧的点（假设已按逆时针排列），显然它们到 $A_...
洛谷5631 最小mex生成树
Luogu分析枚举一个答案 $ans$，那么我们相当于要求在删去边权为 $ans$ 的边后图是否存在一棵生成树，即图是否连通。显然可以考虑线段树分治。具体的，建一棵以边权为下标的线段树，对于每条边权为 $w$ 的边将其放到 $[0,w-1]$ 和 $[w+1,10^5]$ 上。然后在线段树上遍历，遍历到一个节点就将它上面挂着的边连上，这样子到叶结点时就连上了所有不包含该边权的边，判断图是否连...
CF1228E Another Filling the Grid
CodeforcesLuogu分析显然可以考虑容斥。枚举 $i$ 行 $j$ 列的最小值不为 $1$，可以得到答案为代码// =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #in...
CF1245E Hyakugoku and Ladders
CodeforcesLuogu完了我期望都不会算了 /dk分析先把走过的点依次编号 $100\cdots 1$，起点为 $100$，终点为 $1$。再设 $to_i$ 表示 $i$ 爬梯子能到的点。考虑 DP。设 $dp_i$ 表示 $i$ 到 $1$ 的期望步数。当 $2\leq i\leq 6$时，状态转移方程为答案为 $dp_{100}$。代码// ==================...