小红的字符串构造
小红希望你构造一个长度为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]。
