HBC236064[SHOI2011]双倍回文,并查集,数据结构Wandering Robot题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

DreamGrid creates a programmable robot to explore an infinite two-dimension plane. The robot has a basic instruction sequence a1,a2,…an and a "repeating parameter" kkk, which together form the full instruction sequence s1,s2,…,snks_1, s_2, dots, s_n, s_{n+1}, dots, s_{nk}s1,s2,…

DreamGrid creates a programmable robot to explore an infinite two-dimension plane. The robot has a basic instruction sequence a1,a2,…ana_1, a_2, dots a_na1​,a2​,…an​ and a "repeating parameter" kkk, which together form the full instruction sequence s1,s2,…,sn,sn+1,…,snks_1, s_2, dots, s_n, s_{n+1}, dots, s_{nk}s1​,s2​,…,sn​,sn+1​,…,snk​ and control the robot. There are 4 types of valid instructions in total, which are `U' (up), `D' (down), `L' (left) and `R' (right). Assuming that the robot is currently at (x,y)(x,y)(x,y), the instructions control the robot in the way below: U: Moves the robot to (x,y+1)(x,y+1)(x,y+1). D: Moves the robot to (x,y−1)(x,y-1)(x,y−1). L: Moves the robot to (x−1,y)(x-1,y)(x−1,y). R: Moves the robot to (x+1,y)(x+1,y)(x+1,y). The full instruction sequence can be derived from the following equations {si=aiif 1≤i≤nsi=si−notherwisebegin{cases} s_i = a_i & text{if } 1 le i le n \ s_i = s_{i-n} & text{otherwise} end{cases}{si​=ai​si​=si−n​​if 1≤i≤notherwise​ The robot is initially at (0,0)(0,0)(0,0) and executes the instructions in the full instruction sequence one by one. To estimate the exploration procedure, DreamGrid would like to calculate the largest Manhattan distance between the robot and the start point (0,0)(0,0)(0,0) during the execution of the nknknk instructions. Recall that the Manhattan distance between (x1,y1)(x_1,y_1)(x1​,y1​) and (x2,y2)(x_2,y_2)(x2​,y2​) is defined as ∣x1−x2∣+∣y1−y2∣left| x_1 - x_2 right| + left| y_1 - y_2 right|∣x1​−x2​∣+∣y1​−y2​∣.

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： HBC236064[SHOI2011]双倍回文 并查集 数据结构Wandering Robot题解