P1563 [NOIP2016 提高组] 玩具谜题(找规律，心要细，数学思维）

Description of the topic

Xiaonan has a lovely set of toys, they have different occupations.

One day, these toy people hid Xiaonan's glasses. Xiaonan found the toys around a circle, some face inside, some face out of the circle. Here's the picture:

At this time, singersinger told Xiaonan a mystery: "The glasses are hidden in my left number 3rd toy person right number 11th toy person left number 22nd toy little person." ”

Xiaonan found that the toy in this puzzle is very critical, because the inside and outward toys are opposite to the left and right direction: face inside the circle of toys, its left side is clockwise direction, the right side is counterclockwise direction; And facing the toy person outside the circle, its left side is counterclockwise direction, the right side is clockwise direction.

Xiaonan struggled to identify the toy man, counting:

Singersinger faces inward, and the 33rd on the left is archerarcher.

Archer archer faced out, and the 11th on the right was thinkerthinker.

Thinkerthinker faces outwards, and the 22nd on the left is writwriter.

So the glasses are hidden here in writerwriter!

Although successfully recovered the glasses, but Xiaonan did not rest assured. If there were more toys to hide his glasses next time, or if the mystery was longer, he might not be able to find them. So Xiaonan wants you to write a program to help him solve similar puzzles. Such a puzzle can be described as:

There are nn toys in a circle, known for their occupation and orientation. Now the 11th toy man tells Xiaonan a mystery containing the mm instruction, wherein the zz instruction is shaped like "left/right number ss, a toy little man". You need to output these instructions in turn after arriving at the toy man's occupation.

Enter the format

The first line of the input contains two positive integers n, mn, m, representing the number of toy cubs and the number of instructions.

Next nn lines, each containing an integer and a string, gives the orientation and occupation of each toy person counterclockwise. Where 00 indicates an inner orientation ring and 11 indicates an outward orientation ring. Make sure that no other numbers appear. Strings are no longer than 1010 in length and consist only of lowercase letters, strings are not empty, and strings are two or two different. Integers and strings are separated by a space.

Next, line mm, where line ii contains two integer a_i, s_iai, si, for the second instruction. "If the a_i is 0ai, it means s_isi people to the left, and if a_i is 1ai to 1, it means to the right s_isi individuals." Guarantee that no other numbers will appear in the a_iai, 1 sle s_i < n1 ≤si<n.

The output format

Output a string that represents the occupation of the person who arrived after counting mm instructions, starting with the first person to read in.

A sample of the input and output

Enter #1 copy

7 3
0 singer
0 reader
0 mengbier 
1 thinker
1 archer
0 writer
1 mogician 
0 3
1 1
0 2

输出 #1复制

writer

输入 #2复制

10 10
1 C
0 r
0 P
1 d
1 e
1 m
1 t
1 y
1 u
0 V
1 7
1 1
1 4
0 5
0 3
0 1
1 6
1 2
0 8
0 4

输出 #2复制

y

说明/提示

【样例1说明】

这组数据就是【题目描述】 中提到的例子。

【子任务】

子任务会给出部分测试数据的特点。 如果你在解决题目中遇到了困难, 可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表:

其中一些简写的列意义如下:

• 全朝内: 若为“√”, 表示该测试点保证所有的玩具小人都朝向圈内;

全左数:若为“√”,表示该测试点保证所有的指令都向左数,即对任意的

1≤z≤m, a_i=01≤z≤m,ai=0;

s= 1s=1:若为“√”,表示该测试点保证所有的指令都只数1个,即对任意的

1≤z≤m,s_i=11≤z≤m,si=1;

职业长度为11 :若为“√”,表示该测试点保证所有玩具小人的职业一定是一个

长度为11的字符串。

题意分析就是要每一次的方向动都要进行更新，然后保证值为正，还有开数组大小要足够。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;//如果发现运行对的但是就是过不了，考虑一下空间 
int main()
{
  int n,m;int k=1; 
  cin>>n>>m;
  int a[maxn];char b[maxn][11];
  for(int i=1;i<=n;i++)
  {
  cin>>a[i]>>b[i];      
  } 
  for(int i=1;i<=m;i++)
  {
    int x,y;
    cin>>x>>y;
    if(a[k]==0)
    {
      if(x==0)k=k-y;
      else k=k+y;
    }
  else
    {
      if(x==0)k=k+y;
      else k=k-y;
    }
    if(k<=0)k=k+n;
    if(k>n)k=k-n;
  }
  cout<<b[k]<<endl;
}