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

温州中学一试解题报告


【数的计数】
首先这道题目可以暴力枚举通过 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),有兴趣的同学可以自行思考。


赞助商链接
相关文章:
推荐初中数学中考温州试题解析
试试 3 悬赏文档 全部 DOC PPT TXT PDF XLS ...推荐初中数学中考温州试题解析_中考_初中教育_教育...的展开图解题. 解答: 解:A、可以折叠成一个正方...
2016年浙江省温州中学自主招生化学模拟试卷
温州中学自主招生化学模拟试卷参考答案与试题解析 一、选择题(每题 3 分且仅 1 个正确答案,多选、错选、不选不得分,共 9 分) 1. (3 分) (2016?温州...
二次函数可能性温州中考题解析
试试 3 帮助 全部 DOC PPT TXT PDF XLS 广告 百度文库 教育专区 初中...二次函数可能性温州中考题解析_初三数学_数学_初中教育_教育专区。一.选择题(...
2007年浙江省温州中学高一自主招生考试物理试卷
2007 年浙江省温州中学高一自主招生考试物理试 卷一、选择题: (每题 4 分,共 16 分) 1. (4 分)一个物体放在光滑水平面上,初速为零,先对物体施加水平向东...
2014-2015学年浙江省温州中学高一(下)期末化学复习试卷...
2014-2015 学年浙江省温州中学高一(下)期末化学复习试卷(文科)一、单项选择题(...抓住是否有新的物质生成是 解题的关键. 6.制取下列物质,不能直接用乙烯作原料...
浙江省温州市2017年中考数学真题试题(含解析1)
2017 年浙江省温州市中考数学试卷一、选择题(共 10 小题,每小题 4 分,共 40 分) : 1.﹣6 的相反数是( A.6 B.1 C.0 ) D.﹣6 2.某校学生到校...
浙江省温州市中考数学试题解析
浙江省温州市 2011 年中考数学试卷 一、选择题(本...熟记公式是解题的关键. 12、 (2011?温州)某校艺术...2014年度细分行业报告汇集 2014年移动互联网O2O分析报告...
浙江省温州市永嘉县楠江中学2014-2015学年高一上学期第...
浙江省温州市永嘉县楠江中学2014-2015学年高一上学期第二次月考数学试卷_数学_...解题时要认真审题,仔细解答. 2.函数 f(x)= +lg(x+1)的定义域为( ) A...
浙江省温州市平阳县山门中学2015-2016学年八年级数学上...
试试 3 帮助 全部 DOC PPT TXT PDF XLS ...浙江省温州市平阳县山门中学2015-2016学年八年级数学...点是解题关键. 2.在直角坐标系中,点 A(2,1)...
浙江省温州市苍南县求知中学2016年物理选考模拟试卷(10...
浙江省温州市苍南县求知中学 2016 年物理选考模拟试卷(10 月份)(解析版) 一...运用动能定理解题关键选择好研究的过程,分析 过程中有哪些力做功,然后根据动能...
更多相关标签: