[Daimayuan] 子串的循环挪动(C++,模拟)
给出一个字符串 sss,你需要执行 mmm 个任务。每个任务给出两个下标 li,ril_i,r_ili,ri 和一个整数 kik_iki(字符串的下标从 111 开始),表示你需要循环挪动 sss 的子串 s[li...ri]kis[l_i...r_i]\\ k_is[li...ri] ki 次。请从前到后依次执行给出的每个任务。
字符串的循环挪动操作:将最后一个字符移到第一个字符的位置,并且将其他所有字符向右移一个位置。
比如:如果字符串 sss 是 abacaba
,一个任务为 l1=3,r1=6,k1=1l_1=3,r_1=6,k_1=1l1=3,r1=6,k1=1,那么答案为 abbacaa
。接下来一个任务为 l2=1,r2=4,k2=2l_2=1,r_2=4,k_2=2l2=1,r2=4,k2=2,那么我们会得到 baabcaa
。
输入格式
第一行一个字符串 sss,该字符串只包含小写英文字符。
第二行一个整数 mmm,表示任务个数。
接下来 mmm 行每行有三个整数 li,ril_i,r_ili,ri 和 kik_iki。
输出格式
输出执行了 mmm 个任务后的最终的字符串 sss。
样例输入
abacaba
2
3 6 1
1 4 2
样例输出
baabcaa
数据规模
对于所有数据保证,1≤∣s∣≤100001≤|s|≤100001≤∣s∣≤10000(∣s∣|s|∣s∣ 表示字符串 sss 的长度),1≤m≤3001≤m≤3001≤m≤300,1≤li≤ri≤∣s∣1≤l_i≤r_i≤|s|1≤li≤ri≤∣s∣,1≤ki≤10000001≤k_i≤10000001≤ki≤1000000。
解题思路:
步骤如下:
(1)对k=k%lenk=k\\%lenk=k%len(因为循环移动len=r−l+1len = r - l + 1len=r−l+1次之后,子串与操作前一致)
(2)取出子串尾部kkk个字符缓存
(3)将前len−klen - klen−k个字符向后移动kkk位
(3)将缓存的字符放回子串首部
(pspsps:本来想先用模拟尝试深入理解一下题目,看一眼数据规模发现好像能过,结果就过了qwqqwqqwq)
AC代码如下
#include <iostream>
using namespace std;
const int max_len = 1e4;char str[max_len + 1];
char buffer[max_len + 1];int main() {char c = '\\0';int len = 0;while ((c = getchar()) != '\\n' && c != '\\r') {str[len++] = c;}str[len] = '\\0';int t, l, r, k;cin >> t;for (int i = 0; i < t; i++) {cin >> l >> r >> k;k %= r - l + 1; l--; r--;for (int j = r - k + 1; j <= r; j++) {buffer[j] = str[j];}for (int j = r - k; j >= l; j--) {str[j + k] = str[j];}for (int j = r - k + 1, idx = l; j <= r; j++, idx++) {str[idx] = buffer[j];}}cout << str << endl;return 0;
}