AT2146 一次元リバーシ / 1D Reversi

    • 94通过
    • 162提交
  • 题目来源 AtCoder 2146
  • 评测方式 RemoteJudge
  • 标签 字符串
  • 难度 普及-
  • 时空限制 2000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    输入一个长度不多于$10^5$的字符串,只包含B或W。若前后两个字符不一样,答案累加,输出答案。

    感谢@da32s1da 提供的翻译

    题目描述

    きつねの次郎と三郎が一次元リバーシで遊んでいます。一次元リバーシでは、盤面には白か黒の石が一列に並んだ状態となっており、列の右端か左端に新たに石を打っていきます。通常のリバーシと同じように、たとえば白の石を打つことで黒の石を挟むと、挟まれた黒の石は白い石に変わります。

    ゲームの途中で三郎に急用ができて帰ってしまうことになりました。このとき、盤面の状態は文字列 $ S $ で表されます。石は $ |S| $ (文字列の長さ) 個並んでおり、左から $ i $ ( $ 1\ ≦\ i\ ≦\ |S| $ ) 個目の石の色は、 $ S $ の $ i $ 文字目が B のとき黒、W のとき白です。

    次郎は現在の盤面に対して、できるだけ少ない個数の石を新たに打つことで全ての石を同じ色にしようと考えました。最小で何個の石を打てばよいかを求めてください。

    输入输出格式

    输入格式:

    The input is given from Standard Input in the following format:

     $ S $ 

    输出格式:

    Print the minimum number of new stones that Jiro needs to place for his purpose.

    输入输出样例

    输入样例#1: 复制
    BBBWW
    输出样例#1: 复制
    1
    输入样例#2: 复制
    WWWWWW
    输出样例#2: 复制
    0
    输入样例#3: 复制
    WBWBWBWBWB
    输出样例#3: 复制
    9

    说明

    制約

    • $ 1\ ≦\ |S|\ ≦\ 10^5 $
    • $ S $ に含まれる文字は B または W のいずれかである

    Problem Statement

    Two foxes Jiro and Saburo are playing a game called 1D Reversi. This game is played on a board, using black and white stones. On the board, stones are placed in a row, and each player places a new stone to either end of the row. Similarly to the original game of Reversi, when a white stone is placed, all black stones between the new white stone and another white stone, turn into white stones, and vice versa.

    In the middle of a game, something came up and Saburo has to leave the game. The state of the board at this point is described by a string $ S $ . There are |S| (the length of $ S $ ) stones on the board, and each character in $ S $ represents the color of the $ i $ -th ( $ 1\ ≦\ i\ ≦\ |S| $ ) stone from the left. If the $ i $ -th character in $ S $ is B, it means that the color of the corresponding stone on the board is black. Similarly, if the $ i $ -th character in $ S $ is W, it means that the color of the corresponding stone is white.

    Jiro wants all stones on the board to be of the same color. For this purpose, he will place new stones on the board according to the rules. Find the minimum number of new stones that he needs to place.

    Constraints

    • $ 1\ ≦\ |S|\ ≦\ 10^5 $
    • Each character in $ S $ is B or W.

    Sample Explanation 1

    たとえば右端に黒い石を打つとすべての白い石を黒い石にすることができます。他にも、左端に白い石を打つことでもすべての石の色を同じにできます。

    いずれの場合も $ 1 $ 個の石ですべての石を同じ色にすることができるので、 $ 1 $ を出力します。

    Sample Explanation 2

    最初から全ての石が同じ色の場合、新たに石を打つ必要はありません。

    Sample Explanation 4

    By placing a new black stone to the right end of the row of stones, all white stones will become black. Also, by placing a new white stone to the left end of the row of stones, all black stones will become white.

    In either way, Jiro's purpose can be achieved by placing one stone.

    Sample Explanation 5

    If all stones are already of the same color, no new stone is necessary.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。