Codeforces Round #638 (Div. 2) B. Phoenix and Beauty(构造/思维)
2022/8/22 23:23:11
本文主要是介绍Codeforces Round #638 (Div. 2) B. Phoenix and Beauty(构造/思维),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
https://codeforces.com/contest/1348/problem/B
如果一个数组的所有长度为k的子数组的和相同,那么这个数组就是美丽的。数组的子数组是任何连续元素的序列。 Phoenix目前有一个长度为n的数组a。他想在数组中插入一些整数,可能是零个,这样数组就变得漂亮了。 插入的整数必须介于1和n之间,包括1和n。整数可以被插入任何地方(甚至在第一个元素之前或最后一个元素之后)。 他并没有试图最小化插入的整数的数量(个数随便)。 无论怎么插都不能为美丽数组,就输出-1。
input 4 4 2 1 2 2 1 4 3 1 2 2 1 3 2 1 2 3 4 4 4 3 4 2 output 5 1 2 1 2 1 4 1 2 2 1 -1 7 4 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的情况
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> 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<int> s; for(int i=1;i<=n;i++) { cin>>a[i]; s.insert(a[i]); } //只有当k小于s的个数的时候,就要输出-1,因为凑不出那么多 if(k<s.size()) cout<<"-1"<<endl; else { //n个数,每个都按照k个来一遍(k个为一轮) cout<<n*k<<endl; for(int i=0;i<n;i++) { for(int x:s) cout<<x<<" "; for(int j=0;j<k-s.size();j++)//不足k的数字可以用任意相同的数字填充 cout<<"1"<<" "; } cout<<endl; } } return 0; }
这篇关于Codeforces Round #638 (Div. 2) B. Phoenix and Beauty(构造/思维)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-04安装 VPrix Desktop 的系统要求-icode9专业技术文章分享
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享