小红的字符串构造和小红的排列构造

简介: 小红的字符串构造和小红的排列构造

小红的字符串构造

小红希望你构造一个长度为nnn的、仅包含小写字母的字符串,其中恰好有kkk个长度大于1的回文子串。你能帮帮她吗?输入两个整数n,k,用空格隔开。 1≤n≤10^5,0≤k≤n/2.一个字符串。如果有多解输出任意即可。 可以证明,一定存在至少一个合法解。

#include<iostream>
#include<string.h>
using namespace std;
const int N = 1e6+6;
typedef long long ll;
ll n , k;
string s;
int main()
{
  cin >> n >> k;
    char c = 'a';
    for(int i=0;i<k;i++)
    {
        s += c;
        s += c;
        c ++;
        if(c > 'z') c = 'a';
    }
    while(s.size() < n)
    {
        s += c;
        c ++;
        if(c > 'z') c = 'a';
    }
    cout << s;
    return 0;
}

小红的排列构造

定义两个数组a和b的汉明距离为:有多少个下标iii满足ai≠bi。例如,[2,3,1]和[1,3,1]的汉明距离是1。现在小红拿到了一个长度为n的排列p,她希望你构造一个长度为n的排列q,满足p和q的汉明距离恰好等于k。排列指长度为n的数组,其中1到n每个元素恰好出现了一次。第一行输入两个正整数n,k,代表排列p的长度,以及构造后的q和p的汉明距离。 第二行输入n个正整数pi,代表小红拿到的排列。 1≤n,k≤10^5,1≤ai≤n;如果无解,请输出-1。 否则输出n个正整数qi,代表小红构造的排列。

#include<iostream>
using namespace std;
const int N=1e5+5;
typedef long long ll;
int a[N];
int main()
{
  int n,k;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  if(k>n||k==1)
        cout<<"-1\n";
  else{
    for(int i=0;i<k-1;i+=2){
      swap(a[i],a[i+1]);
    }
    if(k%2) 
            swap(a[k-1],a[0]);
    for(int i=0;i<n;i++){
      cout<<a[i]<<" \n"[i==n-1];
    }
  }
  return 0;
}

执行交换操作

for(int i=0;i<k-1;i+=2){
swap(a[i],a[i+1]);
}
if(k%2)
swap(a[k-1],a[0]);

对于 k 的每个偶数索引(从0开始),与其下一个索引(即奇数索引)进行交换。例如,如果 k=4,则交换 a[0]a[1],然后交换 a[2]a[3]

如果 k 是奇数,则额外交换 a[k-1]a[0]

目录
打赏
0
1
1
0
26
分享
相关文章
一文带你通俗理解23种软件设计模式(推荐收藏,适合小白学习,附带C++例程完整源码)
一文带你通俗理解23种软件设计模式(推荐收藏,适合小白学习,附带C++例程完整源码)
1333 0
卸载时报错:“系统找不到指定的驱动器”问题处理
【10月更文挑战第5天】文档介绍了分析“系统找不到指定的驱动器”错误的原因及解决方法。此错误多因外部设备移除、网络驱动器断开或软件卸载程序缺陷引起。解决策略包括检查外部设备连接、更新驱动器盘符、使用第三方卸载工具以及手动清理注册表和文件系统。
2920 3
《池化技术:深度学习热点背后的神秘力量,探寻最大池化与平均池化如何引领图像革命》
【8月更文挑战第21天】池化技术是深度学习中关键的特征提取手段,通过下采样减少数据维度和计算量,同时保持核心特征。主要分为最大池化和平均池化:前者选取局部区域的最大值,保留显著特征并具平移不变性;后者计算区域平均值,平滑噪声并稳定输出。两者依据任务需求选择,如图像分类偏好最大池化以突出关键特征,而去噪任务则倾向平均池化以平滑图像。
181 0
day28:Java零基础 - 进制转换
【7月更文挑战第28天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
139 6
为什么MySQL索引使用B+树而不用hash表和B树
支持范围查询:B+树索引在数据结构上有序排列,可以有效支持范围查询,例如大于、小于、区间查询等操作。而哈希表无法支持范围查询,只能进行精确查找,而B树在范围查询操作时性能相对较低。
521 0
查看NodeJs版本和查看NPM版本
查看NodeJs版本和查看NPM版本
434 0
查看NodeJs版本和查看NPM版本
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等