ClassicalStringProblem

There are Q+2 lines in the input. The first line of the input contains the string S. The second line contains the integer Q. The following Q lines each denotes an operation. You need to follow the order in the input when performing those operations.

Each operation in the input is represented by a character c and an integer x. If c = 'M', this operation is a modify operation, that is, to rearrange S according to the value of x; if c = 'A', this operation is an answer operation, to answer what the x-th letter in the current string S is.

  • $2 \le |S| \le 2 \times 10^6$ (|S| stands for the length of the string S)
   • S consists of lower case letters
  •    $1 \le Q \le 8 \times 10^5$
   • c = 'M' or 'A'
   • If c = 'M', $1 \le |x| < |S|$
  •  If c = 'A', $1 \le x \le |S|$
   • There is at least one operation in the input satisfies c = 'A'

C(clang 3.9) 解法, 执行用时: 210ms, 内存消耗: 13076K, 提交时间: 2020-09-18 14:28:26

#include<stdio.h>
#include<string.h>

char s[2000005];

int main(){
	int n,T,k=0,w,l;
	char c;
	scanf("%s",&s);
	scanf("%d\n",&T);
	l=strlen(s);
	while(T--)
	{
		scanf("%c %d",&c,&w);
		getchar();
		if(c=='M')
		k=(k+w+l)%l;
		else
		printf("%c\n",s[(k+w-1)%l]);
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 238ms, 内存消耗: 4364K, 提交时间: 2020-07-18 12:12:19

#include<bits/stdc++.h>
using namespace std;
int _,n;
string s;
int main(){
	int k=0,x; char ch;
	cin>>s;
	n=s.length();
	for (scanf("%d",&_);_;_--){
		scanf("%c%c%d",&ch,&ch,&x);
		if (ch=='M') k=(k+x+n)%n;
		else printf("%c\n",s[(k+x-1)%n]);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 238ms, 内存消耗: 13424K, 提交时间: 2020-07-19 16:57:54

#include<bits/stdc++.h>
using namespace std;
string s;
int q,l,t,m;
char c[5];
int main(){
	cin>>s;
	cin>>q;
	l=s.size();
	while(q--){
		scanf("%s%d",c,&t);
		if(c[0]=='M'){
			m=(m+t+l)%l;
		}
		else printf("%c\n",s[(m+t-1)%l]);
	}
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 1291ms, 内存消耗: 17012K, 提交时间: 2020-07-19 09:11:07

from sys import stdin
s = input()
n = int(input())
slen = len(s)
i=0
M = 0
while i <n :
    p,q = stdin.readline().strip().split()
    q = int(q)
    if(p == "A"):
        print(s[(M + q)%slen-1])
    else:
        M += q
    i += 1

详情