本文共 2883 字，大约阅读时间需要 9 分钟。

前言

上一篇似乎咕咕咕了233333

来Atcoder玩耍

**ARC093-E - Bichrome Spanning Tree

总感觉这题也不算很难…

但是自己又还是不会做… 相当于要求你一个同时包含了黑边与白边的$MST$ 遇见生成树的题，一般先联系一下最小生成树的关系 设原图的$MST$为$T$，边权和为$S$ 先任意找出一个$MST$，对于每条不在当前$MST$的边，我们求出一个$num[i]$表示他的权减去他能替换掉$MST$的边中最大的边权 然后分类讨论 如果$S>X$，显然无解，否则设$eq=\sum [num[i]=X-S],up=\sum [num[i]>X-S]$ 当$S=X$的时候，我们有两种操作，分别是就让当前的$MST$成为新图的$MST$，以及构建一个新$MST$使其满足上述条件 第一个就是 $(2^{n-1}-2)\ast 2^{m-n+1}$，前面去除了$MST$全为黑或白的情况 第二个就是$2\ast (2^{eq}-1)\ast 2^{up}$，表示找出来的$MST$全为白或黑，但是能替换的边中至少有一个是可以替换使得合法的 当$S<X$的时候，贡献就是上面的第二个

**ARC095-F - Permutation Tree

自己sb

先分析一下他这种造树方法造出的是个什么树 从表面看不好看，我们考虑从小到大枚举数，即按序枚举$1,2,3..$出现的位置 记录一个$mx$表示当前最右的点在哪 每枚举到一个$i$，先让他和$mx$连边，再让$mx$与$i$所在的位置取$max$ 容易知道这就是他给出的构造方法所构出来的树 再仔细想一想的话，可以发现的是，这样的构造方法实际上是先出来一条链，链上每个点挂上一些点 那么如果原图非这样的图就gg了，判的话显然构造的链是直径，找到瞎判即可 然后再算答案 我们可以将链上每个点挂的点计数，不妨设为$cnt[i]$ 容易想到，肯定是让$cnt$字典序最小的那一面开始挂点 那么如果枚举到链上第$i$个点，已经用了的编号为$lst$ 那么让$[lst+2,lst+cnt[i]+1]$按序填在答案数组，在最后填上$lst+1$ 可以发现，这样一定是字典序最小的方案

发现自己很容易忘记分析题目构造的性质…

类似从小到大加数这样的常规操作

ARC095-E - Symmetric Grid(口胡

没有算复杂度qwq…

容易发现，行和列是不相关的操作 那么先枚举行放什么，再判断列能不能放好 开搜，枚举每行的匹配行与每列的匹配列 行确定之后列的确定只需要知道某列reverse之后是否与另一列同构 发现状态数极少 于是就pass了

**ARC096-F - Sweet Alchemy

$n$不大也不小的题就有点恶心了…

注意到儿子的选择次数一定大于等于父亲，那么可以转化题意 每次选一棵子树$+1$，只有以$1$为根的子树可以无限选其他都仅能选$D$次 值域小一点似乎可以直接背包？ 但是值域有点大…这时候要想到一个套路就是 在大范围贪心，小范围大力$dp$ 考虑两个物品分别有$v_i,v_j$的费用与$w_i,w_j$的贡献 那么我们考虑如果取了$v_i$个$j$物品与$v_j$个$i$物品的时候，他们占用的费用是相同的，但是贡献肯定有一个较小 那我们可以贪心地把较小的那个给去掉换成较大的那个，此时费用仍然相同但是贡献会变大 所以最后，一定存在是一些都在小于$n$的个数，其余的是通过贪心取值的 这里的贪心我们可以用一个经典的性价比贪心来完成 故每个物品取$min(n,D)$个出来单独做$dp$，剩余的用贪心来贡献

**ARC096-E - Everything on It

感觉一下就是个容斥，脑子混乱了竟然有一个东西没想到…

用经典容斥设$f[i]$表示至少有$i$个非法选择方案，窝之前居然naive的想设2维状态… 式子写一下 $$\sum _{i=0}^n(-1{)}^i{2}^{2^{n-i}}{C}_n^i\sum _{j=0}^i\sum _{k=1}^{j}S(j,k)\ast C_i^j\ast (2^{n-i}{)}^k$$ 解释一下 前面那个$2^{2^{n-i}}$是指不包含非法酱的集合有多少 首先是枚举至少有多少个酱非法选择了，其次枚举有多少个出现了一次的酱料.我之前居然naive的卡在了不会算他们合在一起的方案数…md就是个斯特林数啊… 后面那个东西是让每个合法酱料在其中任意出现的方案数 这个东西可以$n^{3}logn$做了… 观察式子感觉没法优化…那就从组合意义之类的入手 随便化开可以得到一个这样的东西 $$\sum _{j=k}^{i}S(j,k)\ast C_i^j$$ 注意他的现实意义是，将$i+1$个不同求扔进$k+1$个不同的盒子中的方案数。证明的话考虑这个式子枚举的是不与$i+1$放在一起的球是什么… 那么就可以愉快$n^{2}logn$了

转载地址：http://wrmu.baihongyu.com/