tceic.com
学霸学习网 这下你爽了
相关标签
当前位置:首页 >> IT/计算机 >>

NOIP2010题解报告(普及组&&提高组)


2010.11

NOIP2010 题解报告

太原成成中学张浩千

NOIP2010 题解报告
提高组 No.1 机器翻译
时间及空间复杂度 时间复杂度:O(NM) 空间复杂度:O(M) 时间复杂度:O(N) 空间复杂度:O(M) 题解 方法一:模拟整个机器翻译的过程, 判断某一元素是否在当前内 存中,可以采用顺序遍历整个内存的方式来处理。预期分数 100 分 方法二:如果将题目 N、M 的数据范围改成 100000,那么方法一 就会因超时而挂掉,这时我们可以根据题目中说每个数都不超过 1000 来优化算法,我们可以建立一个标记数组(hash 表)来判断 i 是否在内存中。预期分数 100 分 方法三:如果将题目 N、M 的数据范围改成 100000 且每个数都不 会超过 maxlongint,那么方法二也同样会挂掉,我们可以继续改进 算法,我们可以将每一个数都 mod 一个质数,然后根据这个质数 建立链表(hash 表) 。预期分数 100 分

时间复杂度:O(N) 空间复杂度:O(M)

提高组 No.2 乌龟棋
时间及空间复杂度 时间复杂度:O(M!) 空间复杂度:O(N) 时间复杂度:O(NM^4) 空间复杂度:O(NM^4) 题解 方法一:枚举每一张卡片的使用顺序,对于每一种顺序求的当前的 解,保留最优解即可。预期分数 30 分 方法二:使用动态规划算法。用 f[I,j1,j2,j3,j4]表示前 i 个格子,用 j1 张 1 号卡片,j2 张 2 号卡片,j3 张 3 号卡片,j4 张 4 号卡片所得到 的最优值,则 F[I,j1,j2,j3,j4]=A[i]+max{F[i-1,j1-1,j2,j3,j4], 当 j1>0 F[i-1,j1,j2-1,j3,j4], 当 j2>0 F[i-1,j1,j2,j3-1,j4], 当 j3>0 F[i-1,j1,j2,j3,j4-1]} 当 j4>0 边界条件 f=-oo f[1,0,0,0,0]=0 最后结果 f[n,tot[1],tot[2],tot[3],tot[4]] tot[i]表示第 i 种棋的个数 预期分数 50 分 方法三:方法二在表达状态上有浪费,因为 j4 根据 I,j1,j2,j3 的关系 就可以算出来,则现在的转移方程式变为 F[I,j1,j2,j3]=A[i]+max{F[i-1,j1-1,j2,j3], 当 j1>0 F[i-1,j1,j2-1,j3], 当 j2>0 F[i-1,j1,j2,j3-1], 当 j3>0 F[i-1,j1,j2,j3]} 当(i-j1-2*j2-3*j3) div 4<=tot[4] 边界条件 f=-oo f[1,0,0,0]=0 最后结果 f[I,j1,j2,j3] 预期分数 100 分

时间复杂度:O(NM^3) 空间复杂度:O(NM^3)

2010.11

NOIP2010 题解报告

太原成成中学张浩千

时间复杂度:O(M^4) 空间复杂度:O(M^4)

方法四: 方法三在表达状态上依然有浪费, 因为 i 可以通过 j1,j2,j3,j4 的关系算出来,而 i>=j4,这样我们就得到了比方法三更优的算法 用 f[j1,j2,j3,j4]表示已经使用了 j1 张 1 号卡片,j2 张 2 号卡片,j3 张 3 号卡片,j4 张 4 号卡片,所得到的最优质,则 F[j1,j2,j3,j4]=A[1+j1+j2*2+j3*3+j4*4]+max{F[j1-1,j2,j3,j4], 当 j1>0 F[j1,j2-1,j3,j4], 当 j2>0 F[j1,j2,j3-1,j4], 当 j3>0 F[j1,j2,j3,j4-1]} 当 j4>0 边界条件 f=-oo f[0,0,0,0]=a[1] 最后结果 f[tot[1],tot[2],tot[3],tot[4]] 预期分数 100 分

