做生蚝的网站,永久免费做网站,时尚网站设计,柳城企业网站制作哪家好DeepinC的题解 考场AC nb%%%%%%%%%%%%%%%%%% 2019/4/27Day1 T3 奇怪的道路step1#xff1a;复杂度分析1 n 30, 0 m 30, 1 K 8.按照习惯#xff0c;正解复杂度一般在1e6-1e8级别而且往往复杂度关系最大的就是最小的那个数对#xff0c;抓住那个… DeepinC的题解 考场AC nb%%%%%%%%%%%%%%%%%% 2019/4/27Day1 T3 奇怪的道路step1复杂度分析1 n 30, 0 m 30, 1 K 8.按照习惯正解复杂度一般在1e6-1e8级别而且往往复杂度关系最大的就是最小的那个数对抓住那个k8打所以说先蒙个复杂度Omnk?太小Omn*2^k这个差不多所以试试状压step2算法算法一其实看到这么小的数据范围应该也能 感受一下 状压的气息吧[任何一个城市都与恰好偶数条道路相连0也被认为是偶数]奇数偶数可以用0,1两种状态表示这很状压这非常状压设dp[n][m][state]表示已经考虑了n个城市m条道路所有城市状态为state时的情况数如果你把n和p连起来n-kpn (pow[i]表示2的i次方)则 dp[n][m][state]dp[n][m-1][state^pow[n]^pow[p]];异或超棒的当你连上一条路时两个端点已经连上的路原来是奇数的就变成偶数偶数就变成奇数题库里内存128M考试时内存256Mstate太占内存大概能处理n15一半分算法二优化我说过那个最小的k是突破口吧但是用上了吗根据复杂度分析如果把那个2^n替换成2^k就可以了那么就要把state的位数变成k仔细一看刚好合适那么state的含义稍微一变最后k座城市的状态交线牛逼法很好啊因为第i座城市的状态转移只与最后k座城市有关NOI2019 Day2 T1 mentor:中国好码农ing...码出来的时候忽然发现一个问题我没考虑当前城市的情况所以state的大小其实是2^(k1)王鹤松式没关系没关系复杂度更接近上限了正确的可能性更高了玄学信仰状态转移的式子稍微一改 dp[n][m][state]dp[n][m-1][state^1^pow[n-p]];而且因为state的表示范围在变化所以对于每个ndp值都需要特殊转移 dp[n][m][state1(pow[k1]-1)]dp[n-1][m][state];dp[n][m][0]即为答案算法三无关紧要的优化时间小优化 我是个听学长话的乖孩子。。。。。。 他说过取模超级慢的是嘛 怎么避免取模呢减法优于取模判断优于计算 inline long long mod(long long k){return k1000000007?k-1000000007:k;} 因为代码里只存在加法所以计算结果不会超过1000000007*2减去一个1000000007就行了空间大优化 为什么只有256M啊NOI还有5G呢 可见dp式子只从n-1转移到n 滚动数组棒 式子再稍微一改 dp[i1][j][s]mod(dp[i1][j][s]dp[i1][j-1][s^1^pow[i-p]]) dp[(i1)^1][j][s1]dp[i1][j] 滚起来别忘了清空数组 dp[i1][j][s]0;编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间#57153 #C. 奇怪的道路 Accepted 100 67 ms 616 KiB C11 / 754 B DeepinC (吴迪) 2019-04-27 21:46:3420个测试点时间还不错k8的话目测可以处理mn300 代码 转载于:https://www.cnblogs.com/znsbc-13/p/11268465.html
