网站建设加微信,wordpress系统付费,网页制作视频教程优质课,深圳规模较大的网站建设公司C
题面
Problem - 1348B - Codeforces 输出标准输出 凤凰网喜欢美丽的数组。如果一个数组中所有长度为k的子数组 的子数都有相同的总和#xff0c;那么这个数组就是美丽的。一个数组的子数组是任何连续元素的序列。
凤凰网目前有一个数组a 的长度为n . 他想在他的数组中插入…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). 现在所有长度为k2的子数组 都有相同的和 3 . 存在许多其他可能的解决方案例如
2,1,2,1,2,1 1,2,1,2,1,2 在第二个测试案例中数组已经非常漂亮所有长度为k3的子数组 都有相同的和 5 .
在第三个测试案例中我们可以证明我们不能插入数字来使数组a 美丽。
在第四个测试案例中数组b 是美丽的所有长度为k4的子数组 的所有子数都有相同的和 10 . 也存在着其他的解决方案。
代码
CodeForces - 1348B Phoenix and Beauty思维题干细节_zaiyang遇见的博客-CSDN博客 见代码问号注释
#includebits/stdc.h
using namespace std;
const int N110;
int f[N],vis[N],c[N];
***
int main()
{int T;cinT;while(T--){memset(f,0,sizeof f);memset(vis,0,sizeof vis);memset(c,0,sizeof c);***int n,k,S0;多组输入初始化cinnk;数组长漂亮长for(int i1;in;i){cinf[i];if(vis[f[i]]0){vis[f[i]]1;c[S]f[i];}}读入并记录原数组数据和数据是否出现。记录数组数据种类并存入c***if(Sk){cout-1endl;种类大于k则不能构造漂亮因为每个k长度的连续序列里的总和相同的话必定是要每个k区间元素都具有相同的种类与排列}***else{否则for(int iS1;ik;i)c[i]c[i-1];***for(int ik1;i9999;i)需要构造n*k个这样的连续序列。似乎是因为存在一些排列与要构造k排列不同的子区间而且又不能打乱n的排列所以假定最坏情况下每次构造只能满足其中一个元素的排列这样要构造n-k次。c[i]c[i-k];距离为k1cout9999endl;***for(int i1;i9999;i)coutc[i] ;coutendl;}不够k的部分随便补可以补成一样的数。大于k的部分变成和k一样的序列只要具有相同的长度为k的排列就可以满足题意突然发现可以用双指针滑动窗口来理解这个题因为以k长度的滑动窗口移动时k少掉了哪个元素就会新增哪个元素。最后输出。看到k长度没有提取出双指针滑动窗口套路不太熟练要再去加深印象}return 0;
}
考验代码
430 400 400
#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 k1;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;
}套路双指针滑动窗口的构造。
前提条件固定长度的连续区间
双指针滑动窗口特殊性在于每次移动会少一个元素会多一个元素 要让总和相同少掉的元素必须等于新增的元素。
所以如果原数组中即将进入滑动窗口的元素不等于少掉的元素时 就要插入一个与少掉的元素相等的数作为新增的元素。 一直插入直到原数组中每个元素都进入了滑动窗口。
