当前位置:首页 >> 学科竞赛 >>

温州中学一试解题报告


【数的计数】
首先这道题目可以暴力枚举通过 60%的数据。 假设 X 是一个 K 超级数, Y 为 X 各位 令 数 之 和 , 则 因 为 X<=10^18 , 所 以 Y<=18*9=162 , 因 为 YK 被 X 整 除 , 所 以 X<=YK<=162*1000=162000。 事实上再暴力枚举就可以通过所有数据了。 通过此方法进一步

计算,实际上 X<=38000,暴力枚举可以轻松通过 100%的数据。

【跑路】
朴素的方法是 F[i][j]表示到了第 i 个点,j 距离是否可能。最后扫一遍 F[n][j],取最优值 即可。由于 50%的数据有最优路径长度不大于 1000,所以 j<=1000,总效率 O(1000n^2), 可以拿到这 50 分。 标准方法类似倍增。 F[i][j][k]表示 i 到 j 长度为 2^k 的路径是否存在, 可以通过类似 floyed 的方法预处理:F[i][j][k]=F[i][j][k] or F[i][u][k-1] and F[u][j][k-1]。因为跑路先长后短还是先 短后长并不影响,所以不妨走长的路径,再走短的路径。然后进行一次动规,G[i][j]表示走 到第 i 个点,上次跑路的长度至少为 2^j,由于两次跑路长度相同必然不优,所以这次决策 或是不走,j-1,或是走,G[u][j-1](F[i][u][j-1]=true)被 G[i][j]+1 更新。最后 G[n][0]即为所 求答案。因为路径长度<=maxlongint 所以该算法总效率为 O(30*n^3),可以通过所有数据。

【RP 字符串】
这道题目可以用动态规划的方法解决。F[i][j]表示原串[i,j]这段区间是否是一个 RP 字符 串, 便得到方程 F[i][j]=F[i][j] or F[i+1][k] and F[k+1][j-1] and (a[i]=”1”) and (a[j]=”1”), 表示[i,j] 这段区间是 RP 字符串的充要条件是 a[i]=”1”, a[j]=”1”且存在一个 k(i+1<=k<=j-1)满足[i+1,k], [k+1,j]区间均是 RP 字符串。最后 F[1][n]即为我们所求的答案。这样我们就得到了一个总状 态数 O(n^2),转移效率 O(n)的算法,算法复杂度为 O(n^3),由于系数很小可以通过 30%的 数据。 事实上并不是所有的状态都有用, 所以对于这道题目, 也可以用记忆化搜索的方法解决, 由于没有使用到所有的状态,虽然算法的复杂度仍为 O(n^3),但算法的效率进一步提高, 可以通过 50%的数据。 原方法状态数已不可改变,想要提高算法的效率,必须加快转移的效率。事实上,对于 F[i][j],我们只关注是否存在一个 k 使得 F[i+1][k] and F[k+1][j]=true。令 G[i][j]=F[i+1][j], 则原式可转化为 F[i+1][k] and G[k][j]。 因为我们只关注是否存在 k 使 F[i+1][k] and G[k][j]>0, 所以我们使用位运算优化,将 k 以 31 个为一组压进一个 longint,成组完成 and 操作,只要 有一位为 true,这一组的值就大于 0,这样就可以快速判断。这样转移的效率就是 O(n/31), 比原来快了 31 倍。算法复杂度为 O(n^3/31),可以通过所有测试数据。 动态规划的复杂度几乎已经到达下限, 现在我们考虑模拟的方法。 0 表示一个合法的 用 串,假如存在’1001’,那么它肯定是一个合法的串且不会是其他合法串的一部分(因为存在 连续的两个 0) 所以我们把所有’1001’的串转化为’0’, 。 然后继续做下去, 直到原串转化为’0’ 或找不到’1001’为止。这样的总效率是 O(n^2)可以通过所有测试数据。 事实上,这种方法可以通过链表优化到 O(n),有兴趣的同学可以自行思考。


相关文章:
NOIP2015普及组复赛解题报告
NOIP2015普及组复赛解题报告_学科竞赛_初中教育_教育专区。NOIP2015普及组复赛解题报告 NOIP2015 普及组解题报告南京师范大学附属中学树人学校 CT 1. 金币(coin.cpp/...
NOIP2015提高组day1第二题解题报告
NOIP2015提高组day1第二题解题报告_学科竞赛_高中教育_教育专区。NOIP2015提高组...但和考 试时写的几乎一样,文件输入输出已注释) (visit 数组这里简化成了 vis...
NOIP2015普及组复赛试题解题报告word版第一二题满分程序
NOIP2015普及组复赛试题解题报告word版第一二题满分程序_学科竞赛_初中教育_教育专区。NOIP2015普及组复赛试题解题报告word版第一二题满分程序 ...
Noip 2013 Day1 解题报告
Noip 2013 Day1 解题报告_学科竞赛_高中教育_教育专区。Noip 2013 Day1 解题报告Noip 2013 Day1 解题报告 --By GreenCloudS 第一题:转圈游戏(快速幂)根据题目...
...程序设计竞赛复赛试题(初中组)解题报告(1)
宁波市第29届中小学生程序设计竞赛复赛试题(初中组)解题报告(1)_学科竞赛_初中教育_教育专区。宁波市第29届中小学生程序设计竞赛复赛试题(初中组)解题报告(1)宁波...
noip 2012 提高组 解题报告
试试 3 帮助 全部 DOC PPT TXT PDF XLS ...noip 2012 提高组 解题报告_学科竞赛_高中教育_教育...借教室二份答案+前缀和 1. 按订单将答案二分,...
NOIP2008普及组复赛试题与解题报告
试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 初中教育 学科...NOIP 2008 普及组解题报告一、ISBN 号码(isbn.pas/c/cpp) 【问题描述】 每...
NOIP2014普及组解题报告
NOIP2014 普及组复赛解题报告本人是潍坊一中的 wyw,69 级,今年高一, 现在马上就要 NOIP 了, 打算把历年的 NOIP 普及、提高组题目都做一下, 然后写写解题 报告...
NOIP2015普及组解题报告
试试 3 帮助 全部 DOC PPT TXT PDF XLS ...NOIP2015普及组解题报告_学科竞赛_初中教育_教育专区...样例 1 样例输入 1 6 2 5 5 3 2 2 2 2 2...
高三女生学习物理障碍研究解题报告
试试 7 悬赏文档 全部 DOC PPT TXT PDF XLS ...高三女生学习物理障碍研究解题报告_理化生_高中教育_...1 页共 4 页 高三女生学习物理障碍研究结题报告...
更多相关标签:
中学数学解题研究 | 区间众数解题报告 | 解题报告 | acm解题报告 | poj解题报告 | 中学数学解题研究pdf | noip2016解题报告 | 中学数学解题网 |