2020牛客暑期多校训练营（第二场）题解

首先由于这场比赛的代码写得有点过于仓促，主要都是考试写得代码，和大部分根据框架改的代码，所以可读性一般，因此这篇题解就不给代码了，见谅！
A: All with Pairs
首先这道题要求我们求一个最长前缀和后缀的关系，我们可以把所有的前缀和后缀都存在一个hash表里面，然后我们发现有些前缀和后缀会算重复，当且仅当我们可以把最长的后缀和前缀合在一起再算一遍，然后我们可以发现这个就是KMP的next数组，然后我们只需要把字符串做一遍KMP和hash表就可以求出这题需要的答案，最后我们统计一个长度出现了几次然后我们可以用一个数组记录一下，最后累加即可，不要忘记取模！
B: Boundary
这题我们可以通过三点确定一个圆，首先我们已知了(0,0)在边界，因此我们可以通过枚举另外两个边界上的点，来确定这个圆，然后由于我们可以按照三点共圆的公式确定它们的圆心，最后统计那个圆心出现的次数最多即可！
然后具体实现可以用sort或者map来实现！
C: Cover the Tree
要求我们cover这个树，一种显而易见的贪心方式是我们肯定要尽可能地让叶子之间两两连接
一种构造方式我们对于这个最后的结点按照dfs序然后我们一一对应：
接下来我们要分两种情况讨论：
当叶子结点个数为偶数：1-n/2+1,2-n/2+2...n/2-n一一对应连接即可
当叶子结点个数为奇数：1-(n+1)/2+1,2-(n+1)/2+2...(n+1)/2-1-n 最后要一个配对就是(n+1)/2-root
然后root必须是一个非叶结点，这个需要我们事先特判一下！
值得注意的是我们需要考虑个数为1或者2的情况，直接特判输出即可！
D: Duration
签到题，直接算出总时间作差即可！
E: Exclusive OR
根据高斯消元的思想，考虑线性代数秩的个数不会超过20，然后我们发现ans[i]>=ans[i-2]，显然可以放两个相同的数来抵消，因此我们可以只需要求出前20个的ans即可，然后这个我们可以做20次FWT，就是异或卷积！
然后注意奇数和偶数的答案不同，至于这个秩的个数，如果大家会线性基可以通过线性基来考虑
其实线性基就是一个秩，线性基的大小不会很大，但是他可以异或出包括所有种本来可以异或出来的ans，然后这里可以类比一下方便我们理解！
本题的时间是复杂度O(20nlogn)
F: Fake Maxpooling
是一个拼题，虽然暴力点的做法好像可以过题，但是正解是O(n^2)的，我们考虑记忆化搜索或者直接gcd筛，来get一下gcd的表，然后就非常套路，我们用两个单调队列来求出答案，然后累加即可！
单调队列的方法就是我们可以行和列个维护一个，先完成一个行的ans，然后分列插入单调队列即可！
G: Greater and Greater
这题看到数据范围40000，就大体是bitset！
然后我们可以sort一下然后我们可以把查询和插入放在一起，然后我们可以反复左移右移，我们按位类似于FFT那样的匹配就可以求出满足条件的点！
这题的核心是我们可以通过bitset左移右移这样可以加速我们单次查询的速度，可以类比于字符串匹配的FFT或者bitset算法来理解！
H: Happy Triangle
码码码就好了，可以分几种情况考虑
考虑维护一个set同时维护一个线段树或者树状数组，当然你splay也可以，这样就是两个splay！
然后set的用途就是我们求两个小于等于它的最大数然后我们对于这两个pre然后看一下两个数的和是否能和当前的边构成一个三角形
还有一个就是维护set大于他的插值，然后可以用动态开点的线段树维护或者树状数组或者splay，然后我们可以方便实现细节定义两个哨兵结点-1和Inf，是个技巧大家可以参考下！
个人感觉这道题没有什么思维难度，主要是有代码的细节，然后这些细节我们可以理清逻辑或许能够更好地实现！
I: Interval
容易发现这题是一个类似于网络流最小割的模型，但是我们直接用dinic最大流可能会tle，因此我们可以发现模型是一个平面图我们把它转化成对偶图就可以了！
由于作者还不太会平面图转对偶图，待补，抱歉！
J: Just Shuffle
首先由于P是一个大质数，所以保证有解，这点先考虑到，其实那个-1是陷阱！
然后我们发现是一个置换的操作，我们找这个置换的循环节，然后我们平移一下就可以了，有一种写法就是我们用一个数组记录一下将来的位置，然后直接隔着md为移动就好了，这样可以省去快速幂的复杂度，总复杂度O(n)
K: 作者不会积分待补，抱歉！