提高组 No.3 关押罪犯
时间及空间复杂度 时间复杂度:O(2^N) 空间复杂度:O(N^2) 时 间 复 杂 度 : O(Mlog(10^9)) 空间复杂度:O(M) 题解 方法一:枚举每一个人是在第一个监狱或第二个监狱,用邻接矩阵 来存图,找到每一种情况的解,保留最优解即可。预计分数 30 分 方法二:由于 M 过大,且为稀疏图,这样我们可以采用链表的方 式去存储。如果直接求解不好求,那么我们可以尝试去判断一个解 是否成立。这个过程与猜数游戏非常类似,如果猜大了,那么你就 往高猜,如果猜小了,那么你就往低猜,这样每次分段的时间复杂 度 为 O(log(N)), 判断是否 为解 需要 O(1) ,故 总时 间复 杂度 为 O(log(N))。对应到这个题目,如果我们判断一个解的时间复杂度比 较低的话,就可以采用二分答案的方式。判断一个解是否成立,我 们可以判断哪些人不能和这个人分成一组, 既判断这个图是否为二 分图,我们可以采用染色的方式,1 号犯人颜色为 1,则如果连接 1 号犯人的人边权大于我们猜到的值,则这个犯人颜色为 2,反之 颜色为 1,对于其他犯人也做类似处理。如果在这个过程中没有发 生冲突(指本次需要染一种颜色,但是这个犯人本身已经有另一种 颜色的情况) ,则表明猜数猜小了,反之为猜大了或猜中了。 预期分数 100 分 方法三:本题虽然可以二分去做,但是是经典的 2-sat 问题,所有 的点分成两个集合。 把每一个点拆成 0 和 1 两个点,如果有边相 连接,则 a0 与 b1 相连,a1 与 b0 相连,b0 和 a1 相连,b1 与 a0 相连。我们按照边权从大到小排序,依次插入,如果出现了环(a0 与 a1 相连) ,则出现了矛盾。上述过程可以使用并查集去维护。 预期分数 100 分

时间复杂度:O(MlogM) 空间复杂度:O(M)

2010.11

NOIP2010 题解报告

太原成成中学张浩千

提高组 No.4 引水入城
时间及空间复杂度 时间复杂度:O(NM) 空间复杂度:O(NM) 时间复杂度:O(NM) 空间复杂度:O(NM) 题解 方法一: 只考虑无解的情况, 将每一个(1,i)作为起点, 进行 Flood Fill, 如果(n,i)有遍历不到的情况,则直接输出答案。预期分数 30 分 方法二:只考虑无解和 N=1 时的情况。对于 N=1 时,我们可以用 排序求出第 i 大海拔高度的位置,按照海拔高度从大到小的数进行 处理,如果当前节点还没有被访问,则这个节点向左和向右扩展, 直到全部节点都被访问时, 输出解。 这样的贪心策略一定是正确的, 因为如果海拔高度高的节点能遍历到海拔高度低的节点, 那么这个 海拔高度低的能遍历到新的节点海拔高度高的节点也一定能遍历 到。在结合方法一,预期分数 40 分 方法三:只考虑无解、N=1、M<=20 的情况。对于 M<=20,因为一 定有解,我们可以枚举子集的办法将所有情况列出来,对于每种情 况进行一次 Flood Fill,取最优解即可。预期分数 60 分 方法四:首先需要用到一个结论,如果(1,i)能遍历到(n,i)的某些点, 那么这个区间一定是连续的。用反证法,对于其逆命题,如果这个 区间不是连续的,假设现在分成两段。如下图,从红色节点出发, 到达最后一行的区间会被紫色节点(表示不可到达)所分成两段

时间复杂度:O(2^M) 空间复杂度:O(NM) 时间复杂度:O(NM^2) 空间复杂度:O(NM)

时间复杂度:O(NM) 空间复杂度:O(NM)

由于一定可以由第一行的节点访问到紫色节点, 那么这个节点访问 到紫色节点的路径中一定会包含红色节点所遍历到的路径 (图中的 绿色路径) ,从而证明了假设不成立,则原命题成立。 下面我们可以将问题分成两个部分: 1. 求(1,i)的某个节点能控制到(n,i)的区间[st[i],ed[i]] 2. 使用最少的区间使整个线段遍历 对于第一问, 我们只需要枚举每一个第一行的点做一次 Flood Fill 即可。 时间复杂度为 O(NMM) 对于第二问,可以使用动态规划的方法来做,设 f[i]覆盖前 i 段, 需要最少的几个区间,则转移方程为 F[i]=min(st[i]-1) 当 st[i]<=i<=ed[i] 边界条件 f=-oo f[0]=0;最终答案 f[m] 时间复杂度为 O(NM) 预期分数 90-100 分 方法五:对于方法四,我们可以继续优化求(1,i)的某个节点能控制 到(n,i)的区间[st[i],ed[i]],如果从第一行求不方便,我们就可以从最

