题解 | #String Game#

题目大意：

给出一个长度为n的字符串，问操作k次后的字符串。

定义一次操作为：将第一个字符放在末尾，其他字符向前移。

思路：

• Subtask1:

对于$10^{5}10^5$次操作，我们可以直接选择暴力模拟翻转过程。

• Subtask2:

对于这档分数，我们发现题目良心地给出了特殊条件A:$x\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)x\backslash equiv\; 0\backslash pmod\; n$ A的意思就是(x-0)/n得出数是一个正整数，那不就是在说明x是n的倍数吗！ 通过几次模拟不难发现，我们操作n-1次，就是将整个字符串头变尾，尾变头。 操作n次就是不变，那n的倍数也是同理。 答案为原串，这一档分数就到手了。

• Subtask3：

K直接增加到$10^{18}10^\{18\}$，模拟一定会超时。 考虑在纸上手动模拟几组数据（这里大家自己模拟） 会发现答案具有周期性，规律就是K%n表示开头的字符，答案为kn-1(字符串从0开始记位)+0k-1 处理这种问题，我们考虑将整个字符串复制一遍到末尾（破环成链），然后直接输出开始位k向后n个字符。

Code:

#include <cstdio>
#include <iostream>

using namespace std;

typedef long long ll;

ll n, x;
char s[200100];

int main()
{
    scanf("%lld%lld", &n, &x);
    cin>>s;
    for(ll i = 0; i < n; i++) s[i + n] = s[i];  //破环成链
    //cout<<endl;
    x %= n;
    for(ll i = x; i <= x + n - 1; i++) cout<<s[i];
    printf("\n");
}