简要记录补的abc的思路，正式参加的就不记了。

不排除我咕咕的情况。

题号靠前，没有记录，要么是模拟，要么是开始决定补题前做了的。

代码实现都在账号 Livinfly 中，可在AtCoder所有提交中查看。

abc042

• b，sort。

• c，从小到大枚举 i >= n，判断有没有不喜欢的数字。

  • 贪心的去选应该不太成立，后面可能比所有可用的都大。

• d，前n-a+b-1有i步向下走，剩余的步数，有n-1-i步向下走。

  • $ans = \sum_{0}^{n-a-1}C(n-a+b-1, i)*C(n+m-2-(n-a+b-1), n-1-i)$
  • 求阶乘记得加LL。

abc043

• a，模拟/等差数列的和。
• b，模拟。
• c，枚举最后变成的值，取花费最小的。

• d，枚举unbalanced的字母，然后枚举找到长度为3的区间内有两个以上这个字母的地方，特判下n = 2的情况。

  • 因为长度为3的区间不多于两个，那前面的就对后面更长的没有贡献，也就不会对unbalanced有改变。

abc283

• e，DP，第i行的操作只会影响i-1和i+1的状态，不妨从上到下遍历，用dp[i, j, k]，表示第i行，行合法，且i-1行变换为j次，第i行变换k次的最小次数。因为状态的转移之和上下两个有关，可以状态压缩。
• f，分类讨论，讨论$i$和$j$的关系，$p_i$和$p_j$的关系，从左到右、从右到左，都分别维护两个树状数组。
• g，线性基，求第k大子集异或和模板题。

abc284

• g，首先是比较明显的内向基环树森林，然后后面需要推式子。（这一块我太弱了qnq，感觉就是先确定一些值，然后后面看看能不能不用这些值，必须要用的值枚举出来）

  • 容易发现的是n个作为$b_1$的结果一定是一样的，所以，我们只需考虑单个的情况。不妨考虑$b_1 = 1$，结束的方式一定是沿着链到环上，循环。那么我们给定一个链+环的长度k，以为1一定在链上，剩下链+环还有k-1，我们剩下n-1个不同的数，排k-1个；由于不在链+环上的n-k个数，我们不关心它是否不同，所以可以随便取；最后，1可能在链的各个位置，用等差数列求和公式可以得出之和链长有关的结果。
  • 最后得，$ans = A_{n-1}^{k-1} \cdot n^{n-k} \cdot \frac{k(k-1)}{2}$。

abc285

• f，不难发现一个区间符合递增且在中间大小的出现次数。26个树状数组维护各个字符的区间和，复杂度log，然

abc286

• d，多重背包，bitset + 二进制会很舒适。
• e，floyd，转移的时候，加一维比较即可，比较那边的条件有点长，看jls貌似转成pair来写可以舒服很多。
• f，给出的图是内向基环树森林。若有环，那么就可以知道n对环的长度取模的余数，容易想到构造中国剩余定理，手玩出符合的取模值，贴板子。
• g，若全是在S中必走且只能走一次的边，原问题就是是否有欧拉通路，即是否图中只有0个或者2个度数为奇数的点，原本不必须走的边，能够反复走，所以可以合并成一个点来看，那么就能转化为判断欧拉通路的问题。

abc287

• c，求图是不是链，用并查集判断是否联通，判断n-1 == m，没有度数大于2的点。
• d，维护前缀的信息和后缀的信息，若有不合法的存在，就是No。
• e，第一种做法是trie模板，第二种做法是sort，LCP最大的肯定是相邻的。

• f，树形DP，官方题解比较清楚。

  • 时间复杂度可以看树上背包的时间复杂度证明，形象地说就是每一个点对都只会在其LCA处合并一次。
• g，逐个考虑操作，先单纯考虑询问，只要贪心地从大到小选；再考虑第二个修改，只需要动态维护前缀和的位置；再考虑第一个修改，只需要离散化，然后为后面的数留空，就可以和第二个修改需要的东西一样了。

abc288

• c，并查集维护k个子图，记录点数和边数，答案就是把每个子图变成树的代价，即$\sum_i cnt[i]_{edge}-(cnt[i]_{point}-1)$
• d，每一次加减都是长度为k，不难发现，若是好的序列，下标对k取模相同的和，与其他余数都相同。

