Codeforces Round #563 (Div. 2)/CF1174

首页 > Codeforces Round #563 (Div. 2)/CF1174

CF1174A Ehab Fails to Be Thanos

其实就是要(sumlimits_{i=1}^n a_i)与(sumlimits_{n+1}^{2n}a_i)差值最大，排一下序就好了

一个显然的结论就是如果至少有一个奇数和一个偶数，那么是可以随意调整的，也就是升序排序

否则不可以进行任何操作

code

与(x)互质的数填不同的数，把有向关系表示出来，发现边数是不能承受的

反过来想，成倍数关系填相同的数，把这些数想象成一条链，而这条链开始的数一定是质数，(sumlimits_{prime_i}frac{n}{prime_i})是可以承受的

把这条链的点赋一个相同的值

code

求出答案序列的异或前缀和(sum_i)，([l,r])子段异或和可表示为(sum_rigoplus sum_{l-1})

故转换问题为，填(sum)数组，数组内的元素不为(0)且互不相同，且两两异或不为(x)

预处理(x)为多对值，每对值异或起来为(x)，显然是两两互不影响的，每对值选择任意一个填就行了

最后还得从(sum_i=igoplus_{j=1}^i a_i)转换为(a_i)

code

先来填第一个数，为了保证(f(p))最大，第一个数分解一下为(prodlimits_{p_i}p_i^{k_i})使得(sumlimits_{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

(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

转载于:https://www.cnblogs.com/y2823774827y/p/10972640.html