牛客contest5668-B: Classical String Problem

传送门

题目大意

给定一个由小写字母组成的字符串S。你要执行一系列操作。有以下两种操作：
1、修改：给定一个整数x，你需要根据x的值来修改S。如果x是正数，就把S中最左边的x个字母移到S的右边；否则，就把S中最右边的|x|个字母移到S的左边。
2、查询：给定一个正整数x，输出字符串中第x个字符。

思路

题面很简单，朴实的字符串位移操作。上手十分钟写了个string模拟

#include <bits/stdc++.h>

using namespace std;

int q;
string str;

int main()
{
	cin >> str;
	scanf("%d", &q);
	
	while(q--)
	{
		int x;
		char op;
		scanf("%d", &op);
		
		switch (op)
		{
		case 'A':
			scanf("%d", &x);
			printf("%c\n", str[x-1]);
			break;
			
		case 'M':
			scanf("%d", &x);
			if(x > 0)
			{
				string tmp = str.substr(0, x);
				str.erase(0, x);
				str += tmp;
				//cout << "str is:" << str << endl;
			}
			else
			{
				x = abs(x);
				int len = str.length();
				string tmp = str.substr(len-x, len);
				str.erase(len-x, len);
				tmp += str;
				str = tmp;
				//cout << "str is:" << str << endl;
			}
			break;
		}
	}
	
	return 0;
} 

然后非常果断地超时了，说明这道题不能用模拟的思路来做。

改进

既然不能直接对字符串操作，那么考虑直接计算下标。

使用recent指针记录每次操作后的下标位置，输出答案时直接对ret加上当前输入的x即是所查询的字符。处理下标越界的情况，模上字符串长度。

#include <bits/stdc++.h>

using namespace std;

const int LIM = 2e6 + 5;
char str[LIM], op[10];
int q, x, ret;

int main()
{
	scanf( "%s", str );
	scanf( "%d", &q );
	const int LEN = strlen( str );
	
	while(q--)
	{
		scanf( "%s", op );
		scanf( "%d", &x );
		if ( op[0] == 'A' )
			printf( "%c\n", str[(ret + x + LEN - 1) % LEN] );
		else
			ret = (ret + x) % LEN;
	}
	return 0;
}