cf1348B phoenix and beauty(双指针滑动窗口)

简介: 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+1
            cout<<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;
}

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

前提条件:维护一个长度为k的连续区间,连续子数组,连续时间段,相邻位置的信息

包括:总和:排列:种类:最值:

情景:

如果一个帖子曾在任意一个长度为D的时间段内收到了不少于k个赞,小明就认为这个贴子曾经是“热帖”


还有最近做的:

凤凰网喜欢美丽的数组。如果一个数组中所有长度为k的子数组的子数都有相同的总和那么这个数组就是美丽的。一个数组的子数组是任何连续元素的序列。 一个数组的子数组是任何连续元素的序列。

维护连续区间的信息,为什么不用线段树?

因为题目的要求是构造一个信息满足某种要求的序列,而不是求序列信息。

目录
相关文章
|
2天前
|
存储 算法
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
LeetCode刷题---209. 长度最小的子数组(双指针-滑动窗口)
|
2天前
|
算法 容器 NoSQL
双指针扫描、滑动窗口
双指针扫描、滑动窗口
|
2天前
|
索引
LeetCode438题(无敌双指针——滑动窗口)
LeetCode438题(无敌双指针——滑动窗口)
|
2天前
|
存储
【Leetcode 209】长度最小的子数组 —— 滑动窗口|双指针
我们可以使用双指针解决本题,定义两个指针 i 和 j 分别表示子数组(滑动窗口窗口)的开始位置和结束位置,维护变量 sum 存储子数组中的元素和。每一轮迭代中,每当 sum >= target 则记录子数组最小长度,移动慢指针。在每一轮迭代最后,移动快指针
(双指针滑动窗口)AcWing 1238. 日志统计
(双指针滑动窗口)AcWing 1238. 日志统计
62 0
|
机器学习/深度学习
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(四)
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(四)
|
存储 算法
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(三)
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(三)
|
人工智能
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(二)
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(二)
|
算法 索引
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(一)
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟
<代码随想录二刷>二分查找 | 双指针 | 滑动窗口 | 枚举模拟(一)
|
容器
双指针之滑动窗口(长度最小的子数组 和 和为s的连续正数序列)
双指针之滑动窗口(长度最小的子数组 和 和为s的连续正数序列)
95 0

热门文章

最新文章