题解 P3654 【First Step (ファーストステップ)】

# 洛谷三月月赛R1·官方题解 T2 #### 本题标程请见题目页面下方的标程部分。 ### 1. 解析 本题只需按照每行分别扫描所有连续的空位，判断连续的一段空位长度是否超过k，如果超过k，则在这段上一共有l-k+1种摆放方式（其中l是长度）。 然后再按照每列扫描一遍，做同样的事情。 需要注意k=1的时候，横着站竖着站一样，所以统计的结果还要除以2。 ### 2. 出题事故 首先没有卡掉O(n^3)的算法。事实上这个之前本人跟出题组提过，不过并没有被重视。也是沟通上的问题。 再来k=1的情况出数据的人本身也没有考虑到特殊情况，本人在写std的时候也忘记了这一茬。结果比赛开始大约1小时才被指出，然后临时修改重测。 因为评测机实现上的一些问题，这一重测又导致了大规模的评测故障，所以本题的分数直到这篇题解发布的时候还不能完全确定。 #### 本题标程请见题目页面下方的标程部分。