Chips
题意翻译
### 题目描述
有$n$个棋子排成环状,标号为$1..n$
一开始每个棋子都是黑色或白色的。随后有$k$次操作。操作时,棋子变换的规则如下:我们考虑一个棋子本身以及与其相邻的两个棋子(共3个),如果其中白子占多数,那么这个棋子就变成白子,否则这个棋子就变成黑子。注意,对于每个棋子,在确定要变成什么颜色之后,并不会立即改变颜色,而是等到所有棋子确定变成什么颜色后,所有棋子才同时变换颜色。
对于一个棋子$i$,与其相邻的棋子是$i-1$和$i+1$。特别地,对于棋子$1$,与其相邻的棋子是$2$和$n$;对于棋子$n$,与其相邻的棋子是$1$和$n-1$。
如图是在$n=6$时进行的一次操作。
![图像](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1244F/954a54cba9c62be21723582b0f9fdfba14d8bb72.png)
给你$n$和初始时每个棋子的颜色,你需要求出在$k$次操作后每个棋子的颜色。
### 输入格式
第一行两个整数$n\ (3 \leq n \leq 2\cdot 10^5)$和$k\ (1 \leq k \leq 10^9)$,表示棋子总数与操作次数。
第二行是一个长度为$n$的,仅由字符$B$和$W$构成的字符串。如果第$i$个字符是$B$,表示第$i$个棋子位黑色,否则为白色。
### 输出格式
一行,长度为$n$的,仅由字符$B$和$W$构成的字符串,描述操作完成后每个棋子的颜色。
注意输出的顺序要和输入数据中的对应。
### 样例解释
1. 就是题目描述中举的那个例子
2. "WBWBWBW" $\rightarrow$ "WWBWBWW" $\rightarrow$ "WWWBWWW" $\rightarrow$ "WWWWWWW"
3. "BWBWBW" $\rightarrow$ "WBWBWB" $\rightarrow$ "BWBWBW" $\rightarrow$ "WBWBWB" $\rightarrow$ "BWBWBW"
题目描述
There are $ n $ chips arranged in a circle, numbered from $ 1 $ to $ n $ .
Initially each chip has black or white color. Then $ k $ iterations occur. During each iteration the chips change their colors according to the following rules. For each chip $ i $ , three chips are considered: chip $ i $ itself and two its neighbours. If the number of white chips among these three is greater than the number of black chips among these three chips, then the chip $ i $ becomes white. Otherwise, the chip $ i $ becomes black.
Note that for each $ i $ from $ 2 $ to $ (n - 1) $ two neighbouring chips have numbers $ (i - 1) $ and $ (i + 1) $ . The neighbours for the chip $ i = 1 $ are $ n $ and $ 2 $ . The neighbours of $ i = n $ are $ (n - 1) $ and $ 1 $ .
The following picture describes one iteration with $ n = 6 $ . The chips $ 1 $ , $ 3 $ and $ 4 $ are initially black, and the chips $ 2 $ , $ 5 $ and $ 6 $ are white. After the iteration $ 2 $ , $ 3 $ and $ 4 $ become black, and $ 1 $ , $ 5 $ and $ 6 $ become white.
![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF1244F/954a54cba9c62be21723582b0f9fdfba14d8bb72.png)Your task is to determine the color of each chip after $ k $ iterations.
输入输出格式
输入格式
The first line contains two integers $ n $ and $ k $ $ (3 \le n \le 200\,000, 1 \le k \le 10^{9}) $ — the number of chips and the number of iterations, respectively.
The second line contains a string consisting of $ n $ characters "W" and "B". If the $ i $ -th character is "W", then the $ i $ -th chip is white initially. If the $ i $ -th character is "B", then the $ i $ -th chip is black initially.
输出格式
Print a string consisting of $ n $ characters "W" and "B". If after $ k $ iterations the $ i $ -th chip is white, then the $ i $ -th character should be "W". Otherwise the $ i $ -th character should be "B".
输入输出样例
输入样例 #1
6 1
BWBBWW
输出样例 #1
WBBBWW
输入样例 #2
7 3
WBWBWBW
输出样例 #2
WWWWWWW
输入样例 #3
6 4
BWBWBW
输出样例 #3
BWBWBW
说明
The first example is described in the statement.
The second example: "WBWBWBW" $ \rightarrow $ "WWBWBWW" $ \rightarrow $ "WWWBWWW" $ \rightarrow $ "WWWWWWW". So all chips become white.
The third example: "BWBWBW" $ \rightarrow $ "WBWBWB" $ \rightarrow $ "BWBWBW" $ \rightarrow $ "WBWBWB" $ \rightarrow $ "BWBWBW".