ARC104
A
题解
一道小学数学题，$X = \frac{A+B}{2}, Y = \frac{A-B}{2}$。B
题解
一道暴力题。发现子串合法的充要条件是 $cnt_{\text{A}} = cnt_{\text{T}} \land cnt_{\text{G}} = cnt_{\text{C}}$，暴力统计即可。C
题解
简单区间 dp。发现 $[1,2n]$ 可以拆成若干合法且不交的段，段内 $[i,i+\frac{len}{2}-1]$ 为某些 $a_i$，$[i+\frac{len}{2},i+len-1]$ 为某些 $b_i$。据此区间 dp 即可，一个区间合法当且仅当它本身合法或者它能被拆成两个区间。D
题解
很平凡的一道计数啊。考虑将所有数都减去 \(x\)，那么就要求选的数和为 \(0\)。
正负分开考虑，\(0\) 可以任意选。需要多重背包求 \(f_{i,j}\) 表示选 \(1 \sim i\) 的数和为 \(j\) 的方案数。前缀和优化是平凡的。
E
题解
首先期望转化成 $\text{LIS}$ 总和除以方案总数（即 $a_i$ 乘积）不必多说了。观察可发现题目 $n$ 特别小，考虑 $O(n^n)$ 枚举 $x_i$ 的相对大小关系（排名），固定排名后算出 $\text{LIS}$，再计算这种排名对应的方案数。于是现在问题变成了有 \(m\) 个数，每个数的上界为 \(b_i\)，要求序列单调递增的方案数。考虑直接套 CF1295F Good Contest 的做法，\(b_i\) 离散化后设 \(f_{i,j}\) 为第 \(i\) 个数位于值域第 \(j\) 段的方案数。转移枚举以 \(i\) 为右端点的极长值域位于同一段的区间左端点 \(k\)，以及 \(k-1\) 位于哪个段。系数是在 \([1,len_j]\) 中选 \(i-k+1\) 个互不相同的数的方案数（为 \(\binom{len_j}{i-k+1}\)）。可得：
\[f_{i,j} \gets \sum\limits_{k=1}^{i-1} \sum\limits_{x=1}^{j-1} \binom{len_j}{i-k+1} f_{k-1,x} \]暴力计算即可。
总时间复杂度大概是 \(O(n^{n+5})\)（没仔细算，实际远远达不到）。
F
题解
考虑连边 $(i,p_i)$（若 $p_i = -1$ 则不连边），可以发现形成了一篇内向树森林且这个森林存在一个 dfs 序为 $1,2,...,n$。这棵森林有如下性质：
- \(\forall v \in son_u,h_u > h_v\)
- \(\forall v,w \in son_u \land v < w,h_v \le h_w\)
考虑一个 \(p\)，我们寻找一个最优的 \(h_0\)，使得它能生成 \(p\)。显然 \(h_0\) 的每个数都要取到下界。
因为一棵树的点编号为连续的区间，所以考虑区间 dp。
设 \(f_{i,j,x}\) 为 \([i,j]\) 形成了一棵树且 \(h_i = x\) 的方案数，同时设 \(g_{i,j,x}\) 为 \([i,j]\) 形成了一片森林且最后一棵树的根的 \(h\) 值 \(= x\) 的方案数。
有转移：
- \(f_{i,j,x} \gets g_{i+1,j,x-1}\)，表示以 \(i\) 为根将 \([i+1,j]\) 的森林连起来。
- \(g_{i,j,x} \gets f_{i,j,x}\)，表示一棵树也算森林。
- \(g_{i,j,x} \gets \sum\limits_{k=i}^{j-1} [x \le a_{k+1}] \sum\limits_{t=1}^x g_{i,k,t} \times f_{k+1,j,x}\)，表示枚举这片森林的最后一棵树（此时森林一定要有至少两棵树）的树根 \(k+1\)，\(h_{k+1}=x\)，前面的数的 \(h\) 值都要 \(\le x\)。
- \(g_{i,j,x} \gets \sum\limits_{k=i}^{j-1} [x \le a_{k+1}]g_{i,k,x} \times \sum\limits_{t=1}^{x-1} f_{k+1,j,t}\)，仍然表示枚举最后一棵树的根 \(k+1\)，但是 \(h_{k+1} < x\)，此时把最后一棵树的 \(h\) 值整体加直至 \(h_{k+1} = x\)。\(< x\) 是因为要避免算重。
答案即为 \(\sum\limits_{x=1}^n f_{1,n,x}\)。
直接转移是 \(O(n^5)\) 的，因此再设 \(sf_{i,j,x} = \sum\limits_{t=1}^x f_{i,j,x},sg_{i,j,x} = \sum\limits_{t=1}^x g_{i,j,x}\)，这样整道题就变成 \(O(n^4)\) 了。
ARC121
A
保留 \(x,y\) 中的次大，最大，次小，最小，显然答案一定在它们之间。然后暴力算。时间复杂度 \(O(n \log n)\)，瓶颈在排序。
B
若所有颜色均出现偶数次，则答案为 \(0\)。
否则若只出现了两种颜色，则枚举一种颜色的所有 \(a_i\)，lower_bound 去找另外一种颜色中和 \(a_i\) 最接近的值即可。
如果三种颜色都出现了，那么在只有两种颜色的基础上，答案还可能是两种出现奇数次的颜色跟另外的颜色最接近的值的绝对值之和，取最小值即可。
C
每次肯定是选择一对逆序对然后交换。如果当前没有可以操作的位置，就选 \(n-1,n\) 或者 \(n-2,n-1\) 换，具体是什么看奇偶性。
看起来不是很对，但是能过（（（
D
考虑如果限制每次只能选两个怎么做。显然可以将序列排序后贪心地选最小和最大，次小和次大，等等配对。
如果每次可以选一个，那么就相当于选它和一个 \(0\) 配对。然后就想到枚举选一个的次数，然后再按上面的方法贪心。
时间复杂度 \(O(n^2 \log n)\)。
E
显然 \(a_i\) 可以是除了 \(i\) 的所有祖先以外的任意点。考虑求 \(a\) 的逆排列 \(b\)，\(b_i\) 就不可能是 \(i\) 子树内的点。
考虑一个容斥，\(g_i\) 为钦定其中 \(i\) 个结点不合法的方案数。那么 \(ans = \sum\limits_{i=0}^n (-1)^i g_i (n-i)!\)。
现在问题转化成了如何求 \(g_i\)。考虑树形 dp，\(f_{u,i}\) 表示 \(u\) 子树内有 \(i\) 个点不合法 且只考虑不合法的点 的方案数。
- 不同子树，因为不合法的范围不交，所以可以直接类似树形背包合并，\(f_{u,j+k} \gets f_{u,j} \times f_{v,k}\)。
- 最后计算 \(u\) 不合法的情况的 dp 值时，\(f_{u,i} \gets f_{u,i-1} \times ((sz_u-1)-(i-1))\)，意思是 \(u\) 原本可以选子树内的 \(sz_u-1\) 个点，有 \(i-1\) 个点已经被选了。
那么 \(g_i = f_{1,i}\)。
时间复杂度 \(O(n^2)\)。
F
如果存在一个叶子结点值为 \(1\)，且连向它的父亲的边是 OR，那么这样就是合法的。因为可以最后再缩它，那么根结点的值就是 \(1\) 了。
否则分类讨论：
- 如果值为 \(1\) 且 AND 或者值为 \(0\) 且 OR，那么什么时候缩边都没有影响，可以立即缩。
- 如果值为 \(0\) 且 AND，就相当于在一个时刻将它的父亲的值设为 \(0\)。显然要贪心地一开始就立即缩。
然后我们发现缩边可以按照深度从大到小缩，顺序确定了，考虑树形 dp，\(f_{u,0/1}\) 表示 \(u\) 子树已经操作完了且不含 \(1\) OR，\(u\) 的值为 \(0/1\) 的方案数；\(g_u\) 表示 \(u\) 子树已经操作完了且包含 \(1\) OR 的方案数。转移也是显然的，分八种情况（\(0/1\) OR/AND \(0/1\)）讨论即可。
时间复杂度 \(O(n)\)。
标签：AtCoder,limits,板刷,题解,sum,合法,vp,text,gets From： https://www.cnblogs.com/zltzlt-blog/p/17323186.html