2020-05-30 模拟赛

发布于 2020-05-30 | 分类于模拟、搜索、折半搜索、字符串、后缀自动机、校内 | 3分钟 | 712字数 | 浏览量：

~~又双叒叕最后一名，被吊打了/kk~~

一共三道题：

$T_1$ ：大模拟，看题不清写了半个小时寂寞，然后又写了 $40~mins~+$ 。

最后好像有一些细节没考虑到只拿了 $57~pts$ ，然而考完后的人都不想再调了。

$T_2$ ：一道搜索细节题吧（大雾

$30~pts$ 做法：直接暴力干，啥也不需要考虑了。

$50~pts$ 做法：搞一个 $dp[i][j][k]$ ， $i,j$ 表示坐标， $k$ 表示这个坐标上值为 $k$ 的方案数。

$100~pts$ 做法：考虑数据范围在 $30~pts$ 的做法下大约跑 $\binom{40}{20}={10}^{11}$ 左右，我们重新思考发现搞一个折半搜索就好了。（然而我考虑到了范围很小但不会折半搜索的套路，并且转写 $dp$ 时数据范围考虑小了。挂成 $0~pts$ 了。

$T_3$ ：后缀字符串的一些东西。

$10~pts$ 枚举 $l_1,l_2$ 即两个字符串的起始位置，然后再枚举 $k$ 即字符串长度，复杂度为 $\mathcal{O(n^3)}$ 。

对于后面的分数段考虑到把数组差分一下，就是一个正宗的字符串题面了，然而做法不会。

本来打算这周把字符串内容肝完的，结果写完 $AC$ 自动机的内容就没推了，只拿了 $10~pts$ 。

预估 $100+50+10=160~pts$ ，实际 $57+0+10=67~pts$ 。

理想与现实的差距，竟使我黯然神伤，无言以复。

所以还是脚踏实地，老老实实记下套路吧，以后就不要再错了。

~~很多时候我们最需要的不是新型科技，而是拾起曾经的泪水。~~

$T_1$ 本来不想更正，结果发现有一条调试信息没删掉，然后就有 $95~pts$ 了。

这里是一个关于折半搜索的小技巧，可以顺利通过 $T_2$ ：

我们考虑枚举对角线作为中转站，因为一条路径当且仅当只会经过一次对角线。

那么我们首先 $dfs_1$ 出 $(1,1)$ 到 $(n-i+1,i)$ 的路径数，并且记录下他的贡献类型。

然后再 $dfs_2$ 出 $(n-i+1,i)$ 到 $(n,m)$ 的路径数，对应 $dfs_1$ 的记录类型计入答案。

这个东西用 $map$ 实现就好了，注意到虽然搜索次数少了，但是还是只能过小数据。

所以 $dp$ 啥的还是要老老实实学好，妄想 $dfs$ 爆搜过题？~~（朱神行为~~

感谢您的支持，我会继续努力的!