正经题解｜电子打印机

题目大意

给出一个字符串$s$，并且首尾相连，即$n+1 -> 1$ , 现在要求将字符串当中的字符$a_i$集体向后移动$m$位，求解位移后的字符串。

解题思路

我们设定字符串$s$的长度为$n$，假若$m > n$的情况下，实际上每位$a_i$位移的格子相当于$m \% n$ 格，例:

• abcde 右移1格为 eabcd
• abcde 右移6格为 eabcd

不难发现，在字符串长度为$n = 5$的情况下右移1格与右移6格的结果相等，那么我们就可以得等价关系 $ m = m % n$。

进一步换算，假若字符串下标从0开始进行计算，那么转移后第$i$位的位置与原来字符串的位置表达式可以写为$i = (n - m + i) \% m$

时间复杂度分析

$O(n)$

演示代码

#include<bits/stdc++.h>
using namespace std;

void solve()
{
	string s;
	int m;
	cin >> s >> m ;
	int len = s.size();
	m %= len; 
	for(int i = 0 ; i < s.size() ; i ++ )
	{
		cout << s[(len - m + i) % len];
	}
	cout << endl;
}


int main()
{
	solve();
	return 0;
}