主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
计数笔记
最后更新于 2025-08-27 19:18:31
作者
The_foolishest_OIer
分类
个人记录
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
注：带 * 代表不会的，带 / 对了一半，^ 表示代码挂了。 ## 7.27 ### CF1696E Placing Jinas * ::::info[题解] 把每一列直接平推肯定是最优的。 对于第 $x$ 行第 $y$ 列的格子要操作的次数 $f_{x,y}=f_{x-1,y}+f_{x,y-1}$，初始化 $f_{0,0}=0$。 然后发现 $f$ 实际上是一个杨辉三角，有 $f_{x,y}=\begin{pmatrix} x+y-2 \\ x-1 \\ \end{pmatrix}$，直接杨辉三角前 $a_i$ 项求和。 又有 $\sum_{i=0}^b f_{x,i}=f_{x+1,b-1}$，所以 $ans=\sum_{i=0}^n \begin{pmatrix} i+a_i \\ i+1 \\ \end{pmatrix}$。 :::: ### CF1359E Modular Stability * ::::info[题解] $n<k$ 显然方案数为 $0$。 由于对于任意的 $x$，满足 $(x \bmod a) \bmod b = (x \bmod b) \bmod a$，不妨设 $x=pa+r$，可以得出当且仅当 $a \mid b$ 或 $b \mid a$ 时对于任意 $x$ 都成立。 于是记 $s = \min \limits_{i=1}^n a_i$，则当对于任意 $i \text{ } (1 \le i \le n)$，$s \mid a_i$ 就是成立的。 枚举 $s$，组合数做掉即可。 :::: ## 7.28 ### CF895C Square Subsets * ::::info[题解] 一个数 $x$ 可以写成 $k^2m$ 的形式，其中 $m$ 是数 $x$ 的特征值，显然我们只需要考虑 $m$。 由于 $a_i \le 70$，开一个桶记录特征值为 $y$ 的数的个数为 $t_y$，考虑状压 DP。 记 $dp_{i,j}$ 为第 $i$ 个数，状态为 $j$ 的方案数，可以发现是否为完全平方数只与每个质因子的就行有关。 二项式定理优化即可，答案为 $dp_{n,0}$。 :::: ### CF1454E Number of Simple Paths ^ ::::info[题解] 图是一个基环树，所有任意两个点对 $(u,v)$ 的路径条数不是 $1$ 就是 $2$。 拓扑排序找环。 :::: ### CF1366E Two Arrays ::::info[题解] 考虑动态规划，记 $f_{i,j}$ 为以 $i$ 为结尾，第 $j$ 个段的方案数。 有 $f_{i,j}=\sum \limits_{1 \le k < i \land \min \limits_{p=k}^i = b_j} f_{k,j-1}$，显然复杂度太大。 由于 $b$ 单调递增，我们可以做出第 $i$ 个数最多可以被划分在第 $c_i$ 个子段，即 $b_{c_i} \le a_i$。 再从后向前推平 $c$，有 $c_i = \min(c_i,\min \limits_{j=i+1}^n c_j)$，记在所有的 $c_i=j$ 中最右边的 $a_i=b_j$ 的 $i$ 距离最左端的 $i$ 的 $c_i=j$ 的距离记为 $d_i$。 如果 $d_i$ 不存在，$0$ 种方案。 否则乘法原理，$ans = \prod \limits_{i=1}^m (d_i+1)$。 :::: ### CF689E Mike and Geometry Problem * ::::info[题解] 转化问题，求每个点的贡献即可，离散化做掉。 :::: ## 7.29 ### CF1622D Shuffle * ::::info[题解] 注意到数据范围是 $n \le 5 \times 10^3$。 记 $s_i=\sum \limits_{j=1}^i a_j$，考虑枚举最左端改变的位置 $i$ 和最右端改变的位置 $j$，满足 $s_j-s_{i-1}\le k$。 由于 $i,j$ 强制改变，组合数做一下即可。 :::: ### CF1426F Number of Subsequences / ::::info[题解] 我们看对于每一个字符 $\texttt{b}$ 的贡献是多少，设左边有 $a$ 个确定的 $\texttt{a}$，$b$ 个 $\texttt{?}$，右边有确定的 $c$ 个 $\texttt{c}$，$d$ 个 $\texttt{?}$。 当左边的 $\texttt{?}$ 是 $\texttt{A}$，右边的 $\texttt{?}$ 是 $\texttt{C}$ 时会产生贡献。 共有四种方案产生贡献： - $\texttt{a}$ 与 $\texttt{c}$，共 $3^{b+d}$ 种，每种贡献为 $ac$。 - $\texttt{a}$ 与 $\texttt{?}$，共 $3^{b+d-1}$ 种，每种贡献为 $ad$。 - $\texttt{?}$ 与 $\texttt{c}$，共 $3^{b+d-1}$ 种，每种贡献为 $bc$。 - $\texttt{?}$ 与 $\texttt{?}$，共 $3^{b+d-2}$ 种，每种贡献为 $bd$。 相加即可。 :::: ### CF552D Vanya and Triangles ^ ::::info[题解] 正难则反，斜率弄一下就行。 :::: ## 7.30 ### CF1749D Counting Arrays ::::info[题解] - 长度为 $1$ 的序列肯定是合法的。 - 对于一个序列 $a$，一直选 $1$ 肯定可以全部删除，因为 $\gcd(x,1)=1$。 - 若对于一个数 $a_i$，满足存在一个 $j \in [2,i]$，$\gcd(a_i,j)=1$，那么这个序列就是不合法的。 - 由上一条可得，记 $S$ 为所有 $\le i$ 的质数之乘积，那么 $a_i=kS \text{ } (k \in \text{N}^*)$。 乘法原理求解即可。 :::: ### CF1606E Arena * ::::info[题解] 考虑 dp。 设 $f_{i,j}$ 表示当前还剩 $i$ 个人，最大血量为 $j$ 的方案数。 若 $i-1 \ge j$，则所有方案都是可行的，$f_{i,j}=j^i-(j-1)^i$。 否则本轮过后场上还有人存活，枚举存活人数 $k$，又得出最大血量为 $j-i+1$，没有存活的显然可以取 $[1,i-1]$ 中的任意整数，有 $f_{i,j}=\sum \limits_{k=2}^i \begin{pmatrix} i \\ k \end{pmatrix} f_{k,j-i+1} (i-1)^{i-k}$。 :::: ## 7.31 ### CF893E Counting Arrays * ::::info[题解] 对于每个质因子做一遍插板法即可。 :::: ### CF2037G Natlan Exploring ::::info[题解] 考虑 dp，记 $f_i$ 为跳到 $i$ 的方案数。 $O(n^2)$ 做法是显然的，有 $f_1=1$，$f_i=\sum \limits_{j<i\land \gcd(a_i,a_j) \ne 1} f_j$。 发现仅当有一个质因子相同时可以转移，又由于一个数的质因子个数很少，可以直接大力容斥。 时间复杂度：$O(n(\sqrt W +2^V V))$，$W$ 是值域，$V$ 是最多的质因子个数。 :::: ### CF711D Directed Roads ::::info[题解] 找环，记这个连通块的点数为 $n$，环上点数为 $m$，可以得出环上边数量为 $m$，并且只有两种情况会出现环。 所以这个连通块的答案就是 $2^{n-m} (2^m-2)$，乘法原理即可。 :::: ## 8.1 ### CF128C Games with Rectangle / ::::info[题解] $O(n^5)$ 的暴力 dp 比较显然，考虑 $O(n^3)$ 做法。 注意到矩形位置没有影响，记 $f_{i,j}$ 为用 $i$ 步形成 $j$ 行的方案数，转移与 $O(n^5)$ 类似。 :::: ### CF156C Cipher ^ ::::info[题解] 简单 dp，可以发现如果两个字符串的 ASCII 码之和相同，那么是可以互相转化的，记 $f_{i,j}$ 为前 $i$ 为总和为 $j$ 的方案数，显然有 $f_{i,j} = \sum \limits_{k=1}^{26} f_{i-1,j-k}$，我们令字母 $\texttt{a}$ 的价值为 $1$，字母 $\texttt{b}$ 的价值为 $2$，以此类推。 :::: ## 8.2 ### CF1906J Count BFS Graph * ::::info[题解] 考虑 dp，记 $f_{i,j}$ 为遍历到 $i$，前 $j$ 个点入队的方案数，记 $nxt_i$ 为使 $[i,j]$ 单调递增的最大的 $j$。 显然有 $f_{i+1,k}\gets \sum \limits_{k=j}^{nxt_{j+1}} 2^{j-i-1}f_{i,j}$，可以用前缀和优化到 $O(n^2)$。 :::: ### CF489F Special Matrices ^ ::::info[题解] 考虑 dp，记 $f_{i,j,k}$ 表示第 $i$ 行有 $j$ 个和为 $1$ 的列，$k$ 个和为 $2$ 的列。 初始化显然，剩下的分类讨论： - 两个 $1$ 都贡献到和为 $0$ 的列，$f_{i,j,k}=f_{i-1,j-2,k} \begin{pmatrix} n-j-k+2 \\ 2 \\ \end{pmatrix}$。 - 和为 $1$ 和和为 $0$ 的各分一个，$f_{i,j,k} = f_{i-1,j,k-1} (n-j-k+1)j$。 - 两个 $1$ 都贡献到和为 $0$ 的列，$f_{i,j,k}=f_{i-1,j-2,k+2}\begin{pmatrix} j+2 \\ 2 \\ \end{pmatrix}$。 滚动数组优化一维，但是 TLE on 21。 发现 $j$ 的转移时奇偶性不变，所以循环时每次加 $2$，$O(n^3)$ 可以通过。 :::: ## 8.3 ### CF1788D Moving Dots * ::::info[题解] 发现如果一堆点汇聚到一个点，那么这些点的运动轨迹一定是形如 $[\rarr,\rarr,…,\rarr,\larr,…,\larr,\larr]$，考虑枚举最右边的右箭头位置 $i$ 和最左边的左箭头位置 $j$，一对 $(i,j)$ 可以产生贡献当且仅当： - $i < j$ 且区间 $[i+1,j-1]$ 没有任何数被选中。 - 满足形如上述运动的方式。 方案数显然是 $O(2^s)$ 的，$s$ 是可选点数，双指针做掉。 :::: ## 8.4 ### CF479E Riding in a Lift ::::info[题解] 考虑 dp，记 $f_{i,j}$ 为第 $i$ 步走到 $j$ 的方案数，朴素转移是 $O(n^2k)$ 的，前缀和优化到 $O(nk)$ 即可。 :::: ## 8.6 ### CF1268B Domino for Young * ::::info[题解] 考虑黑白染色，最终取所占格子少的即可。 :::: ## 8.23 ### CF997B Roman Digits * ::::info[题解] 打表可以轻松解决。 首先可知，在 $\{1,5,10,50\}$ 中取 $n$ 个组成不同数的方案数和在 $\{0,4,9,49\}$ 中取 $n$ 个组成不同数的方案数是相同的。 然后发现 $9 \times 4 = 4 \times 9 + 5 \times 0$，为了避免重复，我们取的 $4$ 的个数不能超过 $8$ 个。 又发现 $1 \times 4 + 5 \times 9 = 1 \times 49 + 5 \times 0$，所以只要取了 $4$，取 $9$ 的个数就不能超过 $4$ 个。如果没有取 $4$，那么取 $9$ 的个数就不能超过 $48$ 个。 再发现 $8 \times 4 + 1 \times 49 = 9 \times 9$，也就是说，当不取 $4$ 的时候，取 $9$ 的个数不能超过 $8$ 个。 然后就比较显然了，枚举 $4$ 和 $9$ 的个数分别为 $i,j$，剩下的全都选 $0$ 或 $49$，方案数为 $n-i-j+1$。 ::::
正在渲染内容...
点赞
0
收藏
0
