CF1270H Number of Components
Codeforces Luogu 分析 可以发现一个性质，即连通块一定是连续的一段。证明可以设 $i<k<j$，然后讨论各种情况，并证明无论如何 $k$ 与 $i,j$ 都连通。证起来有些复杂所以此处略去（ 那么我们可以枚举连通块的最右边的点 $p$，如果 $[1,p]$ 与 $[p+1,n]$ 间没有连边即 $\min_{1\leq i\leq p}a_\max_{p+1\le...
分类 题解 下的文章
- 首页
- 题解
CF671C Ultimate Weirdness of an Array
Codeforces Luogu 分析 考虑求出一个 $H_i$ 表示有多少个 $[l,r]$ 满足 $f(l,r)\leq i$，则答案为 考虑快速求 $nxt_i$。考虑从大到小枚举 $i$，在 $i$ 减小时考虑 $nxt$ 的变化。 假设满足 $i|a_j$ 的 $j$ 为 $x_1,x_2,\cdots,x_m$，则 $[l,r]$ 外至多有这些数中的一个。因此 $nxt_{x_...
LOJ575 「LibreOJ NOI Round #2」不等关系
LOJ 分析 假设 > 是没有限制的，那么整个序列被 < 划分为若干段。设这些段的长度为 $a_1,a_2,\cdots$，则方案数为 边界为 $dp_0=0$。将 $(-1)^{cnt_{i-1}}$ 提出后分治 NTT 即可。 代码 // =================================== // author: M_sea // website:...
洛谷5400 [CTS2019]随机立方体
Luogu LOJ 分析 为了方便，设 $n<m<l$，$V=nml$。 考虑容斥，求出至少有 $i$ 个极大数的方案数 $c_i$。 那么 $c_i$ 等于选出 $i$ 个极大数的方案数、$i$ 个极大数所在的平面的并填数的方案数、其它位置填数的方案数之积。 首先考虑求选出 $i$ 个数的方案数 $f_i$，不难得到 总时间复杂度 $\mathcal{O}(n)$。 代码 /...
LOJ6495 「雅礼集训 2018 Day1」树
LOJ 分析 设 $dp_{i,j}$ 表示 $1\sim i$ 构成的树高度为 $j$ 的方案数。 显然树上一定存在 $(1,2)$ 这条边，因此我们转移时讨论以 $2$ 为根的子树（记做 $A$）和整棵树其它部分（记做 $B$，显然它也是一棵树）的高度关系。 转移讨论一下整棵树最深的节点在哪里即可 边界为 $dp_{1,1}=dp_{1,2}=1$。 代码 偷懒把第一问打了个表 QAq...
LOJ2729 「JOISC 2016 Day 1」俄罗斯套娃
LOJ 分析 我们把每个套娃看做一个点 $(R_i,H_i)$，把套在一起的若干个套娃看做一条链，把每条链 $H$ 最大的那个套娃称作这条链的头。 这样子问题就变为，每个点可以向右上方某一个点连边，求最小链数。 先考虑只有一组询问的情况。 我们把所有物品按 $H$ 从小到大排序，然后依次加入。对于每个物品，显然选择能选择的最右的链头连上最优。于是我们只需要找到左边第一个链头即可。 考虑处理询...
洛谷3270 [JLOI2016]成绩比较
Luogu LOJ 分析 考虑容斥，求出至少 $i$ 个人被 D 神碾压的方案数 $f_i$。 首先钦定 $i$ 个人被 D 神碾压，然后对于每一科选出没有被 D 神碾压但是这一科分数比他低的 $n-r_i-i$ 个人，然后再枚举 D 神的分数并计算出其它人分数的方案数，即可求出 $f_i$，即 总时间复杂度为 $\mathcal{O}(n^2m)$。 代码 // ============...
CF1285F Classical?
Codeforces Luogu 分析 下文中的 $A$ 为 $\max_{i=1}^n\{a_i\}$。 考虑枚举答案的 $\gcd$，问题变为求满足 $\gcd(x,y)=g$ 的 $x,y$ 中 $x\times y$ 的最大值。 可以考虑贪心。我们先把所有满足为 $g$ 的倍数的数拿出来并从大到小排序，然后依次扫描，同时开一个栈来维护。对于每个数，我们需要判断栈中有没有与它互质的数，...
CF1284E New Year and Castle Construction
Codeforces Luogu 分析 考虑任意五个点对答案的贡献。显然有 如果五个点的凸包为五边形，则贡献为 $0$； 如果五个点的凸包为四边形，则贡献为 $1$； 如果五个点的凸包为三角形，则贡献为 $2$。 我们只需要求出五个点凸包为为 $x$ 边形的方案数 $s_x$，然后答案即为 $s_4+2s_3$。 不知道怎么想到可以把答案拆成 $5(s_5+s_4+s_3)-(5s_5+...
CF1286D LCC
Codeforces Luogu 分析 容易发现最早碰撞的一定是相邻的两个球。 我们钦定某一对球是最先撞上的以及它们的运动方向，然后考虑 DP。设 $dp_{i,0/1}$ 表示前 $i$ 个球，当前的球往左/往右，且保证最早撞上的是钦定的那一对的概率。转移讨论一下几种情况即可。 这个转移显然可以写成若干个 $2\times 2$ 的矩阵相乘。如果我们把所有方案按时间从小到大排序再枚举，则每...