[THUPC2018]生生不息(???)
2024-09-01 12:17:42
SB题,写来放松身心。
首先 $n,m\le 5$,这是可以打表的。
本地怎么对于一个 $n,m$ 求答案?此时虽然复杂度不需要太优,但是还是得够快。
一个想法是枚举每个初始状态,不停模拟。因为总状态数只有 $O(2^{nm})$ 种,所以会出现周期。
如果压缩状态,复杂度是 $O(4^{nm}nm)$。太大了。
但是,虽然一个状态的周期可能很长,但是如果一起考虑所有状态呢?
对于每个状态 $S$,直接模拟它下一轮会变成啥(设为 $T$)。那么连一条 $S\rightarrow T$ 的边。
那么就是问有多少个边走不到 $0$。
可以建反图,计算从 $0$ 能走到多少个点。
复杂度 $O(2^{nm}nm)$。除了 $n=m=5$ 的点大概要跑 10s,其它的都可以 1s 出。
代码就没必要放了。
最新文章
- SQLServer2005+分页SQL
- 【58测试】【贪心】【离散】【搜索】【LIS】【dp】
- BZOJ1051 受欢迎的牛
- 使用JS制作一个鼠标可拖的DIV(三)——移动带图片DIV
- was服务器下修改jsp无效果
- Linux基础(七)
- HAproxy功能配置
- java总结之基础类型与常量池
- SQL插入数据--数据中的某一列来自本表中的数据
- 【转】Android开发笔记(序)写在前面的目录
- reduce函数
- NOIP经典基础模板总结
- windows mysql 的myini
- java读取视频文件时长
- CentOS7初始化mysql库报错
- 第五周 PSP 燃尽图 以及 进度条总结
- WebLogic 11gR1修改jdk版本
- STL源码分析归档
- 23_java之IO操作
- [转载]uml 类图依赖与关联的区别