9134

blog 题面 yinhee 去面试 Google 总裁。 面试官给他了一个长度为 \(n\) 的 \(01\) 串。 面试官给他以下两种操作是的这个序列前 \(n-m\) 个数字与后 \(n-m\) 个数字匹配。具体地说就是让 \[a_1 = a_{m+1} \cdots a_{n - m} = ......

首先考虑一些简单的情况，比如 \(m=1\)。 容易发现操作 1 和操作 2 的顺序不会影响结果，于是可以钦定所有操作 1 在操作 2 之前。并且可以发现，进行完所有 1 后 2 的次数即为 \((\text{连续段个数}-1)\)。 然后考虑将 \(m>1\) 的情况。显然最后序列上每 \(m\) ......