CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== A ======

思路非常巧妙啊，

假如我们先随便走一条路，我们看最少用多少方框可以使得路上的黑色全部变白，

然后发现一个方框能且仅能圈住路径上连续的一段黑色，

答案即为路径上连续的黑色段数，

那么dp求解连续的黑色段数最少是多少即可。

====== B ======

首先如果自己先做一行的话，就只存在0，1，2了。

如果只有0和1呢，

那原式相当于$S_{i,j}=S_{i-1,j}+S_{i-1,j+1}\ mod \ 2$ ，即最后答案为每个数字出现的次数*每个数字%2

所以答案为$S_{n,1}=\sum_{i=1}^{n}a_i*C_{n-1}^{i-1} \ mod\ 2$

值得一提的是模2意义下，$C_n^m=(n\ and\ m)==m$

这个做法事实上也确实求出了$S_{n,1}\ mod\ 2$的值，那么如果值是1，答案就是1.

那么如果值是1，如何判断是0还是2呢

然后我们又发现，第二层如果有1的话，答案不会为2，因为2早晚要和1做差。

如果第二层没1呢，答案只可能是0或2了，那我们将每个数除2，又变成了只有0和1的问题

最后再给答案乘个2即可。

这一场告诉了我们什么呢，

告诉了我们实力不够先别打AGC。

CVBB ACM Team

用户工具

站点工具

页面工具