1615 H

最优化问题常见方法，构造一个下界，尝试构造一个方案达到下界

构造下界

我们定义\((u,v)\)为所有\(u\)可以到\(v\)的点对，直接相邻或者间接相邻都可以

假设存在有一个点对\((u,v)\)，那么答案至少为\(a_u-a_v\)

更一般的，如果对于k个点对\((u_i,v_i)\)，满足一个数字在集合\((U∪V)\)中只出现了一次

那么答案至少为\(\sum a_{u_i}-a_{v_i}\)

找到这个最大的和即为下界

这个过程很简单，对于原图的\((u,v)\)，建立\((inf,a_u-a_v)\)的边

然后对于每一个点\(u\),\(S\)与\(u\)和\(u\)与\(T\)建立\((1,0)\)的边，跑最大费用流即可

最后，如果\(u\)同时与S和T的边都满流了，把他设定为不满流，显然这样不会影响费用

这样处理之后，每一个点要么和\(S\)满流，要么和\(T\)满流，即至多出现一次

在残留网络中，即如果还有流量就保留，包括反向边，对S跑出到所有节点的最长路\(d_u\)

我们令\(b_u=a_u+d_u\)为答案

对于原来的一个限制点对\((u,v)\)，因为原本的边流量为inf，故必存在与残留网络中，即有\(d_u+(a_u-a_v)\le d_v\)，即\(b_u=d_u+a_u\le d_v+a_v=b_v\)，符合条件

但同时，对于我们选中的点对\((u,v)\)，反向边有流量，同理可得\(b_v\le b_u\)。

同时，因为\(u\)在残留网络中与\(t\)连通，故必不可能有\(d_u>0\)，否则找到一条增广路

同理有\(d_v\)不可能小于\(0\)

故得到\(a_v\le b_v=b_u\le a_u\)

不难发现，对于一个选中的点对，调整力度恰好就是\(a_u-a_v\)

对于一个没有选中的点，有\(d_u=0\)，证明同上

故恰好与所需的下界相同

不妨令\(f(x)\)为消完因子之后的答案，即消完平方因子之后的数

显然有\(f(xy)=f(f(x)f(y))\)

\(f(n!(n+1)!)=f(n+1)\)

对于偶数\(2k\)，\(f(1!2!3!...(2k)!)=f(2*4*8*...*2k)=f(2^k*k!)\)

若\(k\)为偶数，则只去掉\(k\)就可以是一个合法方案

若k为奇数，去掉\(k\)和\(2\)就是一个合法的方案

故对于偶数，只需要删掉不超过2个数

奇数因为通过删掉\(n\)就可以变为偶数，故答案不超过\(3\)

故对于所有的数删掉的数不超过\(3\)个

对于所有质数随机一个大数\(p(x)\)，然后\(p(xy)=p(x) \ xor\ p(y)\)

一个数为平方数，显然有\(p(x)=0\)

故得到做法，先判一下全选，然后尝试删掉一个，然后尝试删掉两个，最后尝试三个，一定能找到一组解