A 操作 2 会让奇数-1，偶数+1。 不难发现只有当 $a$ 为奇数时，我们能让 $a$ 减小，且只能减少 $1$。 如果 $a > b$，那么当且仅当 $a \oplus 1 = b$ 有解。 下面讨论 $a < b$ 的情况。 如果 $x \le y$，那么我们全部使用操作 $1$ 即可。 否则我们肯定是两种操作交替使用。 关于第…

link $\texttt{Solution}$ 较为复杂的计数直接考虑 DP。 区间相关的题目排了序才能做，就是按照左端点还是右端点排的问题。 我们考虑当前区间 $i$，如果要选它，那么我们需要保证与其异色的区间右端点小于 $l_i$。 这个就是后效性的源头，把它加入状态即可。 设 $f_k,0/1$ 为选出的最后一个区间右端点为 $k$，颜色为…

因为时间紧迫所以忽略所有时间复杂度的计算。 luogu2657 [SCOI2009] windy 数 板子。 #include<bits/stdc++.h> using namespace std; #define int long long #define uint unsigned long long #define PII pai…

先放题，有时间再整理。 其实也就那回事，理解了思想之后就没啥特殊性了。 luogu6647 [CCC2019] Tourism 不难发现 $t =\lceil \frac{n}{k} \rceil$，然而并没有什么用，我们只要在转移时对取值区间进行限制即可。 具体地，第 $i$ 天的取值左端点是 $L_i = \max(0,i-k)$，右端点是 $…

区间形态的扩展 luogu3205 [HNOI2010] 合唱队 队列的形成方式是不断往左或往右扩展。 考虑区间 DP。发现对于一个区间 $[i,j]$，最后一个元素的来源会对转移产生影响，所以设 $f(i,j,0/1)$ 为考虑区间 $[i,j]$，其中最后一个元素是从左边还是右边加入的方案数。 转移很简单$$f(i,j,0) = [a_i &l…

[ARC101E] Ribbons on Tree 对于以 $x$ 为根的子树，如果 $(x,fa_x)$ 的边没有被覆盖，那么说明子树内没有任何一个点与子树外的点匹配。 把这些没有被覆盖的边看作特殊边，那么整棵树就被若干特殊边划分成了若干连通块。我们要求的是不含任何特殊边的匹配方案。 考虑容斥。钦定一个边集 $S$，表示 $S$ 内的边一定是特殊…

聊聊状态压缩。 顾名思义，就是把一个状态压成一个整数，从而使得问题的所有状态可以度量。 一般都是用二进制状态压缩来表示子集与全集的关系，对应着二进制每一位都是 $0$ 或 $1$。更高的进制能表示更多的信息，但状态的数量也会随之增加，并且实现的时候要自己手写位运算，较为复杂，本文不会涉及。 信息的表示 luogu7076 [CSP-S2020] 动…

专门放一些不大可能会考的计数题，长期更新。 大约是输入的只有问题规模，输出的只有相应方案数。 luogu6561 [SBCOI2020] 人 两两不相邻这个条件不是很容易搞。 考虑把 $[1,2m]$ 分成 $m$ 个数对，形如 $(\text{odd},\text{even})$，其中 $\text{odd} +1 =\text{even} $ …

计数杂题。 CF840C On the Bench 先进行一些基本的观察。 $\texttt{Observation}$ ${a_i}$ 中乘积为完全平方数的数集，一定是相对封闭的。因此我们可以将 ${a_i}$ 划分成若干个集合，满足其中两两乘积为完全平方数。 $\texttt{proof}$ 考虑和 $a_i$ 相乘为完全平方数的数集 ${a_…

Trie luogu2922 [USACO08DEC]Secret Message G 给定两个字符串序列 $a$ 与 $b$，对于 $b$ 中每个字符串 $t$，求 $a$ 中有多少个字符串 $s$，满足以下两个条件之一 $s$ 是 $t$ 的前缀。 $t$ 是 $s$ 的前缀。 两个字符串序列中所有字符串长度之和不超过 $500000$。 把 …