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

温州中学一试解题报告


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


相关文章:
温州中学一试解题报告
温州中学一试解题报告 隐藏>> 【数的计数】首先这道题目可以暴力枚举通过 60%的数据。 假设 X 是一个 K 超级数, Y 为 X 各位 令数之和,则因为 X<=10^...
温州中学二试解题报告
32页 免费 必修一专题1 3页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 温州中学试解题报告 隐藏>> 【基因...
解题报告范例
IOI2010 国家集训队第二次作业 GCJ09 Final 解题报告 江苏省常州高级中学 吴翼 Doubly-sorted Grid GCJ09 Final Problem C 【简要描述】给出一个 N*M 的方格...
解题报告
解题报告 隐藏>> 物理教学中渗透学习策略与方法教育的研究焦作市实验中学课题组 ...然后让一位同学上台展示用温度计测水的温度,其他同学指出他操作 不当的地方,...
第一周解题报告
试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 理学第一周解题报告_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档第...
名校的数学解题报告一
《课程改革的操作策略》 报告人:杨昭 4、6 月 21 日下午 14:30——17:00...无论是邗江中学、13 中还是江苏锡山高中,虽然他们的叙述方式不一样, 但三校的...
解题报告
试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 IT/计算机 ...解题报告_计算机软件及应用_IT/计算机_专业资料。2012 级新生练习赛 1 A. Hello...
oj上机解题报告
oj上机解题报告_计算机软件及应用_IT/计算机_专业资料。C++基础的一些练习和解答 A.jhljx 上大学题目描述 JHLJX 数列,通项如下: JHLJXn = n/1! + n/2! ...
解题报告。
解题报告。 隐藏>> 实验前测分析一调查目的: 通过本次调查 ,解决以下问题:是...公主屯中学 2007 年 4 月 理论价值: 1教育与训练相结合为提高学生心理品质...
简单解题报告
小学生计算机知识竞赛解题报告 1.输入 N(n<=10000),输出 N 以内的整数,使其数字之和为 13,每行输出 8 个数。输出场 宽为 4 例如:数 85,其数字之和为 ...
更多相关标签:
noip2016解题报告 | 中学数学解题研究 | noip2015解题报告 | noip2015day2解题报告 | noip2016复赛解题报告 | 解题报告 | noip2014解题报告 | acm解题报告 |