Codeforces Round 638 (Div. 2) B. 凤凰与美丽（构造/思维）

文章Codeforces Round #638 (Div. 2) B. Phoenix and Beauty（构造/思维），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

://codeforces.com/contest/1348/problem/B

如果一个数组的所有长度为k的子数组的和相同，那么这个数组就是美丽的。数组的子数组是任何连续元素的序列。Phoenix目前有一个长度为n的数组a。他想在数组中插入一些整数，可能是零个，这样数组就变得漂亮了。插入的整数必须介于1和n之间，包括1和n。整数可以被插入任何地方(甚至在第一个元素之前或最后一个元素之后)。他并没有试图最小化插入的整数的数量（个数随便）。无论怎么插都不能为美丽数组，就输出-1。

input44 21 2 2 14 31 2 2 13 21 2 34 44 3 4 2output51 2 1 2 141 2 2 1-174 3 2 1 4 3 2

这种插入个数随便但是又要求我们输出总值的题目，九成是个定值，该值肯定跟给定数字有关
我们可以想到：它既然在每k个范围内都要是定值，所以我们可以在每1个值里面都凑出k个值来，这样总个数就变成了n*k个

我们需要每k个的值都相等，那么a[1]=a[k+1], a[2]=a[k+2]...其实也就是k个k个都是一样的值。

这样我们就可以把数组中有的去重后依次插入每k个之间，如果不够的话，取任意值作为替补
与此同时我们就可以发现，一旦数组中去重后的个数都会大于k个，那么必定在k个里面容不下多余的，所以就会产生-1的情况

#includeusing namespace std;typedef long long LL;typedef pair PII;const int N=200200,M=2002;int a[N];int main(){    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);    int T=1;    cin>>T;    while(T--)    {        int n,k;        cin>>n>>k;        set s;        for(int i=1;i<=n;i++)        {            cin>>a[i];            s.insert(a[i]);        }        //只有当k小于s的个数的时候，就要输出-1，因为凑不出那么多        if(k