11月做题记录

Ramen 收录于趣题记录

2017-11-26 约 2337 字预计阅读 5 分钟

0x00. 前言

大家好，我是Ramen。

11月经历了很多事情，最主要的就是青岛站被打爆。关于青岛站的看我前面一篇文章。

其次是事情越来越多，很多时候不知道自己在忙什么，恍惚间又堕落了一下午，忙了一个晚上也不知道做了什么。

但是起码刷题坚持下来了，哈。

目前主要就是做lrj紫书和kuangbin系列题目查漏补缺，比赛主要在Codeforces、AtCoder和CS Academy上打（我也想打TopCoder啊，但是都是半夜的SRM打不动啊QAQ）。

不多感叹了，Here We Go。

我的答案仓库是 Click Me!。根据题号你能找到我的答案，但是我的答案有很大改进余地，欢迎与我探讨。

0x01. 模板题

本期的模板题主要是刷完了kuangbin带你飞第一期，具体的点击查看就好，主要是BFS与DFS。

这一期没做什么模板题，时间不是很多。12月要看一手新东西了。

0x02. 趣题

组合数学十分有意思。很多时候有些题思路真的很晕，感觉还是思路杀，这个东西不积累不行。

Ralph And His Magic Field
Another Chinese Round。又是一道组合数学的题目，十分有趣。
题意很简单，$n\times m$方格里面放数，保证每一行每一列乘积均为$k$，求可行方案数对$1e9+7$去模。题目限制了$k\in {-1,1 }$，那这个随意放数字不就是$1$和$-1$两种。其次考虑一个问题，如果$n+m$是一个奇数而$k=-1$的话，我们怎么放都不可能放的满足要求，这一点应该比较容易想到，想不到的话画一个$3\times 4$的方格自己尝试一下就行。
接下来难点在于怎么剩下的划分。考虑对于任一行，对于这一行的排列来说，假如前$m-1$个数确定了，那根据规则，最后这$1$个数也确定了。对于列同理。所以最终需要考虑的格子只有$(n-1)\times(m-1)$个。最终答案就是$2^{(n-1)\times(m-1)}$。
这里有一个问题，这个数太过巨大，而且算起来很麻烦。这里首先第一步的处理是使用快速幂，这里带来的是时间上的优化。第二步，根据幂的运算律：$2^{(n-1)\times(m-1)}=(2^{(n-1)})^{(m-1)}$，那这里我们就先计算内部的$2^{(n-1)}$，再计算外部就能保证不会溢出了。
这个题比赛的时候前中期过的人甚至没有C多，太凶险了。~~然而C在System Test干掉了2/3的人更凶险~~。
另外，这个题我比赛的时候想的是枚举第一行和第一列，然后reduce到$(n-1)\times(m-1)$的情况，完全反向了，不过还是很有启发性，很不错的题目。
Short Program
另一道很有趣的题目。你有一台运算机，可以接受三种操作：与或非，以及一个操作数。有个人写了一个小程序，但是太长了，需要你简化到5步以内。题解看这一篇比我讲的好。
这个题有趣的地方在于对于位运算的化简。关键的一个点是，我们需要构建这样一个映射：
$$procedure(x)=f(x)=(((x\times a)+b)\oplus c)$$
而我们的构造方法是使用中间变量$x$和$y$，看$x$与$x’$、$y$与$y’$最后的真值对应关系来计算出$a$、$b$、$c$。这个思路很巧妙，很多时候我们做位运算的题目可以根据初始状态和终止状态来获得映射关系。

Sudoku

题意十分简单，给出一个$n\times n$大小的数独，问当前这个解是否是一种正解（也就是说行、列、块没有重复数字）。

这个题很简单吧？但是这里我拿出来这道题是因为这种做法：

1
2
3
4
5
6
7
8
a = to_string(t) + " shows on row " +  to_string(i);
b = to_string(t) + " shows on column " +  to_string(j);
c = to_string(t) + " shows on section " +  to_string(i / 3) + "," + to_string(j / 3);
if (hash.count(a) || hash.count(b) ||  hash.count(c))
    valid = false;
hash.insert(a);
hash.insert(b);
hash.insert(c);

这种做法真的巧妙！利用了hash的性质，很漂亮的解决了这个问题，我从微博看到的，这样的hash做法是第一次见到，真的是让我大呼"Eureca!"

0x03. 难题

新栏目，讲讲那些困扰了我一段时间的题目。

Olya and Energy Drinks
Olya在一张$n\times m$大小的图上，每次可以冲刺$1-k$的距离，问给定两个点需要的最短时间。
标准BFS没错吧？$\mathcal{O}(n\cdot m\cdot k)$，狂吃TLE。
这个题第一步剪枝很容易想到，我们可以在每次更新的时候直接更新同方向$1-k$距离的所有点，然后就能得出答案。
但是在这一步剪枝就有一个问题，这个题的层次不只是空间层次，还有时间层次。比如，以下两个移动序列都是合法的：
$$(1,1)\to\mathcal{O}(1,3)\to\mathcal{O}(3,3)\\(1,1)\to\mathcal{O}(1,2)\to\mathcal{O}(2,3)\to\mathcal{O}(3,3)$$
那么肯定不能直接开一个vis数组，因为这样会干扰其他路径。这里有两种做法：
- 考虑距离
  我们在每次更新到当前点的最小距离，一旦出现更小的就进行更新，那么我们经过这一层次搜索之后，我们就能在dis[ex][ey]处得到最小距离。
- 考虑方向
  首先根据BFS的性质，假如我们到达第$l$个点，我们必定是得到的是从$l-1$点方向上所有点到$l$的最小距离，那么同理对$l-1$也可以讨论。这么递推回去的结果是，从起点到第$l$个点，沿着这一种方向上到达的最小距离只需要一次BFS就能得到。同时，从相同路径方向的不同冲刺距离下到达$l$点的最短步数也就是这个BFS的结果。那么第一个层次解决了，我们考虑第二个层次。每一个点都有可能成为其他店的中转点，然后根据上面的讨论，每一个方向上的最短距离都可以一步BFS得到，所以我们只需对当前点考虑四个方向进来的步数即可。所以我们的剪枝就是对每个终点看进入方向，假如没搜索过，就放入搜索，否则就不再搜索。
两个思路都很巧妙，但是我觉得第二个思路更有思维深度和BFS特性，我最后选择第二种做法。

这个月很多时候面对很多题解和别人代码都感觉头晕，很多时候对于为什么使用min和max，变量间是什么关系真的毫无想法，可能真的是做题不足。

还干过什么变量开小了（答案可能是long long范围结果开了个int），真的是蠢。

一道魔方题手打287行代码然后一发A还是很爽的（看了标程感觉自己是一个智障）。

努力吧。

目录

11月做题记录

0x00. 前言

0x01. 模板题

0x02. 趣题

0x03. 难题