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