CF1204E Natasha, Sasha and the Prefix Sums

首先，看到这个 $\max$ 可以想到转化成求和最大值大于等于 $i$ 的方案个数。

按照这种 prefix sum 的一般想法，会发现这个东西就是画成折线后和 $y=i$ 的交点。然后枚举 $i$ 分情况讨论，由于结束点显然在 $(n+m,n-m)$ 那么：

• 如果 $n-m \ge i$ ，显然必然有交点。方案数为 $\binom {n+m} n$ 。
• 否则，我们考虑把 $(0,0)$ 翻折到 $(0,2i)$ ，那么现在折线就肯定有交点了，并且会发现翻着后的折线一定有一条唯一的原来的有交点的折线与之对应。因为如果原折线有交点，那么一定可以从第一个交点处把之前的位置翻上去得到一种唯一的新折线。不难发现这是一一对应的。方案数为 $\binom{n+m}{n-i}$ 。

一道精妙的题，没见过这个套路可能翻车。

CF698C LRU

首先吐槽一下，luogu 翻译是有锅的，希望管理改一下。具体请看这里，按照原题意理解的话这个 $dp$ 感觉就会不是很对劲。

考虑倒着看这个序列，会发现只有最后 $k$ 种不同数出现的位置是有用的。因为每得到一个数，就会直接把它放到队尾，也就是说无论前面的情况如何，一旦经过了最后 $k$ 种数，那么最后队列仍然会是这 $k$ 种数。

也就是说，当我们确定了这 $k$ 个数后，前面的巨量操作就对后面没有了影响。由于操作的次数非常大，我们可以认为一定有足够的操作填满这个队列。所以可以直接当作是这样的题意：每次选择一个数，直到选择齐了 $k$ 个数，求选择结束后每个数留在队列的概率。

这个问题就非常简单了，直接 $dp[u][S]$ 表示进行一些操作后正好凑齐了 $S$ 这个集合的概率即可，然后直接把已经在集合的数忽视掉即可转移。

复杂度 $O(n2^n)$ 。

CF747C Igor and Interesting Numbers

首先考虑求出最后的长度，具体来说从小到大枚举长度，然后求出没用前导零的串的个数。

然后从大到小枚举每一位的的字符，然后尝试给这个字符的限制减少 $1$ ，求一次可以有前导零的方案数，如果方案数不到 $n$ 就选择下一个字符，否则就确定了这一位，继续做下一位即可。

复杂度 $O(16t\text{len}^2)$ 左右，这种题看起来复杂度就很松。

CF1430G Yet Another DAG Problem

场上差点写完的题。

首先可以发现，分配的权值对于每个连通块来说值域一定不大，最优的分配方案肯定是每个连通块被分配到 $1\sim i$ 的连续的权值。

直接统计答案不方便，我们考虑进行一个差分，枚举一下最大值 $s$ ，按照最大值从低转移到高。具体来说，设 $dp[S]$ 表示 $S$ 这个集合的一种最优的分配权值的方案，使得如果外面的点的权值正好是这个集合的最大权值 $+1$ 时的答案。会发现转移就是枚举一个子集作为最大值，枚举 $T \sube S$ ，然后由 $dp[S\setminus T] + re[S]$ 转移过来，前提是 $T$ 这个集合内部没有边，其中 $re[S]$ 表示 $S$ 外面的点连向 $S$ 的边权总和。转移本质上就是在给最大权值减少 $1$ 做子问题，再加上最大权值的贡献。

不难发现 $re$ 以及集合的可行性都可以 $n^22^n$ 预处理，做这个 $dp$ 复杂度是 $3^n$ ，于是这题就 $O(3^n+n^22^n)$ 解决了问题。

CF599E Sandy and Nuts

大概是写着非常难受的一个题。

第一想法设 $dp[u][S]$ 表示连了整个 $S$ 集合，根为 $u$ 的方案数量。然后转移就是枚举一个子集作为一棵子树。

然后考虑细节。首先我们需要考虑去掉顺序。可以每次钦定选择的子树必须包含 $S$ 的 lowbit 位置。这样对于一种分配子树的方案的转移方式就唯一了。

