企业官网建设流程全解析

P16151 [ICPC 2017 NAIPC] Yin and Yang Stones

Link: https://www.luogu.com.cn/problem/P16151

题目描述

一个由黑石和白石组成的环形神秘图案出现了。Ming 的任务是通过操作使石子达到平衡，最终只剩下一个黑石和一个白石。

Ming 有两种平衡操作：

1. 选取一段连续的石头，其中黑石的数量恰好比白石的数量多 1，并将这一段替换为一个黑石。
2. 选取一段连续的石头，其中白石的数量恰好比黑石的数量多 1，并将这一段替换为一个白石。

给定一个环形排列，请判断 Ming 是否能通过上述操作使石子达到平衡。

输入格式

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入仅包含一个字符串s ss（1 ≤ ∣ s ∣ ≤ 10 5 1 \leq |s| \leq 10^51≤∣s∣≤105），仅由大写字母 ‘B’ 和 ‘W’ 组成。石子呈环形排列，因此第一个石子和最后一个石子相邻。

输出格式

如果 Ming 能通过他的操作使石子达到平衡，则输出 1，否则输出 0。

输入输出样例 #1

输入 #1

WWBWBB

输出 #1

1

输入输出样例 #2

输入 #2

WWWWBBW

输出 #2

0

输入输出样例 #3

输入 #3

WBBBBBWWBW

输出 #3

0

Solution

1. 题意

一系列黑白棋围成一个圆圈，每次操作可以：

• 选择一段黑棋比白棋多 1 个的区段，将这部分替换为 1 个黑棋；
• 选择一段白棋比黑棋多 1 个的区段，将这部分替换为 1 个白棋。

问最后是否恰好可以剩下刚好一个黑棋和一个白棋。

2. 分析

看上去很唬人，其实简单到爆。

回顾一下题意：

选择一段黑棋比白棋多 1 个的区段，将这部分替换为 1 个黑棋。

这个操作其实相当于：

选择一段黑棋比白棋多 1 个的区段，将这部分替换为 1 个黑棋和 0 个白棋。

看到没有，替换前这一段黑棋比白棋多 1，替换后 1 个黑棋 0 个白棋，还是黑棋比白棋多 1。另外一种操作与之同理。如此一来就会发现，给定的两种操作并不能用于减少两种棋子数量上的差距。这也就意味着，当且仅当最开始黑棋白棋数量相等，就能平衡，否则就不能平衡。

3. 代码

两行 Python 代码直接秒掉此题。

ring=input()print(1ifring.count("W")==ring.count("B")else0)