题目解析（洛谷 AtCoder）题目要求我们模拟一个 “乌拉姆·沃伯顿自动机”，即一个网格图，每个格子可以为白或黑色，仅当一个格子为白色且仅有一个相邻格子为黑色时将其染成白色，在稳定状态下（即网格不会在发生改变的状态）停止，输出黑色格子数量
:::info[样例解析]
样例 1 解析模拟过程如下：（白色为 . 黑色为 #）
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
#
#
#
.
.
.
.
.
.
.
#
.
.
.
.
.
.
.
. ...
形式化题意给定一个分数 $\frac{P}{Q}$，它是由若干个分数的平均值构成的。构造一个数列，其中每个数要么为 $1$（即 $\frac11$），要么为 $0$（即 $\frac00$），输出至少经过几次平均运算才能从这样的数列构造出 $\frac{P}{Q}$。
（注：因为 $\frac{P}{Q}$ 是由平均值得来的，所以 $0 \le \frac{P}{Q} \le 1$。）
示例分数为 $\frac14$，可以由下式得出：$$\large{\frac{\frac{0}{1}+\frac{1}{2}}{2}}$$
思路由于目标分数是由多次平均值得出的，分母只通过通分运算和乘以 $\frac12$ 的运算改变，因此可以证明：有效的目标分数分母一定为 $2$ 的幂次。
如果分母不为 $2$ 的幂次，直接判否，输出 impossible。
同样可以证明：约分后的分子 $\frac{P}{\gcd(P,Q)}$ 为奇数（即不含因数 $2$）。
可以将这个题目想象为一棵二叉树，底部的每一对节点对目标分数的贡献相当于 $\log_2 n$。要得到分子 $P$，在每一层（作为叶子）需要的 ...
题目输入 $n$ 个字符串，$m$ 个匹配串，统计每个 $m$ 在 $n$ 中的匹配次数。
思路由于本题的规模非常小，可以直接暴力匹配，对于每一个 $s$ 遍历一次 $c$ 判断是否为 $s$ 的前缀（substr 用于取子串，substr(0, s.size()) 代表从 0 开始，长度为 s.size() 的子串，也就是开头 $|s|$ 个字符）。
代码时间复杂度：$O(n\times m\times |s|)$。
123456789101112131415161718192021222324252627282930313233#include<bits/stdc++.h>using namespace std;int n, m;string c[105];int main(){ cin >> n >> m; for (int i = 1; i <= n; i++) cin >> c[i]; for (int i = 1; i <= m; i++) { string s; cin >> ...
