C
题面
输出标准输出
凤凰网喜欢美丽的数组。如果一个数组中所有长度为k的子数组
的子数都有相同的总和，那么这个数组就是美丽的。一个数组的子数组是任何连续元素的序列。
凤凰网目前有一个数组a
的长度为n
. 他想在他的数组中插入一些整数，可能是零，这样它··就会变得很漂亮。插入的整数必须是在1
和n
包括在内。整数可以插入任何地方（甚至在第一个或最后一个元素之前或之后），而且他并不是要尽量减少插入的整数的数量。
输入
输入由多个测试案例组成。第一行包含一个整数t
(1≤t≤50
)–测试用例的数量。
每个测试用例的第一行包含两个整数n
和k
(1≤k≤n≤100
).
每个测试用例的第二行包含n
空间分隔的整数（1≤ai≤n
)–Phoenix当前拥有的数组。这个数组可能是也可能不是已经很美。
输出
对于每个测试案例，如果不可能创建一个漂亮的数组，则打印-1。否则，打印两行。
第一行应该包含美丽数组的长度m
(n≤m≤104
). 你不需要最小化m
.
第二行应该包含m
空间分隔的整数（1≤bi≤n
)–这是一个美丽的数组，Phoenix将一些可能为零的整数插入他的数组a后可以得到。
. 你可以打印原本不在数组a中的整数
.
如果有多个解决方案，就打印任何一个。可以保证，如果我们能使数组a
美丽，我们总能使它的结果长度不超过104
.
例子
InputCopy
4
4 2
1 2 2 1
4 3
1 2 2 1
3 2
1 2 3
4 4
4 3 4 2
输出拷贝
5
1 2 1 2 1
4
1 2 2 1
-1
7
4 3 2 1 4 3 2
注意
在第一个测试案例中，我们可以通过插入整数1来使数组a
通过在索引3处插入整数1
在索引3处
(在现有的两个2之间)
s). 现在，所有长度为k=2的子数组
都有相同的和 3
. 存在许多其他可能的解决方案，例如：
2,1,2,1,2,1
1,2,1,2,1,2
在第二个测试案例中，数组已经非常漂亮：所有长度为k=3的子数组
都有相同的和 5
.
在第三个测试案例中，我们可以证明，我们不能插入数字来使数组a
美丽。
在第四个测试案例中，数组b
是美丽的，所有长度为k=4的子数组
的所有子数都有相同的和 10
. 也存在着其他的解决方案。
代码
CodeForces - 1348B Phoenix and Beauty（思维+题干细节）_zaiyang遇见的博客-CSDN博客
见代码问号注释
#include<bits/stdc++.h> using namespace std; const int N=110; int f[N],vis[N],c[N]; *** int main() { int T; cin>>T; while(T--) { memset(f,0,sizeof f); memset(vis,0,sizeof vis); memset(c,0,sizeof c); *** int n,k,S=0; 多组输入初始化 cin>>n>>k; 数组长，漂亮长 for(int i=1;i<=n;i++) { cin>>f[i]; if(vis[f[i]]==0) { vis[f[i]]=1; c[++S]=f[i]; } } 读入并记录原数组数据和数据是否出现。 记录数组数据种类，并存入c *** if(S>k){ cout<<-1<<endl; 种类大于k则不能构造漂亮 因为每个k长度的连续序列里的总和相同的话，必定是要每个k区间元素都具有相同的种类与排列 } *** else{ 否则： for(int i=S+1;i<=k;i++) c[i]=c[i-1]; *** for(int i=k+1;i<=9999;i++) 需要构造n*k个这样的连续序列。 ？？？？？？？？？？？？？？？？？？？？？？？？ 似乎是因为存在一些排列与要构造k排列不同的子区间，而且又不能打乱n的排列，所以假定最坏情况下每次构造只能满足其中一个元素的排列，这样要构造n-k次。 c[i]=c[i-k]; 距离为k+1 cout<<9999<<endl; *** for(int i=1;i<=9999;i++) cout<<c[i]<<" "; cout<<endl; } 不够k的部分，随便补，可以补成一样的数。 大于k的部分，变成和k一样的序列 只要具有相同的长度为k的排列，就可以满足题意， 突然发现可以用双指针滑动窗口来理解这个题 因为以k长度的滑动窗口移动时，k少掉了哪个元素，就会新增哪个元素。 最后输出。 看到k长度没有提取出双指针滑动窗口套路，不太熟练，要再去加深印象 } return 0; }
考验代码
4：30
4：00
4：00
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1e4 + 10; int vis[N],f[N],c[N]; int main(){ int T; cin >> T; while(T--){ memset(vis,0,sizeof vis); int n,k,siz = 0; cin >> n >> k; for(int i = 1;i <= n;i++){ cin >> f[i]; if(!vis[f[i]]){ vis[f[i]] = true; c[++siz] = f[i]; } } if(siz > k){ cout << -1 << endl; } else{ for(int i = siz + 1;i <= k;i++){ c[i] = 1; } for(int i = k+1;i <= n *k;i++){ c[i] = c[i-k]; } cout << n*k << " " ; for(int i = 1;i <= n*k;i++){ cout << c[i] << " " ; } cout << endl; } } return 0; }
套路：双指针滑动窗口的构造。
前提条件：维护一个长度为k的连续区间，连续子数组，连续时间段，相邻位置的信息
包括：总和：排列：种类：最值：
情景：
如果一个帖子曾在任意一个长度为D的时间段内收到了不少于k个赞，小明就认为这个贴子曾经是“热帖”
还有最近做的：
凤凰网喜欢美丽的数组。如果一个数组中所有长度为k的子数组的子数都有相同的总和那么这个数组就是美丽的。一个数组的子数组是任何连续元素的序列。 一个数组的子数组是任何连续元素的序列。
维护连续区间的信息，为什么不用线段树？
因为题目的要求是构造一个信息满足某种要求的序列，而不是求序列信息。
