期末了，在考期结束后，我们队重新开始了日常的Regional训练赛。今天的题目比较简单，赛场上有思路的有8道题，不过最终只过了6题。J题由于细节问题被卡了，C题虽然有思路但是已经没时间写了。F题很早就想出了O(n^3logn)的做法，但是由于数据组数较多，感觉要达到O(n^2logn)才能过，所以不太敢写，而且原来的思路最快也要O(n^3),也没有顺着思路继续想。赛后被告知O(n^3)完全能过这题……
A. Automatic Cheater Detection && B. Counting Weekend Days
签到题，读懂题意就行。
C. Toll Management IV
树链剖分
题目大意：给出n个点m条边的带权无向图。其中前n-1条边构成了一棵树，为该图的最小生成树。现在要对每一条边i求出Ai和Bi，满足第i条边的权值在[Wi-Bi,Wi+Ai]区间内变动时，仍然满足原树为最小生成树。输出的答案为：
S = $\sum\limits_1^m(iA_i + i^2B_i)$.
如果Ai或Bi为正无穷或负无穷，则用-1来代替它
题目的关键就是对每条边求出它的Ai和Bi。
对于非树边，显然它可以增加到无穷大。那么它可以减小多少呢？很容易发现应该是ui到vi的路径上的最大值。
对于树边，显然她可以减小到无穷小，那么它可以增大到多少呢？通过画图我们可以发现，应该为跨过它的非树边的Bi的最小值。
这两种操作都可以使用树链剖分来维护。
D. Owllen
贪心
题目大意：给出长为n的仅由小写字母组成的字符串，问对长度和它相同的仅由小写字母组成的字符串中，和它的最长公共子序列的长度最小为多少？
简单的分析一下就可以发现，构造只由原序列中出现次数最少的字母组成的字符串，则此时新字符串与原串的LCS最小，长度为原串中该字母出现的次数。
E. Sum of MSLCM
数学题+分块优化
题目大意：有200组数据，每组数据给出数字n(1 < n <= 2e7)，对每个数字i(2 <= i <= n)，找出一个集合使得该集合的lcm等于i且该集合中数字之和最大，记其和为MSLCM(i)。输出$\sum\limits_2^n(MSLCM(i))$。
我们很容易发现要求的集合即为由n的约数组成的集合。所以要求的公式应该为$\sum\limits_2^n$
$\sum\limits_{d\mid i} d$
但是面对这个公式我们发现并不能在时限内解决这个问题。
我们换一种思路来考虑，即每个数i对答案的贡献。第i个数被加了k次，k为$1\dots n$中是i的倍数的数的个数，即$\lfloor\frac{n}{i}\rfloor$。，因此，可以将上式化为：$\sum\limits_1^n(i\lfloor\frac{n}{i}\rfloor) - 1$。之所以要减1，是因为我们在使用$\lfloor\frac{n}{i}\rfloor$时将$1$的$MSLCM$也算入了前面的算式中。
由于n的范围很大，直接计算该公式仍不能在时限内解决该问题，这就用到了之前常用的一个技巧，根据$\lfloor\frac{n}{i}\rfloor$的分段性进行分段优化，这样可将单组数据的时间复杂度优化到$O(\sqrt{n})$
F. Unique Party
算法尚不明确
G. Honey King
算法尚不明确
H. Design New Capital
FFT
题目大意：在坐标平面上有n个点，这些点均不在坐标轴上。现在要从中选出一些点，使得$(0,0)$点到这些店的曼哈顿距离之和小于等于坐标平面上的其他任意点。问在选取个数为$1$到$n$个时，分别有几种选取方法。
由于是曼哈顿距离，所以可以将x、y分开考虑。可以发现，为了达到题目要求，必须使选出的点的横坐标的中位数等于0（如果有两个则0位于这两个数之间）且纵坐标也满足同样条件。
又由于坐标轴上没有点，因此在选择的点的个数为奇数时，其中位数必然不为0，因此此时没有任何选取方案。
在选择的点的个数为偶数时，则可发现，若在第一象限中选择一个点，则必然在第三象限中选择一个点与其对应。二四象限也同理。
设选择的总点数为$2k$，再设第一象限中有$A$个点，第二象限中有$B$个点，第三象限中有$C$个点，第四象限中有$D$个点。则方案数为：$\sum\limits_{i = 0}^k C_A^i C_C^i C_B^{k - i} C_D^{k - i}$
我们发现这是一个卷积的形式，因此可以使用FFT来加速，从而在$O(n\log n)$的时间复杂度内得出所有总点数为偶数的方案数。
由于需要取模，因此使用的应该是NTT。
I. Numbered Cards
状压 + 数位dp
题目大意：有$n$个数，值为$1$~$n$，要从中选出一个子集，使得该集合中任何两个数的十进制表示中都不含相同的数字。问有多少种选取方法。（$n \leq 10^9$）
首先想到dp来表示之前已经用了几个数, 然后转移的时候用到了偏序(因为是集合的原因),我们强制让最后一个数包括最小的那个. 然后转移的g[2^i]是用3(4)进制状压的数位dp做.
重点：
- dp的想法来做,状压
- 集合无序性,我们用偏序做.
- 二进制都是恰好一定要用掉这么多,不能采用用不超过这个范围(但没必要全用完)这样的思维,因为会有很多重复情况. ——这是赛场上差点犯的错误QAQ
- 用3进制状压:不能用,要用还没用,要用已经用过了至少一次
J. The Hypnotic Spirals
计算几何+积分
题目大意：极坐标系中有一个螺旋线$r = a\theta$，还有n条射线$\theta = b_i$，以及m个点$(r_j, \theta_j)$，螺旋线和射线将坐标平面切割成了多个区域，所有的点均不在射线和螺旋线上，现在要把所有点所在的区域涂黑，输出$\frac{要涂黑的总面积}{10}$。若要涂黑的总面积为无穷，则输出-1
大致思路一下就有, 就是算出来第i个点属于的上一圈螺线和下一圈螺线,然后再看弧度在哪两个射线之间. 但是有细节要注意:
- 看弧度在哪两个之间,涉及到转一圈的问题,我们设置一个-角度(代码中没设但是特判了)和一个大于$2\pi$的角度,这样好找,然后$k(设角度为b_i + 2k\pi)$就能统一找了.
- 我们需要用map来判重复,但是记着一个负角度和一个大于$2\pi$的是一样的,需要特殊处理
- 本题中的特殊情况:
- 在第一圈并且有负角的时候,负角度没用,我们应该从0开始积分
- 在最内一圈,不用减去里面的圈,因为没有.
- 在最内一圈和外面一圈的交界处,有的用减去里面的圈,有的不用,分段计算. 总结起来就是,最内圈先是从0开始,并且本身不是环状,影响了这三个