2010.11

NOIP2010 题解报告

太原成成中学张浩千

后一行开始求,由于 st[i]和 ed[i]求的方法类似,在这里只介绍 st[i] 的求法。按照(n,1)到(n,m)的顺序进行 Flood Fill(注意这里遍历条件 和第一行往第 N 行的条件相反) ,将遍历到的节点标记,以后遇到 这个节点直接 break,如果能遍历到第 1 行的某个节点,则 st[i]就 为起点(n,i)的 i 值。这样做的原因是,如果(n,i)为起点是第一个遍历 到 (1,k),则 st[K]=i 一定是最小的。这样在最坏情况下每一个节点 仅会被访问一次,所以时间复杂度为 O(NM)。预期分数 100 分

普及组 No.1 数字统计
时间及空间复杂度 时间复杂度:O(N) 空间复杂度:O(1) 时间复杂度:O(1) 空间复杂度:O(1) 题解 方法一:直接用一个循环枚举 l 到 r 的所有数,对每一个数字进行 判断(判断的方式有:转成字符串,一直 mod 10 等方法求的 2 的 出现次数) 。预期分数 100 分 方法二:如果数据范围改成<=10^10,那么方法一必然超时。采用 动态规划的算法,用 f[i]表示 0 到 10^i-1 中出现 2 的次数,则 F[i]=1 当 i=1 时 F[i]=f[i-1]*10+10^(i-1) 当 i>1 时 因为 ans=count(r)-count(l-1) count(k)表示 1-k 之间出现 2 的次数和 下面模拟 count(3292)时的情况: 把千位为 3 分成三种情况: 1. 千位为 0,1(0 相当于没有千位) f[3]+f[3] 2. 千位为 2 f[3]+1000 3. 千位为 3 继续算 292 时的情况 把百位为 2 分成三种情况: 1. 百位为 0,1 f[2]+f[2] 2. 百位为 2 92+1+继续算 92 的情况 ?? 全部累加以来即 count 的值 预期分数 100 分(相关加强版在 tyvj-P1409)

普及组 No.2 接水问题
时间及空间复杂度 时间复杂度:O(不好估 计) 空间复杂度:O(N) 时间复杂度:O(NlogM) 空间复杂度:O(N) 题解 方法一:按照时间来模拟,每次将时间加 1,如果有同学的水加满 后,则让下一个未接水的同学过来接水。预期分数 100 分 方法二:其实我们仅需要关注换人的一瞬间,其他时间没有任何意 义。 我们用 a[i]表示第 i 个水龙头需要放水的量, 则初始情况 a[i]=w[i]

2010.11

NOIP2010 题解报告

太原成成中学张浩千

(i∈m),每次换人的时候,肯定是 a[i]最小的那个水龙头(因为需 要放的水最小, 所需要的时间就最小) 将这个 a[i]加上下一个需要 , 接水的同学的时间,最终找到最大的 a[i]既是本题的解。于是本题 变成了一个 RMQ(求区间最大最小值)的问题,可以采用线段树、 堆、ST 算法等。 预期分数 100 分(相关加强版本在 tyvj-P1405)

普及组 No.3 导弹拦截
时间及空间复杂度 时间复杂度:O(1) 空间复杂度:O(1) 时间复杂度:O(2^N) 空间复杂度:O(N) 时间复杂度:O(N^2) 空间复杂度:O(N) 题解 方法一: 仅考虑 N=1 的情况, 只需要判断距离哪一个拦截导弹系统 近即可。预期分数 10 分 方法二:仅考虑 N<=2 的情况,枚举哪一些被 1 号系统拦截,另外 的被 2 号系统拦截。预期分数 20 分。 方法三:算出所有导弹距离第一个拦截系统、第二个拦截系统的距 离,升序排序后,枚举第一个拦截系统能拦截到的最大距离,剩下 的由第二个拦截导弹系统进行拦截, 顺序查找剩下的导弹距离第二 个拦截导弹系统的最远距离。预期分数 70 分 方法四:如果说排序后[1,i]由第一个拦截系统拦截,则[i+1,n]就由 第二个拦截系统拦截, 方法三的瓶颈在于寻找由第二个拦截导弹系 统最远的那个导弹的距离,这个问题显然是一个 RMQ(区间最大 最小值)问题,可以采用线段树、ST 算法等,但是本题目具有很 大的特殊性,可以采用动态规划做预处理。 用 f[i]表示后 i 个导弹距离第二个拦截系统的最远距离,则 F[i]=max(f[i+1],b[i]) b[i]第 i 个导弹距离第二个拦截系统的距离 预期分数 100 分。

