洛谷4062 [Code+#1]Yazid 的新生舞会
Luogu LOJ 分析 显然每个数作为众数的情况是相互独立的，因此我们考虑枚举众数 $k$，然后计算有多少个区间中 $k$ 的出现次数超过一半。 不妨把等于 $k$ 的数看做 $1$，不等于 $k$ 的数看做 $-1$，那么我们相当于要求有多少个区间的和大于 $0$。这个东西等价于前缀和的逆序对数。 但是直接做的话当 $A_i$ 的数量比较多时显然会 TLE，所以我们需要一些优化。 考虑到...
分类 题解 下的文章
- 首页
- 题解
CF1276C Beautiful Rectangle
Codeforces Luogu 分析 考虑枚举短边的长度 $r$。设数 $i$ 有 $cnt_i$ 个，那么我们至多能填 个数到矩形中。因此当短边长度为 $r$ 时长边至多为 $\left\lfloor\frac{s_r}{r}\right\rfloor$。 因为短边长度不超过 $\sqrt{n}$，因此我们可以在 $\mathcal{O}(n\sqrt{n})$ 的时间内求出答案。 现...
洛谷4199 万径人踪灭
Luogu BZOJ 分析 下文中默认字符串的下标从 $0$ 开始。 可以发现答案等于「位置和字符都关于某条对称轴对称的子序列」的数量减去「回文子串」的数量。 后面的就是 manacher 板子，考虑怎么求前面的。 设 $c_i$ 表示「位置和字符都关于对称轴 $i$ 对称的子序列」的数量，则有 后就可以用 FFT 求出 $c_i$ 了。每条对称轴 $i$ 的贡献则为 $2^{c_i}-1...
CF1254C Point Ordering
Codeforces Luogu 分析 首先用 $A_1,A_2$ 两个点将凸包分为两部分。我们容易用 $n-2$ 次询问二求出其它的 $n-2$ 个点在左侧还是右侧。 接着用 $n-2$ 次询问一，求出其他每个点与 $A_1,A_2$ 构成的三角形的面积。这时我们实际上已经得知了每个点到直线 $A_1A_2$ 的距离。 我们把两侧的点分开处理。对于某一侧的点（假设已按逆时针排列），显然它们...
LOJ6704 健身计划
LOJ 分析 设 $f_i$ 表示 $n=i$ 时的答案，容易得到 直接矩阵快速幂即可。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // =================================== #include <a...
51nod1597 有限背包计数问题
51nod 分析 考虑根号分治。令 $B=\left\lceil\sqrt{n}\right\rceil$，则 $[1,B]$ 内的物品能取完，$[B+1,n]$ 内的物品无法取完。 先考虑 $[1,B]$ 内物品。设 $f_{i,j}$ 表示前 $i$ 种物品和为 $j$ 的方案数，容易写出转移 注意到 $(i,j)$ 的转移点 $(i,k)$ 满足 $k\leq j\land j\eq...
AGC001E BBQ Hard
AtCoder Luogu 分析 观察题目中给的这个式子 等价于从 $(0,0)$ 走到 $(a_i+a_j,b_i+b_j)$ 的方案数，等价于从 $(-a_i,-b_i)$ 走到 $(a_j,b_j)$ 的方案数。 然后题目中要求的是 $\sum$，因此我们考虑求出以每个 $(-a_i,-b_i)$ 为起点走到每个 $(a_j,b_j)$ 的方案数之和。 注意到 $a_i,b_i$ 的...