cf1348B phoenix and beauty(双指针滑动窗口的构造）

C

题面

Problem - 1348B - Codeforces
输出标准输出
凤凰网喜欢美丽的数组。如果一个数组中所有长度为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+1cout<<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;
}

套路：双指针滑动窗口的构造。

前提条件：固定长度的连续区间

双指针滑动窗口特殊性在于每次移动会少一个元素，会多一个元素，
要让总和相同，少掉的元素必须等于新增的元素。

所以如果原数组中即将进入滑动窗口的元素不等于少掉的元素时，
就要插入一个与少掉的元素相等的数作为新增的元素。
一直插入直到原数组中每个元素都进入了滑动窗口。