codeforces edu1 B Queries on a String

2015年12月4日 0 作者 CrazyKK

题意:给一个字符串(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 l1 = 3, r1 = 6, k1 = 1 then the answer is abbacaa. If after that we would process the query l2 = 1, r2 = 4, k2 = 2 then we would get the string baabcaa.

 

简单的说。。就是把最后一位移动到第一位,其他位依次往后。

很容易想到,对于一个长度为len的字符串。进行i次变换和进行(i+len)次变换是等价的。

然后直接暴力搞。

offset为偏移量。对于位置i的偏移量为(i-l+len-k)%len,len为每次操作区间的长度。