CodeforcesRound#708
unrated
C. k-LCM
比较有意思的构造题，题意是给定n和k，要求构造出一个长度为k的数组，满足
- $a_1+a_2+…+a_k=n$
- $LCM(a_1,a_2,…,a_k)\le\frac{n}{2}$
然后分成两个小问，easy给定k=3，hard中$k\in[3,n]$
实际上easy是在给提示，对于k=3的情况，只需要分以下几类
- 奇数，拆成$1,\frac{n-1}{2},\frac{n-1}{2}$
- 偶数，被4整除，拆成$\frac{n}{4},\frac{n}{4},\frac{n}{2}$
- 偶数，不被4整除（模4余2），拆成$2,\frac{n-2}{2},\frac{n-2}{2}$
然后其实hard也做完了，因为只要先给k-3个1，然后对n-k+3做第一小问就做完了
但是如果跳过easy直接看hard应该会困难很多
D. Genius
把问题转化成一张图，$(i,j)$的边权为$c_i-c_j$，根据二进制理论可以发现每条边权唯一，而且每种方案的顺序一定按照边权从小到大进行，于是可以根据边权从小到大考虑问题，用$dp[i]$表示最后走到$i$这个点时最大的答案，那么按照从小到大的顺序考虑边，逐条做松弛操作就可以求解了
E. Square-free division
题意是这样，给出n个数，问最少分成连续的几段，使得段内任意两个数的乘积不是完全平方数
一样是拆成easy和hard两道题，hard版本的区别在于可以修改k个数(k<=20)
首先考虑什么样的两个数乘积会是完全平方数，完全平方数拆成质因数乘积后，每个质因数的幂次一定是偶数，所以对于每个数，只要质因数分解，然后记录幂次的奇偶性就可以了，用$val[x]$记录转化后的结果，然后如果两个数a,b能乘起来是完全平方数，一定有$val[a]=val[b]$
对于easy只要从头到尾扫一遍，遇到冲突的就ans++然后清空就行了
hard就在此基础上变成了一个dp题，可以认为一定能修改成一个不会产生任何影响的数（因为可供修改的数一定是大于n的），可以把修改看成删除操作。
接着预处理一个$l[n][k]$，表示对于第n个数，在删除了k个数的情况下，包含第n个数的连续段的最左位置，这玩意可以$O(nk)$维护，因为$l[n]$是在$l[n-1]$的基础上，插入一个$prev[n]$（上一个和n一样的数的位置），再排序就可以得到
然后可以$O(nk^2)$维护$dp[n][k]$表示考虑前n位，修改k个数的答案，枚举最后一个连续段所修改的数的个数即可。