当前位置：首页 > news >正文

Codeforces Round #638 (Div. 2) B. Phoenix and Beauty （构造）

news 来源：原创 2024/5/20 22:27:05

传送门

在这里插入图片描述
1.前两天出去玩了，5.1刚回来晚上就打了这场 $c f$ ，三天不做题，如隔千秋。智商都下滑了，这题看懂之后我想写 $s t r i n g$ 直接构造，但是麻烦的是，肯定会出现数组里的数 $x > 10$ ，这怎么 $s t r i n g$ ，我被我自己整吐了

2.正解：我们假设最后得到的序列如下，因为任意 $k$ 长度的子序列的和都相等，那么我们使用尺取/滑动窗口的思路过一下，不难发现，向右滑动一位后，只有 $a [1]$ 被减去，而 $a [k + 1]$ 被加上后和不变，意味着什么—— $a [1] = a [k + 1]$ ，同理我们得到每 $k$ 个数就是一个循环节即可满足题意
在这里插入图片描述
因为题目是在添加的基础上，因此我们首先得到不无重复元素顺序按输入出现的子序列，如果整个初始序列的种类大于了 $k$ 显然无法构造。如果可以，先将刚刚生成的子序列长度添加为 $k$ ，接着对原序列的每个数都输出这样一个序列，长度为 $n * k$

#include <set>
#include <map>
#include <stack>
#include <queue>
#include <math.h>
#include <cstdio>
#include <string>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2e5+10;

int a[maxn];
unordered_map<int,int> mp;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t,n,k;
    cin>>t;
    while(t--){
        cin>>n>>k;
        int sum=0;
        mp.clear();
        vector<int> ans;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(!mp[a[i]]){
                sum++;
                mp[a[i]]=1;
                ans.push_back(a[i]);
            }
        }
        if(sum>k){
            cout<<"-1"<<endl;;
            continue;
        }
        for(int i=1;i<=n;i++)
            if(!mp[i] && sum<k){
                ans.push_back(i);
                sum++;
            }
        cout<<k*n<<endl;
        for(int i=0;i<n*k-1;i++){
            cout<<ans[i%k]<<' ';
        }
        cout<<ans[k-1]<<endl;
    }
    return 0;
}