【NOIP 2018】填数游戏(思考与推导)
这道题讲道理还是不错的,因为你需要不断挖掘其中的性质来帮助解题。可惜数据范围开在这里让考试时的我很慌,勉强也就写了$65$分就没了。回忆在考场上,思路是没有错的,就是发掘不够深入,思路还不够清晰。事实上考场上没有选择继续做这道题是对的,因为就算是我考后仔细分析之后,写完这道题仍然花了我不少时间。
我们可以循着思路一步步分析,一步步得到每一个性质。
题目中对其走过路径的字典序的比较提示我们按斜行分析。稍加思考我们就能得到一个明显的结论,就是对于某一个格子如果它是$1$,那它的右上角的那个格子就不能是$0$,这几乎就是题目条件的定义,因为有一条路径走到了这个格子,它就会在分叉的时候出问题。我们它这个性质总结一下就能得到我们需要的第一个结论:
1.对于每一个斜行,其$0/1$状态一定是存在一个分界点,使得其左下方都是$1$,其右上方都是$0$。
有以上的结论将大大减少每一个斜行的可行的$0/1$状态。我们接着思考,一对不合法的路径的出现,除了上述的情况,都可以归结为两条不同的路径以相同的$0/1$串走到了某一个格子,但是这个格子右边下边的两个格子的$0/1$是不同的,这同样会让矛盾出现。或许你会想这两条路径在$0/1$字典序出现分歧的时候并不一定在同一个格子里,但如果存在这种情况,那我们一定能找到前者所说的更加简单的情况。我们将形式地描述这个问题,我们称一个格子是“模糊”的,当且仅当存在两条不同的路径以相同的$0/1$串走到了这个格子。我们所发现的可以表述成:
2.如果某一个格子它左边上边的两个格子的$0/1$是相同的,或者它左边或上边有格子是模糊点,那这个格子就是模糊点;模糊点右边下边的两个格子的$0/1$必须相同。
这也是一个重要的结论,它为下一个结论的得到提供了一个有力的帮助。模糊点的传递性隐约让我们感觉到它们的排布不会错杂无序,事实上十分有规律。读者可以仔细推敲,利用归纳法简单证明以下结论:
3.去除第一行和第一列的格子后,每一条斜行最多只有一个格子是非模糊的,并且这个非模糊点一定在第二行或第二列。
这个性质令人惊讶,但它是真实的,并且不难证明。有了这个结论后,我们就可以有一个大致的想法,我们可以枚举整张图的模糊状态,状态数是$O(m)$的,因为斜行上一旦全是模糊点,接下来也一定都是模糊点。我们考虑对于一个给定的模糊状态,我们怎么去计算有多少$0/1$的填放方式满足整张图的模糊状态。假设我们枚举那个仅存的非模糊点最后出现在哪一个斜行,手模一下可以发现,为了保证这个非模糊点没有消失,前面的大多数斜行的$0/1$状态是唯一的,只有最开头的两斜行会有多种状态,并且为了让这个非模糊点在下一斜行中消失,这行和下一行的可行状态数也可以知道,那么算到这里方案数还是一个已知的常数。在非模糊点消失后,接下来每一斜行面临的决策都是一样的,对于后面的方案数只要快速幂即可。到这里为止,已经可以解决这道题了,利用此算法的复杂度是$O(mlogm)$。
讲到这里算法大致结束了。对于上述算法而言,我们枚举了非模糊点最后出现的位置然后算方案数,其算式的形式是相同的,我们可以把其中的式子化简一下,就能用等比数列求和直接算了,在此处当$n=m$的时候要求有$3$的逆元。所以,总复杂度为$O(logm)$。这道题的细节相当复杂,其中的有许多常数要手动算出来,也有一些角落需要特判,就算大致知道怎么做了之后实现起来也是不容易的。
这份代码是$O(mlogm)$的实现,写的时候也是有点逻辑顺序在里面的,总的来说是按照斜行的从上到下。可能其中有需要解释的地方,$C$函数用于求在$x + 1$斜行后全部都是模糊点的方案数的计算,one more case中是一个算非模糊点在第二列最后两个位置时特判,dd line是非模糊点在第$n$斜行的特判,last case是非模糊点在第二行最后两个位置时的特判。
#include <cstdio>
#include <algorithm> typedef long long LL; const int MOD = (int)1e9 + ; int n, m, ans, p2, p3; int Pow(int x, int b) {
int r = ;
for (; b; b >>= , x = (LL)x * x % MOD) if (b & ) r = (LL)r * x % MOD;
return r;
}
int C(int x) { // end by x, calc after
if (x >= m) return Pow(, n + m - x - );
if (x >= n) return (LL)Pow(, m - x) * p2 % MOD;
return (LL)Pow(, n - x) * p3 % MOD * p2 % MOD;
} int main() {
scanf("%d%d", &n, &m);
if (n > m) std::swap(n, m);
p2 = Pow(, n - );
p3 = Pow(, m - n);
if (n == ) {
printf("%d\n", Pow(, m));
return ;
}
if (n == ) {
printf("%lld\n", 4LL * Pow(, m - ) % MOD);
return ;
}
ans = (ans + 16LL * C()) % MOD; // on line 2
ans = (ans + ( + (n != ) + (m > )) * 4LL * C()) % MOD; // on line 3
for (int i = ; i < n; ++i) {
ans = (ans + 80LL * C(i + )) % MOD;
}
// one more case
if (n > ) {
if (n < m) ans = (ans + 32LL * C(n + )) % MOD;
else ans = (ans + 24LL * C(n + )) % MOD;
}
if (n < m) ans = (ans + 8LL * C(n + )) % MOD;
else ans = (ans + 6LL * C(n + )) % MOD; // dd line
if (n < m && n != ) ans = (ans + 32LL * C(n + )) % MOD;
for (int i = n + ; i < m; ++i) {
ans = (ans + 24LL * C(i + )) % MOD;
}
// last case
if (n > || m > ) {
if (n < m) ans = (ans + 18LL * C(m + )) % MOD;
else ans = (ans + 24LL * C(m + )) % MOD;
}
ans = (ans + 6LL * C(m + )) % MOD; printf("%d\n", ans);
return ;
}
这份代码是$O(logm)$的实现,其中把一些项合并过了,故而稍变简洁,但是无法从中得到具体的含义的。
#include <cstdio>
#include <algorithm>
using namespace std; typedef long long LL; const int MOD = (int)1e9 + ; int n, m, ans, p2, p3; int Pow(int x, int y) {
int r = , b = (y + MOD - ) % (MOD - );
for (; b; b >>= , x = (LL)x * x % MOD) if (b & ) r = (LL)r * x % MOD;
return r;
} int main() {
scanf("%d%d", &n, &m);
if (n > m) swap(n, m);
p2 = Pow(, n - );
p3 = Pow(, m - n);
if (n == ) ans = Pow(, m);
if (n == ) ans = 4LL * Pow(, m - ) % MOD;
if (n == ) ans = 112LL * p3 % MOD;
if (n > ) {
ans = (3LL * p2 + 21LL * Pow(, * n - ) % MOD * p3) % MOD;
if (n == m) ans = (ans + 27LL * p2) % MOD;
else ans = (ans + (24LL * p3 % MOD + ) * p2) % MOD;
ans = (ans + 80LL * p2 % MOD * Pow(, m - n - ) % MOD * (Pow(, n - ) - )) % MOD;
ans = (ans + 12LL * p2 % MOD * (Pow(, max(, m - n - )) - )) % MOD;
}
printf("%d\n", ans);
return ;
}
$\bigodot$总结:
对于这道题的我的做法,或许与大多数做法不一定相同,它并没有要求什么算法,甚至没有类可归,重要的是要细心耐心地思考与推导。
最新文章
- Angular2入门系列教程7-HTTP(一)-使用Angular2自带的http进行网络请求
- 趣说游戏AI开发:曼哈顿街角的A*算法
- python写2048小游戏
- 浪潮 NF5240M3 ,NP5540M3 服务器安装2008 R2
- CSS弹性盒模型flex在布局中的应用
- python 操作excel 使用笔记
- 网站如何提高PR值
- HTML5每日一练之input新增加的六种时间类型应用
- flash 入门课知识小结
- 使用VisualStudio进行单元测试之一
- MySQL 遇到的问题:在服务里找不到自己的 MySQL,以及在命令行窗口中运行服务出现的问题。
- 【剑指offer】面试题29:数组中出现次数超过一半的数字
- selenium + python自动化测试环境搭建--亲测
- Django项目创建02
- js分析 猫_眼_电_影 字体文件 @font-face
- java中移位运算
- BZOJ.1568.[JSOI2008]Blue Mary开公司(李超线段树)
- VS2010带不出System.Data.OracleClient这个引用的解决方案
- js检测来源网址,如果是搜索引擎跳转到新地址
- 量身打造自己的MyEclipse(多图)