Day2 A
题意
给定 \(n\times m\) 的矩形，每个格子有黑白两种颜色，每次可以操作选定一个同色连通块将其变色。现给定末状态求可能的初状态的可能数
\(n,m\leq2000\)
做法
容易发现对于一个格子，若终态时相邻有不同的，那么肯定没有操作过，其初始颜色一定与最终一样，剩下的可以任意操作，那么代表其初始颜色随意，所以答案就是 \(2^{cnt}\)。
Day2 B
题意
给定 \(n\) 个点 \(m\) 条边的有向图，询问是否可以保留若干条边，使得每条边都有入边，且不存在双向边
\(n,m\leq2\times10^5\)
做法
先保留所有单向边，对于双向边的部分，可以构造一个二分图，左侧每个点代表双向边，右边代表原本的点，每个双向边想两个端点连边，计算是否能是所有都匹配，跑最大匹配即可。
Day2 D
题意
给定一个由 \(n\) 个点的，由红边组成的外向树，每个点有点权 \(c_i\)，每次可以选定一条由红边组成的从 \(u\) 到 \(v\) 的一个路径，将路径上的所有边删去，再在加上 \(u\) 到 \(v\) 一条蓝边，可以操作任意次，求最终最小\(\sum_{f(i,j)=1}c_ic_j\)。其中\(f(i,j)\) 为 \(i\) 能否到达 \(j\)
做法
容易有每次是到某一个叶子节点，记录当前子树往上连的是哪一个点，然后可以写出 DP，容易发现这个 DP 需要快速求解形如 \(kx + y\) 的最小值的形式，所以需要对每个子树维护一个凸包，可以直接启发式暴力维护凸包，用set 维护动态凸包即可。
Day2 E
题意
给定一个长度为 \(n\) 的字符串和一个指针，每次可以花费 \(C\) 的代价移动指针一格，或者花费 \(a_p\) 的代价改变指针指的位置的字符，对于指针的每一个初始位置，求最少代价使得字符串为回文串。
做法
先去除最边界的回文部分，然后显然指针肯定会走到最左或最右其中的一个，那么其所有可能走过的区间只有 \(O(n)\) 种，对于每一种走过的区间，改变的部分的花费不变，而走的部分可以移动指针初始位置可以简单维护，那么直接暴力移动初始指针位置维护即可
Day2 F
题意
定义序列 \(a\) 的漂亮值为 \(\sum[a_i\geq a_{i-1},a_i\geq a_{i + 1}]\)。给定长为 \(n\) 的序列 \(a_i\)，将其任意重排，使得漂亮值最大，求最大的漂亮值。
\(n\leq3\times10^5,\sum n\leq 5\times10^6.1\leq a_i\leq10^9\)
做法
先考虑如下构造，将所有数升序排列， 容易发现，答案就是 \(n - Cnt + 1\)，\(Cnt\) 为不同数的种数，考虑沿用该策略，从小往大放，每次将最大的放在最后面，可以将前面出现的最短的一段拿来当不同段之间的分割，每次找最少的那些，这样可以使一些段消失，最后看剩余多少段就可以了