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

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

小红的字符串构造

小红希望你构造一个长度为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
分享
相关文章
【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置
【LeetCode】每日一题&&两数之和&&寻找正序数组的中位数&&找出字符串中第一个匹配项的下标&&在排序数组中查找元素的第一个和最后一个位置
|
4月前
|
巧用二维数组进行编号排序以及创建新数组排序编号和一个杨辉三角的实现
巧用二维数组进行编号排序以及创建新数组排序编号和一个杨辉三角的实现
109 1
|
9月前
44.从键盘输入12个数存入二维数组a[3][4]中,编写程序求出最大元素的值及它所在的行号和列号
44.从键盘输入12个数存入二维数组a[3][4]中,编写程序求出最大元素的值及它所在的行号和列号
125 0
小红的排列构造(dp优化)
小红的排列构造(dp优化)
80 0
Java【代码分享 06】Lamda表达式将List对象中的Map对象的key全部转化为大写或者小写(去除外层循环:可用于Map对象中的key全部转化为大写或者小写)
Java【代码分享 06】Lamda表达式将List对象中的Map对象的key全部转化为大写或者小写(去除外层循环:可用于Map对象中的key全部转化为大写或者小写)
396 0
|
9月前
Qsort函数实现对各类型数组中元素的排序(思路简单)
Qsort函数实现对各类型数组中元素的排序(思路简单)
数组与字符串的关系【了解一下】
数组与字符串的关系【了解一下】
137 0
【每日一题Day66】LC1754构造字典序最大的合并字符串 | 贪心 双指针模拟
思路:双指针遍历两个字符串,贪心比较字符的字典顺序,并添加至结果集
85 0
【每日一题Day66】LC1754构造字典序最大的合并字符串 | 贪心 双指针模拟
【C/C++】用指针方法对10个整数按由大到小顺序排序
##下面我们将对21 12 45 43 87 897 534 67 90 75这10个数,用下面的程序进行由大到小排序。
504 0
【C/C++】用指针方法对10个整数按由大到小顺序排序
【构造】构造一个字符串满足k个子序列问题总结
【构造】构造一个字符串满足k个子序列问题总结
【构造】构造一个字符串满足k个子序列问题总结