清明节爬山的时候手指被石头砸住了,所以打代码的时候真是惨,就像疯狂动物城里的闪电......不过讲道理题目难度和质量还是很合适的,传送门

1. 二分。签到题,对于选定的字号m,先算出来段落总共占多少行,然后再计算需要多少页,取整的地方要注意。

2. Trie。把每条规则对应的前缀01串插入Trie中,结点保留规则编号,询问的时候记录匹配到的最小编号。使用哈希表也可以做,把前缀插入哈希表,并建立前缀和编号的映射,询问的时候枚举前缀,记录匹配到的最小编号。

3. 动态规划。容易想到,使用dp[i][j]表示到达(i, j)位置需要的最小变换,到不了某个位置的时候就需要拆墙或者加墙,直行有墙就拆,转弯没墙就加,拆墙和加墙只是状态转移的条件,并没有对原图做实际的改变,因而也满足动态规划无后效性的要求。另外,由于涉及改变方向的操作,因此需要再开一维表示方向。

4. 给手指做按摩......所以就没看题。比赛结束后看了下,小数据可以爆搜,没想到大数据也搜过了...条件一的判断比较简单,对于条件二,按照添加顺序从后向前搜索,看能不能与外界的点(101, 101, 101)连通,并对结果记忆化。我先从(101, 101, 101)bfs出与外界连通的区域,并对这些区域做标记,之后逆向对每个点dfs的时候,遇到有标记的点就可以直接剪枝了。 // 由于空间开小wa了26发...嗯...

ps. 学习了金牌爷鞠神的宏,感觉省了很多字符...Orz