Codeforces Round #563 (Div. 2)/CF1174
CF1174A Ehab Fails to Be Thanos
其实就是要\(\sum\limits_{i=1}^n a_i\)与\(\sum\limits_{n+1}^{2n}a_i\)差值最大，排一下序就好了
CF1174B Ehab Is an Odd Person
一个显然的结论就是如果至少有一个奇数和一个偶数，那么是可以随意调整的，也就是升序排序
否则不可以进行任何操作
code
CF1174C Ehab and a Special Coloring Problem
与\(x\)互质的数填不同的数，把有向关系表示出来，发现边数是不能承受的
反过来想，成倍数关系填相同的数，把这些数想象成一条链，而这条链开始的数一定是质数，\(\sum\limits_{prime_i}\frac{n}{prime_i}\)是可以承受的
把这条链的点赋一个相同的值
code
CF1174D Ehab and the Expected XOR Problem
求出答案序列的异或前缀和\(sum_i\)，\([l,r]\)子段异或和可表示为\(sum_r\bigoplus sum_{l-1}\)
故转换问题为，填\(sum\)数组，数组内的元素不为\(0\)且互不相同，且两两异或不为\(x\)
预处理\(x\)为多对值，每对值异或起来为\(x\)，显然是两两互不影响的，每对值选择任意一个填就行了
最后还得从\(sum_i=\bigoplus_{j=1}^i a_i\)转换为\(a_i\)
code
CF1174E Ehab and the Expected GCD Problem
先来填第一个数，为了保证\(f(p)\)最大，第一个数分解一下为\(\prod\limits_{p_i}p_i^{k_i}\)使得\(\sum\limits_{k_i}\)最大
显然第一个数为\(2^x3^y\)且\(y≤1\)，否则可以把\(3^2\)换成\(2^3\)，故第一个数最多有两种选择
定义函数\(Cout(x,y)=\frac{n}{2^x3^y}\)为n以内含因子\(2^x3^y\)的个数
设\(f_{i,x,y}\)为填到第\(i\)个数后\(gcd_{j=1}^i a_i=2^x3^y\)的方案数，显然最后的答案为\(f_{n,0,0}\)
code
CF1174F Ehab and the Big Finale
\(x\)为隐藏节点，\(dep_x=d(1,x)\)
\((1)\)：\(u=1\)
\((2)\)：重链剖分，比如\(v\)为\(u\)的重链底部，查询\(dis(x,v)\)的长度，\(y=lca(v,x)\)且在重链上，\(dis(x,v)=dep_v+dep_x-2*dep_y,dep_y=(dep_v+dep_x-dis(x,v))/2\)，则我们可以找到\(y\)
\((3)\)：但\(dep_y=dep_x\)时，\(y\)为答案，退出
\((4)\)：找到\(y\)后，查询\(sec=(y,x)\)上的第二个节点，\(u=sec\)返回\((2)\)
code
