codeforces edu1 B Queries on a String

题意:给一个字符串(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为每次操作区间的长度。

/* ***********************************************
Author :111qqz
Created Time :2015年12月04日 星期五 14时24分56秒
File Name :code/cf/edu/B.cpp
************************************************ */
 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E4+7;
1char st[N];
2int len;
3int m;
4int l,r,k;
5int main()
6{
7	#ifndef  ONLINE_JUDGE 
8	freopen("code/in.txt","r",stdin);
9  #endif
 1	scanf("%s",st);
 2	scanf("%d",&m);
 3	while (m--)
 4	{
 5	    scanf("%d %d %d",&l,&r,&k);
 6	    l--;
 7	    r--; //强行让下标从0开始。。。处理起来方便
 8	    int len = r-l+1;
 9	    k = k % len;
10	    char tmp[N];
1	    for ( int i = l ; i <= r ; i++)
2	    {
3		int offset = (i-l+len-k)%len;
4		tmp[i] = st[offset+l];
5	    }
6	    for ( int i = l; i <= r ; i++) st[i] = tmp[i];
1//	    printf("%s\n",st);
2	}
3	printf("%s\n",st);
1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}