C

題面

Problem - 1348B - Codeforces
輸出標(biāo)準(zhǔn)輸出
鳳凰網(wǎng)喜歡美麗的數(shù)組。如果一個(gè)數(shù)組中所有長(zhǎng)度為k的子數(shù)組
的子數(shù)都有相同的總和，那么這個(gè)數(shù)組就是美麗的。一個(gè)數(shù)組的子數(shù)組是任何連續(xù)元素的序列。

鳳凰網(wǎng)目前有一個(gè)數(shù)組a
的長(zhǎng)度為n
. 他想在他的數(shù)組中插入一些整數(shù)，可能是零，這樣它··就會(huì)變得很漂亮。插入的整數(shù)必須是在1
和n
包括在內(nèi)。整數(shù)可以插入任何地方（甚至在第一個(gè)或最后一個(gè)元素之前或之后），而且他并不是要盡量減少插入的整數(shù)的數(shù)量。

輸入
輸入由多個(gè)測(cè)試案例組成。第一行包含一個(gè)整數(shù)t
(1≤t≤50
)–測(cè)試用例的數(shù)量。

每個(gè)測(cè)試用例的第一行包含兩個(gè)整數(shù)n
和k
(1≤k≤n≤100
).

每個(gè)測(cè)試用例的第二行包含n
空間分隔的整數(shù)（1≤ai≤n
)–Phoenix當(dāng)前擁有的數(shù)組。這個(gè)數(shù)組可能是也可能不是已經(jīng)很美。

輸出
對(duì)于每個(gè)測(cè)試案例，如果不可能創(chuàng)建一個(gè)漂亮的數(shù)組，則打印-1。否則，打印兩行。

第一行應(yīng)該包含美麗數(shù)組的長(zhǎng)度m
(n≤m≤104
). 你不需要最小化m
.

第二行應(yīng)該包含m
空間分隔的整數(shù)（1≤bi≤n
)–這是一個(gè)美麗的數(shù)組，Phoenix將一些可能為零的整數(shù)插入他的數(shù)組a后可以得到。
. 你可以打印原本不在數(shù)組a中的整數(shù)
.

如果有多個(gè)解決方案，就打印任何一個(gè)?？梢员ＷC，如果我們能使數(shù)組a
美麗，我們總能使它的結(jié)果長(zhǎng)度不超過(guò)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
注意
在第一個(gè)測(cè)試案例中，我們可以通過(guò)插入整數(shù)1來(lái)使數(shù)組a
通過(guò)在索引3處插入整數(shù)1
在索引3處
(在現(xiàn)有的兩個(gè)2之間)
s). 現(xiàn)在，所有長(zhǎng)度為k=2的子數(shù)組
都有相同的和 3
. 存在許多其他可能的解決方案，例如：

2,1,2,1,2,1
1,2,1,2,1,2
在第二個(gè)測(cè)試案例中，數(shù)組已經(jīng)非常漂亮：所有長(zhǎng)度為k=3的子數(shù)組
都有相同的和 5
.

在第三個(gè)測(cè)試案例中，我們可以證明，我們不能插入數(shù)字來(lái)使數(shù)組a
美麗。

在第四個(gè)測(cè)試案例中，數(shù)組b
是美麗的，所有長(zhǎng)度為k=4的子數(shù)組
的所有子數(shù)都有相同的和 10
. 也存在著其他的解決方案。

代碼

CodeForces - 1348B Phoenix and Beauty（思維+題干細(xì)節(jié)）_zaiyang遇見(jiàn)的博客-CSDN博客
見(jiàn)代碼問(wèn)號(hào)注釋

#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;數(shù)組長(zhǎng)，漂亮長(zhǎng)for(int i=1;i<=n;i++){cin>>f[i];if(vis[f[i]]==0){vis[f[i]]=1;c[++S]=f[i];}}讀入并記錄原數(shù)組數(shù)據(jù)和數(shù)據(jù)是否出現(xiàn)。記錄數(shù)組數(shù)據(jù)種類，并存入c***if(S>k){cout<<-1<<endl;種類大于k則不能構(gòu)造漂亮因?yàn)槊總€(gè)k長(zhǎng)度的連續(xù)序列里的總和相同的話，必定是要每個(gè)k區(qū)間元素都具有相同的種類與排列}***else{否則：for(int i=S+1;i<=k;i++)c[i]=c[i-1];***for(int i=k+1;i<=9999;i++)需要構(gòu)造n*k個(gè)這樣的連續(xù)序列。？？？？？？？？？？？？？？？？？？？？？？？？似乎是因?yàn)榇嬖谝恍┡帕信c要構(gòu)造k排列不同的子區(qū)間，而且又不能打亂n的排列，所以假定最壞情況下每次構(gòu)造只能滿足其中一個(gè)元素的排列，這樣要構(gòu)造n-k次。c[i]=c[i-k];距離為k+1cout<<9999<<endl;***for(int i=1;i<=9999;i++)cout<<c[i]<<" ";cout<<endl;}不夠k的部分，隨便補(bǔ)，可以補(bǔ)成一樣的數(shù)。大于k的部分，變成和k一樣的序列只要具有相同的長(zhǎng)度為k的排列，就可以滿足題意，突然發(fā)現(xiàn)可以用雙指針滑動(dòng)窗口來(lái)理解這個(gè)題因?yàn)橐詋長(zhǎng)度的滑動(dòng)窗口移動(dòng)時(shí)，k少掉了哪個(gè)元素，就會(huì)新增哪個(gè)元素。最后輸出?？吹絢長(zhǎng)度沒(méi)有提取出雙指針滑動(dòng)窗口套路，不太熟練，要再去加深印象}return 0;
}

考驗(yàn)代碼

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;
}

套路：雙指針滑動(dòng)窗口的構(gòu)造。

前提條件：固定長(zhǎng)度的連續(xù)區(qū)間

雙指針滑動(dòng)窗口特殊性在于每次移動(dòng)會(huì)少一個(gè)元素，會(huì)多一個(gè)元素，
要讓總和相同，少掉的元素必須等于新增的元素。

所以如果原數(shù)組中即將進(jìn)入滑動(dòng)窗口的元素不等于少掉的元素時(shí)，
就要插入一個(gè)與少掉的元素相等的數(shù)作為新增的元素。
一直插入直到原數(shù)組中每個(gè)元素都進(jìn)入了滑動(dòng)窗口。