written on 2022-08-12
今天的题目……主要偏思维吧。。想到了就不是很难，想不到的话就毫无思路。
但是仍然暴露出许多问题，第一题其实是一道简单的动态规划，简化题意就是给出一个正整数集，让你选出没有交集的两个子集，使得在保证两个子集和相等的前提下，最大化子集的和。数据范围：元素个数 \(\le 500\)，元素总和 \(\le100000\)。
一开始思路完全没有打开，打了个爆搜加背包，然后看着代码心想这哪有优化空间，然后痛苦地阅览着后面的题目毫无思路，，、、
最后突然想起来运用动态规划的思考方式，考虑设计状态，列出决策。当时列的状态是 \(f_{x,suma,sumb}\) 表示决策到第 \(x\) 个元素，集合 \(A\) 元素和为 \(suma\)，集合 \(B\) 元素和为 \(sumb\) 的情况是否存在，然后加了个记搜。显然这样的方式数组是开不下的，而且会 \(T\)。最后就没有时间多想，然后就挂了/dk
但是这真的是一道 dp 大水题。稍作转化，求子集和最大，即是要求剩下的和最小。考虑决策，发现只需要考虑两个集合的元素和之差即可，即设 \(f_{x,c}\) 表示决策到第 \(x\) 个元素，两集合差值为 \(c\)，剩下的元素和最小是多少。然后转移与答案统计就显然了。
这题让我充分认识到自己的愚蠢，看来还需要多多锻炼脑子要不然真的会生锈
一开始真的没想到竟然是高斯消元的题目，因为题目要求的期望可能会造成在两个状态间的循环，然后就不免有些束手无策了。然而事实上这类题却是一类套路题，之前写过一道序列上的随机迭代期望题，好像是用马尔科夫过程解决的，虽然我已经忘记了。然后对于这道题的话，我们根据要求解的目标设计状态。补题时一开始我设 \(f_i\) 表示从 \(1\) ~ \(i\) 的期望，但是这样的话，边界是无法设定的，在多变的信息中，我们需要找到不变的那个量。 题目中提到，走到 \(n\) 号节点就停止，因此我们设 \(f_i\) 表示从 \(i\) ~ \(n\) 的期望，那么边界就是 \(f_n=0\)。
然后，观察到题目要求的是异或的期望值，由于异或是按位计算的，同时根据期望的线性性，就可以考虑按位计算每一位异或值为 \(1\) 的期望，最后累计。
接着考虑对每一个点进行分析。可以发现对于每一个节点，有方程：
\[f_x=(\sum_{y\in son_x,H_{val[x][y],p}=0}f_y+ \sum_{y\in son_x,H_{val[x][y],p}=1}(1-f_y))\div deg_i \]据此列出 \(n\) 条方程，其中第 \(n\) 条方程为 \(f_n=0\)。然后移项，用高斯消元的技巧计算出 \(f_1\)，即本题最后的答案。注意自环的加边只用一条。
总体而言这题用到的技巧较多，但是思路很清晰自然，是一道好题。
\(C,D\) 两题主要在于对题目的深入分析，发现性质然后求解。比赛时思路打不开，于是没有写出来。\(C\) 的话用递归来处理表达式的问题，然后对加法乘法分别分析取值的上限。然后就不难了。\(D\) 的话，关键在于自己造一些样例模拟，发现规律。然后将后缀转化为前缀，插入 \(\tt{Trie}\) 树，在 \(\tt{Trie}\) 树上分类讨论跑树形 \(\tt{dp}\) 即可。
\(E\) 的思路很迷，个人不是很欣赏这题的出题方向，就不写了。