• e，DP，先考虑不能选其他物品的清空，那么第i个物品是a[i]+min(v[i-前面选了的个数 ~ i])，题中，选的数是动态的，所以考虑多记录一维状态

  • $$ \begin{align*} & 状态表示：\\ &&& dp[i, j]，代表前 i 个物品，选了 j 个的最小花费。\\ & 状态转移：\\ &&& dp[i, j] = \left\{ \begin{array}{l} dp[i-1, j-1] + cost(i, j-1) + a[i] & 选i, & \\ dp[i-1, j] & 不选i & \end{array} \right. \end{align*} $$

• f，DP，我想到[l, r]的分法的和，想不下去了

  • 正解为，f[i]，代表1~n的分法的和，s[l, r]代表从l到r代表的数，$f[i] = \sum_j f[j] \cdot s(j+1, i)$，观察f[i]与f[i-1]，转化为$f[i] = 10f[i-1] + \sum_j f[j] \cdot a[i]$

• g，我们先从答案推到输入（按某一位），发现

  • $$ \begin{align*} & a_0 = b_0 + b_1 \\ & a_1 = b_0 + b_1 + b_2 \\ & a_2 = b_1 + b_2 \\ & \space\space\space\space\space\space\space\downarrow \\ & b_0 = a_1 - a_2 \\ & b_1 = a_0 - a_1 + a_2 \\ & b_2 = -a_1 + a_2 \end{align*} $$

• 因为题中每个三进制位的信息独立，是类子集和DP问题。

abc290

• d，观察到第一次遍历是(i-1)*d % n，第二次遍历为，1 + (i-1)*d%n，而一次遍历的个数为n/gcd(n, d)
• e，答案是求坏点对的贡献和，我们自然会考虑求每个点对对所有区间的影响，思考后，发现求坏点对的贡献不容易，反过来求好点对的贡献，记录下每个值出现的位置，然后对同一个数值，双指针统计他的贡献。

• f，排列组合。

  • 确定方案数：因为最后是一棵树，所以边数为n-1，总度数为2n-2。然后每个点的度数至少为1，不妨度数先减去n，因为是一棵树，所以至少有两个点是度数为一的叶子节点，所以剩下n-2度数需要给n-2个点分配，显然，这是可以用组合数里的隔板法来分配的，那么方案数已经可以计算
  • 在考虑方案的直径，通过atcoder的官方题解给的hint的图，不难发现，直径一定是两个叶子节点，中间都是>1的节点，我们可以像图中那样拉直，只需要统计大于2的点数即可，不够的度数，用别的度数为一的补全。（由于度数多一个，就会多一个叶子节点，所以是刚好的）

  • $$ \begin{align*} &令k为度数为1的节点个数 \\ &ans = \sum_{k = 2}^{n}{{n}\choose{k}} \cdot {{n-3}\choose{n-k+1}} \cdot (n-k+1) \\ &由于当k=0或1时，{{n-3}\choose{n-k+1}}为0 \\ &所以可以利用范德蒙德卷积，进行化简： \\ &\sum_{k=0}^{a}{{n}\choose{k}} \cdot {{m}\choose{a-k}} = {{n+m}\choose{a}} \\ &再利用一些恒等变，最后得到结果 \end{align*} $$

  • 具体的过程可以luogu看下题解，这边懒得打了（逃
• g，题解看得不是很懂，jls的思路是先预处理d层的满k叉树的节点数，然后找到节点数比x大的，在贪心的删，即大的子树能删则删，一个注意点是，不是原来的树的根节点为根的要多删一条边。

abc291

• f，从前往后和从后往前做两遍的DP，或者BFS，其实本质相同。
• g，卷积。对每一位求卷积，然后因为序列是0/1，所以可以用FFT/NTT（因为不大于模数）

abc292

• c，统计a*b == x (1 <= x <= n)的方案数，答案就是cnt[i]*cnt[n-i]。
• d，并查集，记录一个集合的点数和边数。
• e，直接dfs搜索，扩展每个点最多能扩展出来的边，然后减去原有的边数。

• f，二分log，数学结论O(1)。

  • 二分，正三角形的边长，通过角度的转变，可以找出三角形的横向宽度。
  • Luogu第一篇题解有说明。

• g，区间DP。

  • 定义f[l, r, k, c]为，第 l 个到第 r 个字符串的从左到右的第k位大于等于c的方案数，最终答案为，f[0, n-1, 0, 0]。

  • 状态设计的来源为字典序大小的比较的递归定义，s1 < s2，要么当前位的大小关系，相等就是去掉当前位的大小关系。可以得到转移方程$f[l, r, k, c] = f[l, r, k, c+1] + \sum_{i = l}^{r} f[l, i, k+1, 0] \cdot f[i+1, r, k, c+1]$，同时，有几个边界条件：

    1. l > r，在右半部分会出现，这时，方案数等于左半边，所以返回 1 ；
    2. k == m，位数结束了，因为是严格递增，所以只有当区间大小为 1 时，才合法，返回 1， 否则返回 0 ；
    3. c == 10，位数超出，显然不合法。

abc293

• d，并查集，不在同一集合里ans2 --， 在同一集合里ans1 ++

• e，分治/矩阵快速幂。分治：类似于(1+a^n/2)(1+a+...+a^n/2)的形式。

  • 用公式法的话因为不一定有逆元，会错。

• f，有两种思考方式：

  1. 枚举base，check01

  2. 枚举01，check 枚举base大小

     前一种是O(n)的，后一种如果位数少，配合二分，复杂度较低。

     所以就诞生了，前1000采用第一种，后面采用第二种的缝合。。

• g，普通莫队板子题，每次加进来和移出去的代价。

abc294

• d，set模拟。
• e，两行可以哪行短了放哪行，然后就可以保证多出来部分的只有一种颜色，累加多出来的部分和新加的长度取min
• f，二分浓度，通过判断浓度大于等于mid来缩小区间，这里进行等价移项，0/1分数规划。
• g，一棵树上的两点距离dist[u]+dist[v]-dist[lca]*2可以求出，时间复杂度符合；维护dist，因为修改边权对dist的影响只有深度深的点的子树，所以可以考虑树状数组维护连续dfn序，来维护一个子树的dist的修改。

abc295

• d，状态压缩。类似前缀和，记录整体的状态，然后能和以当前位为结尾的就是前面的相同的状态。

  • 由于没想到状态压缩，转移认为时间不够，然后就寄了。

• e，概率，设第K大的数为X，X的期望能用下面的式子表示，经过转化后，变为比较好求的$P(X \ge i)$，枚举i的值，在所有第一种操作的情况中，因为i是第k大，先保证至少有$n-k+1个数 \ge i$，然后选择就行。

  • $ans = \sum_{i=1}^{m} \sum_{j=max(0, c0-c1)}^{c0} {{c0}\choose{j}} (\frac{m-i+1}{m})^{j} \cdot (\frac{i}{m})^{c0-j}$

  • $X = \sum_{i=1}^{m}i\cdot P(X=i)$

    $\space\space\space = \sum_{i=1}^{m}\sum_{j=1}^{i}P(X=i)$

    $\space\space\space = \sum_{i=1}^{m} \sum_{j=i}^{m} P(X=j)$

    $\space\space\space = \sum_{i=1}^{m} P(X \ge i)$

    可以忽略第二步的变化，从结果整理得，有$X = 1 \cdot P(X = 1) + 2 \cdot P(X = 2) + ... + n \cdot P(X=m)$，然后等价于第三步。

• f，枚举/数位DP，可以直接枚举在哪个位置，然后把前面和后面的稍做处理就可以得出答案。用string的库函数stoll会很方便。
• g，一开始因为都是连向比自己序号大的点，答案都是自己；因为连接u和v保证v能到u，那么u和v在连边后一定在同一个强连通分量，那么最小的点也就是v了，用并查集维护即可。

abc296

• c，sort，二分找存不存在。

• d，a，b（$a \le b$）两个因子，容易知道a在1e6的范围内，所以枚举a，找满足条件最小的b，其实就是$b= \lceil{m/a}\rceil$，枚举过程中判下a与b的大小关系和$b \le n$，最后判无解。

  • 对这种暴力枚举复杂度还是估不好。

• e，实际上是每个点出度都为1的内向基环树森林，跑拓扑排序，把不在环外的点去掉，然后留下的入度之和就是环的总长度。

  • 想到找环了，但不清晰。
• f，分类讨论：1. 含有的元素不同，No；2. 同个集合内有相同的元素，可以利用相同元素，别的自由交换； 3. 保持A不动的话，两次交换逆序对的奇偶性不变。
• g，计算几何板子题，凸多边形和点的关系，二分logn做法。

abc298

• b，模拟，注意是a=1的地方b为1。
• c，模拟，虽然感觉时间复杂度挺怪的。（？）
• d，类字符串哈希。
• e，概率dp或者记忆化搜索，注意不是等概率的事件，不能win/tot来求概率，多选择的，所以每一次都需要求概率。
• f，看得出是比较典的题，但是确实就不会做，想到假$O(n^2)$，但是不太能想。容易看出，离散化后是不大于n*n的区域，然后从大到小枚举行，从大到小枚举列，到遇到相交的点为空值时退出，显然这样包含最优解，后面需要想时间复杂度。不难发现要访问的点数最多是总点数+n，实际是$O(n)$的复杂度。

• g，算是特殊的区间dp，不可能分割可以优化直接返回。（浮点数有点问题，把浮点数当作INF，还是早转类型好一点。）

  • NOI1999 棋盘分割

abc301

• e，状压DP，因为题中糖果数只有18，地图也不大，预处理糖果、起点、终点之间的距离是可接受的。这样，问题就转化为，我们要采取怎样的顺序去访问糖果，且什么时候停止访问，去到终点。但是，这样的状态一共是$n!$个，显然是不可接受的，我们观察到，我们需要求的答案和具体的访问顺序是无关的，所以，除了当前所在的位置，需要用来计算到下一个状态的代价之外，在这之前的顺序信息是没有价值的，也就是可以丢弃的，而这就是我们状态压缩的地方，状态变成$n \cdot 2^n$（选了哪些点，现在在哪个点）。

• f，DP，总体考虑分别维护前i位的我们分类出来的合法状态的方案数。

  • 先考虑最朴素的做法$O(52^n)$，然后判断。在判断过程中，从DDoS形式出发，我们的状态共有四种：

    1. 没有出现两个相同的大写字母
    2. 出现两个相同的大写字母，但没有小写字母
    3. 出现两个相同的大写字母，且出现小写字母
    4. 出现DDoS
  • 显然，我们的答案就是前三种状态。
  • 我们对第一种状态进行进一步的划分，可以分别统计每个大写字母出现了没有，这样，我们可以用 $26^n$ 种状态来描述大写字母的情况。这样之后，第一种状态是容易维护的，只需要考虑大写字母和问号即可。这里问号先考虑暴力枚举26个大写字母。；同时，第二种状态的方案数也容易维护，从第一种状态的方案数很容易从第二种状态转移过来；第三种情况，也容易从第二种状态转移过来。

  • 帮助理解状态设计的用意：

    • 当确定的大写字母出现相同的情况，显然状态1的方案数在后面不会有了。
    • 当第三种状态后面又出现大写字母，显然，就变成了不合法的DDos，方案数丢弃。
  • 然而这样的状态数有 $n \cdot 26^n$ 种，仍然不可接受。观察到，我们并未为对问号单独有很好的处理，只是把它暴力的枚举成大写字母和小写字母。仔细思索可得，我们不需要每次记录下问号的具体取值，其实只需要知道我们一共有多少个大写字母出现过1次和确定出现的大写字母的集合，问号在作为大写字母时，转移到第二种状态，就是在出现过的选一个出现两次，在第一种情况，就是在剩下没有出现过的大写字母种选一个。作为小写字母也是如此，如此一来我们只需要统计不同的大写字母出现过几个还有另外第二第三种状态的方案数即可。

• g，计算几何。结果要么是，一条线上被挡的点，要么是多个线的交点，然后可以把这些线上被挡的点个数的和。考虑求出的坐标很可能是小数，那么我们用分式的模板类来表示。

  • 直接用y = kx + b和z = kx + b的形式来表示直线。实现的话，jls的代码清晰明白。

abc302