SPOJ16636 Journey IE2
2024-09-07 11:49:49
SPOJ16636 Journey IE2
更好的阅读体验
在Byteland有n个城市,编号从1到n。这些城市由m条双向道路网络连接。众所周知,每一对城市最多只能由一条道路连接。
Byteman最近承认,他喜欢某些城市多于其他城市。更确切地说,他在数字为1到k的城市中花费的时间特别多,所以在每次旅行中,他至少要访问其中的每个城市一次。
Byteman的旅程是一个由d个城市组成的序列,使得每一对连续的城市都由一条道路连接。旅程可以在任何城市开始和结束。你的任务是计算Byteman可以围绕Byteland进行的不同旅程的数量。因为这个数字可能相当大,所以只需找到1e9+9的模数即可。
- 题目来源:SPOJ16636 Journey IE2
- 算法一:
- 我会暴力!
- 复杂度 \(O(nd)\) 期望得分20
- 算法二:
- 在之前基础上特判k=0 DP+矩阵优化
- 设 \(f(i,j)\) 为 \(i\) 时刻在城市 \(j\) 的方案数,然后矩阵乘法优化
- 复杂度 \(O(n^3\log_2d)\) 期望得分30
- 算法三:
- 对于测试点3、4 状压DP
- DP 时除了记录当前点,再记录关键城市是否到过
- 我故意把这几个点的数据做得较水,应该能过
- 复杂度 \(O(dnm \times 2^k)\) 期望得分50
- 算法四:
- DP+矩阵优化+容斥
- 同算法2 的DP,先暂且不理k 个重要城市,构建矩阵
- 用容斥解决重要城市的问题,由于 \(k\) 最多只有 \(7\),所以 \(2k\) 枚举重要城市{可以经过/强制不能经过},强制不能经过只需在构建矩阵时无视与这个城市相连的边就行了
- 最后 ans=f 强制关闭0 个重要城市-f 强制关闭1 个重要城市+f 强制关闭2 个重要城市-f 强制关闭3 个重要城市 +... ...
- 复杂度 \(O(n^3\log_2d \times 2k)\) 期望得分100
- 算法五:
- 这个位置留给大家了
- 我的算法在SPOJ 上总运行时间17.24s 垫底,rank1 的运行时间1.75s
- 所以我的做法显然不是标准算法
最新文章
- Best Coder Round#25 1003 树的非递归访问
- Flip Game poj1753
- ExpandableListView 箭头靠右
- (POJ 3694) Network 求桥个数
- [转载]再次谈谈easyui datagrid 的数据加载
- careercup-中等难度 17.3
- MVC(Model View Controller)框架
- YII 1.0 (7) 登录信息调取 session使用
- jquery.validata.js 插件2
- [转]Oracle High Water Level高水位分析
- 基础才是重中之重~delegate里的Invoke和BeginInvoke
- 46.Scrapy框架结构
- proc文件系统、sysfs文件系统、kobject操作
- eslint 入门学习
- spark sql 中的结构化数据
- 优美的爆搜?KDtree学习
- 为什么GPU可以用于科学计算【转载】
- e621. Activating a Keystroke When Any Child Component Has Focus
- N-gram语言模型与马尔科夫假设关系(转)
- VMware下拷过来的Linux系统ifconfig下没有网络问题