2020牛客暑期多校训练营（第三场）题解
写一下一些作者掌握的题的题解，其他会慢慢补
A: Clam and Fish
这题是一道贪心，我们发现我们要最优策略
就是有鱼我们就钓鱼，反之如果最后有多余的蛤蜊，我们可以花一半的时间用来更优的策略，注意要下取整
算是一道基础题吧！
B: Classical String Problem
一道不易让我们思维定向的题，我们容易往平衡树treap上想
然后发现倍长一下当前的字符串然后用一个指针维护当前所在，然后我们的移动字符可以转化为指针的移动
其实这题的妙处在于字符的相对位置就是那个带绝对值的位置其实不会彼此发生变化，因此我们可以这么理解！
C: Operation Love
这个idea有点类似于AI智能
我们首先发现这个手的图形能够旋转，这不太方便我们的处理
但是我们可以发现最长的边周围两边的长度不同，因此我们只需要根据两边的长度来判断一下这个顺序就行了！
具体我们只需要找到最长边，然后把周围的两个判断一下即可，我们可以采用倍长的技巧，可以减免一些细节，类似于B
然后其实我们也可以用dreamoon说的做外积的方法！
需要注意的是我们有一个精度的eps的范围，这里不能太小，只需要大概满足准确值即可，大概1e5~1e6就可以！
(这题现在要求的可能比较友好，但是这题引出的一些思路还包括一个多边形判断相等，还有判断相似以及旋转的度数，可以给我们来当做加强版，可以引申思考）
D: Points Construction Problem
这道题可以利用等周定理，但是我们可以发现这个周长其实可以利用我们的小学奥数的知识来拼接割补即可
然后我们就可以采用普通构造题的思路，只需要有一个上下界然后卡一下就可以了！
注意如果是奇数我们直接叉掉就好了！
这里标算思路可能略显复杂，因为如果我们要不断移动的构造，产生的差可能有很多细节，但是用上述直接构造可能是一个不错的写法，类似于一道不记得题号的CF题，构造二叉树的那道
E: Two Matchings
我们要构造出两种最优匹配，我们考虑如果只有一种该如何处理
我们注意这个n是偶数，直接1-2 3-4，...这么顺次连下去就可以了
然后另外一组我们可以也类似与如此构造
可以拆开算贡献可能更好理解，然后我们就可以轻松的发现另一种的结论，就是4,6的环是最优的，再大的可以把它拆掉成4,6的达到更优
于是我们就可以简单的dp了！
（注意因为这里的n有可能不是4的倍数，所以要用到6这个长度的环）
F: Fraction Construction Problem
这题作者考试的时候通过某种奇怪的找规律方法得到了结论，但是并不太会证明！
就是我们考虑分解这个数以后总是能找到解的，反之无解
然后我们发现这个分解这个数只要找到两个互质的是等价的，然后结论码完就行了，注意有点细节！
刚开始要判断很多东西，这题的证明可能还是类似于一道CF题，这里dreamoon具体有讲，就不放了见谅！
提示：拆分构造和gcd有关的我们可以向互质的思路上想想
G: Operating on a Graph
一开始想到了启发式合并，然后听了题解感觉好像用链表合并就可以了！
首先不同颜色的边会合并，但是这些边只有m条，然后我们最多就只会合并这么多次
于是我们启发式合并就可以做到一个log个
但是我们考虑如果直接用链表相当于把图的形态按照题目的要求模拟重构可以达到一个不要log的级别
然后我们链式前向星或者list建图也好都可以直接用一个链表的头接到另一个的尾端就好了！
（这个思路我们可以和线段树合并进行类比更好理解，线段树合并其实也是一共nlogV个节点，然后每次都是线性合并的，所以保持了这样的复杂度）
然后这里有list神奇的stl操作，还有容器的赋值最好swap，是O(1)的，所以放一下代码：
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N=8e5+5;
int n,m,q,fa[N];list<int>e[N],s;
int find(int u){return fa[u]==u?u:fa[u]=find(fa[u]);}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)fa[i]=i,e[i].clear();
for(int i=1,u,v;i<=m;i++)scanf("%d%d",&u,&v),e[u].pb(v),e[v].pb(u);
scanf("%d",&q);
while(q--){
int u;scanf("%d",&u);
if(find(u)!=u)continue;
s.clear();
for(auto v:e[u]){
int f=find(v);
if(f!=u)fa[f]=u,s.splice(s.end(),e[f]);
}
swap(s,e[u]);
}
for(int i=0;i<n;i++)printf("%d%c",find(i)," \n"[i==n-1]);
}
return 0;
}L: Problem L is the Only Lovely Problem
签到题，基本字符串+判断就好了，注意审题看到大小写！
字节跳动公司福利 526人发布