牛客網 www.nowcoder.com 普及組（第一場）No.2

題目描述

小A站在一個巨大的棋盤上。這個棋盤可以看成是一個網格圖。這個網格圖的大小為n*m。左上角坐标為(1,1)，右下角坐标為(n,m)。這個棋盤很特别，他每行每列都是一個環。具體來說，當小A站在第一行，他往上走的時候，他會走到第n行，站在第n行往下走會走到第一行。對于第一列和第m列類似。小A在棋盤上可以上下左右走，假設他站在位置(i,j)，向上走，會走到(i-1,j)，向下回到(i+1,j)，向左到(i,j-1)，向右到(i,j+1)。注意由于棋盤是循環的，他不會走出這個棋盤。

現在小A有一個固定的行走序列S，代表他每一步走的方向，U代表向上，D代表向下，L代表向左，R代表向右。比如小A一開始在(1,1)，棋盤大小為3*4。行走序列為UULRD。那麼他會依次經過(3,1),(2,1),(2,4),(2,1),(3,1)。但小A覺得隻走一遍S太無聊，是以他會重複走這個序列T次。比如上面的例子，當T=2時，真正的行走序列為UULRDUULRD。

小A有q個備選的起點位置。他一開始先給定你棋盤大小與行走序列，對于每個起點位置，他想知道，他沿着序列走，最終會走到哪個位置停下。

輸入描述:

第一行三個整數n,m,T。
接下來一行一個字元串S，代表行走序列。注意行走序列在真實走的時候要重複T次。
接下來一個整數q。
接下來q行，每行兩個整數x,y，代表小A的一個備選起點。      

輸出描述:

輸出q行，每行兩個整數，輸出對于這個起點，最後的終點是哪裡。
      

輸入

3 6 4
DUUUDLLLLR
3
3 2
2 5
1 4
      

輸出

2 2
1 5
3 4
      

備注:

20%: |S| * T <= 10^6, q = 1
40%: |S| * T <= 10^6, q <= 10^5
60%: |S|, T <= 10^5, q <= 10^5
100%: 1 <= T,n,m <= 10^9, 1 <= x <= n, 1 <= y <= m. 1<= q, |S| <= 10^5
其中|S|代表S的長度。      

思路:

把它往哪走幾步統計出來，注意它相當于一個環，用模拟就可以搞定了。

#include<iostream>
using namespace std;
int n,m,T,q,a,b;
long long x,y;//注意開long long
string s;
#define cuvee return
#define miao_ 0
int main()
{
	cin>>n>>m>>T;
	cin>>s;
	for(int i=0;i<n;i++)
	{
		if(s[i]=='U') x--;
		if(s[i]=='D') x++;
		if(s[i]=='L') y--;
		if(s[i]=='R') y++;//統計
	}
	cin>>q;
	x*=1LL*T;
	y*=1LL*T;//long long
	for(int i=1;i<=q;i++)
	{
		cin>>a>>b;
		a=a-1;b=b-1;//先減一（一位AK大佬的思路，是以就歸在轉載裡面啦）
		a=((1LL*a+x)%n+n)%n+1;
		b=((1LL*b+y)%m+m)%m+1;//計算移動
		cout<<a<<" "<<b<<endl;//考的時候沒打回車qwq
	}
	cuvee miao_;
}