时间复杂度:O(NlogN) 空间复杂度:O(N)

普及组 No.4 三国游戏
时间及空间复杂度 时间复杂度:O(N^2) 空间复杂度:O(N^2) 题解 方法一:小涵总会赢,因为计算机仅仅是对小涵的操作进行阻碍, 并不能得到试自己处于有利地位的。可以用反证法证明,假设计算 机会赢, 那么根据小涵是优先选择, 一定可以选择到计算机的策略, 故计算机是不可能赢的。小涵一定会赢的情况下,要求武将最大的 默契值最大,最大的默契值一定可以在小涵最先选择的两个人选 出,因为如果后面出现,也一定可以“平移”到最前面,所以我们 只需要考虑前两个人的选取即可。 我们可以先枚举一个小涵最先选 择的武将 i,根据计算机的规则,他一定会阻碍小涵产生最大武将 默契值的那个武将,于是小涵为了武将默契值最大,只能去选择与 武将 i 产生次大的武将默契值才行。于是本题的问题变成了找最大

2010.11

NOIP2010 题解报告

太原成成中学张浩千

的次大值。预期分数 100 分。


推荐相关:

NOIP2010提高组解题报告

NOIP2010提高组解题报告_经济学_高等教育_教育专区。NOIP2010提高组解题报告今日推荐 78份文档 笑翻神图 爆笑图片汇集 搞笑图片乐翻人 cs3简单制作动态搞笑图片104份...


NOIP2010解题报告

NOIP2010普及组个人解题... 9页 免费 全国信息学奥林匹克联赛... 6页 免费 NOIP2010提高组解题报告... 2页 免费 NOIP2010提高组结题报... 9页 免费喜欢...


NOIP2010普及组初赛试题答案C++

[i]=RIGHT; } NOIP2010 初赛 提高组 C++ 9 cout<<go[RIGHT_TO_LEFT)<<endl; return 0; } NOIP2010普及组(C++语言)参考答案与评分标准 普及组 语言)...


NOIP2010普及组复赛试题

NOIP2010普及组复赛试题_初三数学_数学_初中教育_教育专区。NOIP2010普及组复赛试题 全国信息学奥林匹克联赛( 全国信息学奥林匹克联赛(NOIP2010)复)赛 普及组(请...


1NOIP2010普及组C++

NOIP 2010 试题与解题报告 NOIP 2010 初赛试题( 普及组 C++语言 ) 语言●● 全部试题答案均要求写在答卷纸上, 全部试题答案均要求写在答卷纸上,写在试卷纸上一...


NOIP2010普及组C

NOIP 2010 试题与解题报告 NOIP 2010 初赛试题( 普及组●● C 语言 两小时完成 ) 全部试题答案均要求写在答卷纸上,写在试卷纸上一律无效 ●● 一、单项选择...


NOIP基本程序题集解题报告

Noip 2010普及组解题报告 5页 2财富值 Noip 2003 提高组 解题报告... 12页...一元三次方程的解 这一题的方法很多,因为精度要求不高的缘故,所以无论二分...


NOIP2010普及组(Pascal语言)参考答案与评分标准

NOIP2010普及组(Pascal语言)参考答案与评分标准_理学_高等教育_教育专区。NOIP2010普及组(Pascal语言)参考答案与评分标准 NOIP2010提高组(Pascal语言)参考答案与评分标...


2010解题报告

集训队2010 『最大收益』解... 42页 5财富值 Noip 2010普及组解题报告 5页...全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第 3 页共 7 页 【输入输出...


noip2010提高组解题报告

Noip2010 反观 2010 年的提高组题目:第一题机器翻译是一道纯模拟的题目, 第...2003提高组,解题报告 15页 免费 NOIP2010普及组个人解题... 9页 免费 全国信息...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com