Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给一个字符串（1E4），然后给m次操作（m<=300），每次操作是给定一个区间l,r，然后进行k次（k<=1E6）cyclic shift (rotation) 变换。
One operation of a cyclic shift (rotation) is equivalent to moving the last character to the position of the first character and shifting all other characters one position to the right.
For example, if the string s is abacaba and the query is _l_1 = 3, _r_1 = 6, _k_1 = 1 then the answer is abbacaa. If after that we would process the query _l_2 = 1, _r_2 = 4, _k_2 = 2 then we would get the string baabcaa.
简单的说。。就是把最后一位移动到第一位，其他位依次往后。
很容易想到，对于一个长度为len的字符串。进行i次变换和进行（i+len）次变换是等价的。
然后直接暴力搞。
offset为偏移量。对于位置i的偏移量为（i-l+len-k）%len,len为每次操作区间的长度。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2015年12月04日 星期五 14时24分56秒
4File Name :code/cf/edu/B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25
26
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E4+7;
34
35char st[N];
36int len;
37int m;
38int l,r,k;
39int main()
40{
41 #ifndef ONLINE_JUDGE
42 freopen("code/in.txt","r",stdin);
43 #endif
44
45 scanf("%s",st);
46 scanf("%d",&m);
47 while (m--)
48 {
49 scanf("%d %d %d",&l,&r,&k);
50 l--;
51 r--; //强行让下标从0开始。。。处理起来方便
52 int len = r-l+1;
53 k = k % len;
54 char tmp[N];
55
56 for ( int i = l ; i <= r ; i++)
57 {
58 int offset = (i-l+len-k)%len;
59 tmp[i] = st[offset+l];
60 }
61 for ( int i = l; i <= r ; i++) st[i] = tmp[i];
62
63// printf("%s\n",st);
64 }
65 printf("%s\n",st);
66
67
68 #ifndef ONLINE_JUDGE
69 fclose(stdin);
70 #endif
71 return 0;
72}