然后考虑 $a,b,c$ 的限制。 首先，如果一个状态 $dp[u][S]$ 有值，那么对于 $a,b \in S$ 我们钦定它的 $\text{LCA}$ 必须为 $u$ 。那么现在枚举子树 $T \sube S$ 转移的时候，只需要考虑的情况就是 $a \in T,b \in S\setminus T$ 并且算一下是否有 $c = u$ 了。如果不满足，那么就不能有这个转移。

然后考虑边限制。首先我们钦定如果 $dp[u][S]$ 有值，那么不存在边 $a,b$ 使得 $a \in S \setminus \{u\} , b \notin S \setminus \{u\}$ 。显然后面这个满足了就一定不可能连 $a,b$ 这条边出来。于是转移就是枚举子树 $T \sube S$ ，如果子树内存在点 $v$ 与 $u$ 本身就有边了，那么就只能钦定 $v$ 为子树的根。如果存在两个及以上的点，那么就转移不了。在转移完 $dp[u][S]$ 后，还需要看看是否存在开始说的那种情况，如果存在就直接毙掉这个状态。

还需要注意特判 $\text{LCA}$ 处 $a=b$ 的情况。

复杂度 $O(nq3^n)$ 其实跑得非常快。

CF704C Black Widow

一个非常没有意思的题。

判掉一个数单独出现两次的情况。然后按照 $u,v,k$ 建图，然后就能建出很多环和链。

然后对环和链分别进行 $dp$ 即可。

需要注意细节，但是懒得多说了，具体看代码吧。。

CF1408G Clusterization Counting

挺有意思的题，感觉思路很自然，最后代码也很好看。

首先题目中的这个条件，不难发现等价于把 $n$ 个点划分成若干个集合，然后每个集合内部的边权都小于集合向外的边权。因此可以发现这些集合之间是独立的，因此我们称一个集合合法当且仅当这个集合内部的边权都小于这个集合向外的边权。

由于这个条件的特殊性，如果考虑从小到大加入边，那么一个集合合法当且仅当在某次加边后，这个集合整体形成了一个完全图。

然后可以发现对于两个集合 $S,T$ ，如果都合法，那么要么有 $S \cap T = \varnothing$ 要么有 $S \sube T$ 或 $T \sube S$ 。因此可以发现，合法集合其实构成了一棵树的结构，而叶子就是单个的点（单个的点显然合法），根就是全集（全集显然也合法） 。而现在要做的事情就是求一种在树上选择 $k$ 点的方案，使得不存在一个叶子到根路径上没有点被选，且不存在两个被选择的点之间成祖先，子孙关系。这个可以一个树形背包解决。而建树的过程可以用并查集维护连通块内的点的个数，边的个数，以及连通块当前的子树的根有哪些。

复杂度 $O(n^2)$ 。

CF1342F Make It Ascending

一种非常简单的思路是考虑记录状态 $dp[i][j][s_1][s_2]$ 表示当前考虑到第 $i$ 个数，它对应回原数列位置在 $j$ ，已经被用掉的集合为 $s_1$ ，最后一次被用掉的集合是 $s_2$ 。状态的转移就是枚举下一个数的构成状态，于是复杂度 $n^2 4^n$ ，不是很行。

仔细想一想会发现这样设状态是很浪费的，于是可以把 $s_2$ 丢到状态的值里面，类似 LIS $O(n\log n)$ 的做法，就变成了 $dp[i][j][s]$ 表示当前考虑到第 $i$ 个数，它实际上在 $j$ ，用掉了 $s$ 这个集合，这种情况下最小的最后一个数对应的状态是啥。于是转移也是枚举下一个状态，同时需要记录一个 $dp$ 在第二维上的前缀最小值，转移就是

$$dp[i][j][s] = \min_{t \in s , \exist k < j , S[t] > dp[i-1][k][s\setminus t]} \{ S[t] \}$$

由于这里的 $dp$ 本质上就是一个前驱，所以输出答案甚至没有必要记录前驱。

复杂度 $O(3^nn^2)$ 注意枚举顺序，很容易被卡常搞 T 。

CF1326F2 Wise Men

牛逼题