CF1450 题解
A把 $b$ 都提到最前面就好了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back...
A把 $b$ 都提到最前面就好了。#include <bits/stdc++.h> #define fi first #define se second #define db double #define U unsigned #define P std::pair<int,int> #define LL long long #define pb push_back...
题意要求构造大小为 $n$ 的排列，要求至少 $\lceil \frac{m}{2} \rceil$ 条限制：第 $i$ 条限制 $(a_i,b_i,c_i)$ 形如排列中 $b_i$ 的位置要在 $a_i$ 和 $c_i$ 之间。题解神仙题。这个题一般确定排列的方法都不能用了，我们考虑这个在两个数中间的限制：考虑用按照顺序每次将一个数放到前面或者后面的方式。因为保证有解，所以肯定能搞出来一...
A. 跳石头首先我们观察一下青蛙是怎么跳的：对于一个断点 $(i,i+1)$，如果有 $x$ 只青蛙往左跳，那么一定有 $x$ 只青蛙往右跳，所以 $a_i$ 一定是偶数。并且我们发现从 $a_i$ 到 $a_{i+1}$，变化的只可能是 $i+1$ 这一个青蛙，也就是有 $|a_i-a_{i+1}| \in \{0,2,-2\}$。我们考虑 $a_i$ 到 $a_{i+1}$ 的变化：如果...
A. 小星星考虑一个大家都会的暴力 dp：设 $f_{v,i,S}$ 表示确定好了 $v$ 的子树内的点映射到集合 $S$ 上，并且 $v$ 对应 $i$ 的方案数。合并子树的时候要保证 $S1$ 和 $S2$ 不交，然后根据图是否有边来判断。复杂度瓶颈显然在每次转移时的枚举子集。我们考虑我们这个第三维的作用是什么：是为了防止多个点映射到同一个点上。我们如果限定这个数的映射只能用 $S$ 然...
A考虑对串的反串建后缀树，答案就是叶子节点个数。注意到这时的叶子节点一定是一段前缀，如果一个前缀 $s[1\ldots i]$ 是叶子节点当且仅当它不属于任何一个点的 border 集合，所以问题变成了求每个前缀的 border 集合的并的大小，用 kmp 解决即可。这里发现一个结论：每个前缀的 border 集合的并的大小等于 $\max{fail_i}$。证明要考虑这个命题等价于叶子节点...