Day1 A
题意
\(N\) 条线段，\(k\) 个点，每个点会使所有包含他的线段删除，求最后有多少线段被删
\(n\leq100000, s_i,t_i,p_i\leq1000000000\)
做法
离散化，看每个线段有无包含点即可
Day1 C
题意
给定 \(n,m\)，以及长度为 \(n\) 的数组 \(a,b\)，求一个 \(1-m\) 的排列，进行 \(a_i = p_{a_i}\) 的变化，使得 \(a_i=b_i\) 的数量最多，且变化后的 \(a\) 字典序最小
\(n\leq10^5,m\leq60,a_i,b_i\leq m\)
做法
按第一次出现的位置逐个贪心，使用计算最多位置数可以建带权二分图，求最大匹配，一共只需要 \(O(m^2)\) 次最大匹配，一次 \(O(m^3)\)，一共 \(O(m^5)\)。
Day1 F
题意
给定长度为 \(n\) 的括号序列，\(q\) 次操作，将区间左右括号反转或询问通过最少多少次一下操作将区间变为合法的括号序列
1.在串前加上 ) 2.在串尾加上 ( 3.交换相邻括号
\(n,q\leq1.5\times10^5\)
做法
按套路将括号序列看为 1 和 -1。
考虑怎么求一个区间次数最少，首先有 1 和 2 操作只用于将总和变为 0，然后所有操作都是交换，那么容易知道最少操作次数为，求前缀和后的 \(\sum_{p_i<0}\lvert p_i\rvert\)，同时要支持前缀操作和反转 1 和 -1，考虑分块。
将每一个块分开求前缀和，并记录每一种前缀和的数量，即可快速求解答案
区间反转散块暴力重建，整块打反转标记即可
####Day1 K
题意
给定 \(n\) 和 \(D\)。\(n + 1\) 个人，给定每人的初始位置和速度向量。初始时第 \(n + 1\) 个人患病，当患病的人与不患病的人相距不超过 \(D\) 时，将会传染，求每个人被感染的时间。
\(n\leq10^3,D\leq10^4,-10^4\leq x_i,y_i,vx_i,vy_i\leq10^4\)
#####做法
任意两个人相距不超过 \(D\) 的时间是一段，可以容易解出，然后可以使用类似于 Dijkstra 的方法转移求出每个人最早被感染的事件。
Day1 L
题意
给定 \(k\) 和点数为 \(n\) 的以 1 为根的树，每个点有权值 \(a_i\)，等概率随机 \(k\) 个可重复的点，将其 lca 将付出 \(\prod a_{p_i}\) 的代价，已知每给点的代价的期望 \(E_i \mod 10^9+7\)，求 \(a_1\) 的最小可能值
\(n\leq2\times10^5,k\leq10^9\)，\(k\) 为奇数
做法
将 \(E\) 做子树和，可以得到新的 \(E\)，其表达式为 \(E_i=(\frac{1}{n}\sum_{x\in sub(i)}a_x)^k\)，若能模意义下的求 k 次根号即可求可行的 a
由于 \(10^9 + 6 = 2 \times 500000003\)
当 \(k \neq 500000003\) 时，\(k\) 在模 \(10^9+6\) 意义下有逆元 \(invk\)，对于任意数 \(x\)，用模 \(10^9+7\) 意义下的原根表示有 \(x = g^p\)
\[ x^{\frac{1}{k}}=(g^p)^{\frac{1}{k}}=g^{p\frac{1}{k}}=g^{p*invk}=x^{invk} \]
并且该解为是唯一解
当 \(k=500000003\)，任意数 \(x^k\) 在模意义下等于 1 或 -1 或 0。所以所有的 \(E_i\) 必须为这三个值当中的一个。
对于根的时候，不妨将其拆为 \(cnt_{son} +1\) 个部分，将儿子的那些乘上 -1，就是求这些的和的最小可能值。
容易发现若有大于等于三个非 0 的，或没有非 0 的，那么和肯定可以为 0
若有两个，若相等则不可能为 0，不等则可以为 0
若有一个，则等于那么和肯定是 1，或者原根