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

noip模拟试题与解析


何朴藩 山东2012 hpfdf@126.com

? ? ? ?

?

题目大意 在一个106长度的字符串上统计STAR出现的 个数 1.求s*t*a*r 2.求min(s,t,a,r) 3.求最多能选出多少子序列”STAR”

? ? ? ?

考察点 综合基本功 文件名

看清楚题,不要弄反输出顺序 注意输出的答案范围,高精度乘法 优化算法时间复杂度(第三问)

?
?

? ? ? ?

考试情况

?
? ?

?
?

100分 90分 80分 70分 60分 50分 ……………… 10分

11人 6人 7人 1人 1人 12人
31人 ←囧

? ? ?

第三问:求最多能选出多少子序列

模拟法:每次选最前的,O(N2) 扫描法: 统计s,t,a,r出现的次数; 若某一时刻s < t,则至少有一个”T”用不了; 同理,维护s ≥ t ≥ a ≥ r; 最后r即为答案。O(N)

? ? ?

例题:最优子串相关问题

求数列A的一个连续子串使得
1.平均值最大 2.和最大 3.相邻项差的平均值最大

?
?

? ? ? ?

例题:最优子串相关问题·解

平均值最大:选最大值即可= =|||
相邻项差的平均值最大:一定相邻(ural1010) 和最大:扫描右界,维护左界

?

All in O(N)

? ?

例题:最短全子串

求一个字符串S中最短的连续子串,使得包 含26种不同小写字母。|S|≤106 以字符集{a,b,c}为例 ababacc ababacc

?
? ?

? ? ?

例题:最短全子串·解

?
?

初始时左界p=1,右界q=1 不断增加q,用 count[’a’…’z’] of longint 统 计子串中字母出现的个数。 如果S[p]出现多余一次,那么删掉也无妨。 一次一旦count[S[p]]>1就inc(p) 这样能求出以每个位置为右界的最短全子 串,取全局最小值即可。

? ? ?

题目大意

已知无向图和P,Q,边权为二元组(a,b) 求x,y使得(a≤x,b≤y)边连通整个图 且Px+Qy最小
N≤200,M≤40000,数据≤109

?

? ? ? ?

考试情况

50分 20分 10分

1个 5个 1个

李成志-胜利一中

? ?

考察点:最小生成树,图,连接表

从小到大枚举x,在所有满足a≤x的边中按b 求最小生成树。若用Prim算法,复杂度为 O(N2M)
优化:每次只把新的边连接的点,与对应 树上连通这对点路径的b最大值比较。需要 支持删除边的数据结构。O(NM)

?

? ? ?

常用技巧:部分和与差分(离散积分/微分)

水题新解:校门外的树
马路长度为L,每次将[x,y]种上树,共Q次 最后有多少棵树?L,Q≤106 Inc(D[x]); dec(D[y+1]);

?

? ? ?

常用技巧:部分和与差分

?

?

例题:聪明的商贩 某国的城市河流网络可以看成一个有向无 环图。花瓶每个城市的交易价各不相同。 商人的船从1城市开始,只能顺水行进。同 时只能持有1个花瓶 。商人可以选择道路买 进或卖出花瓶。求最大可能收益。 N,M ≤ 105

? ?

常用技巧:部分和与差分

例题:聪明的商贩
60 50 10 40 20 20 Sell 5 Buy 80 Sell

Buy

? ? ? ?

例题:聪明的商贩·解

标记边权(u,v)为max(0, Cost[v]-Cost[u])
从1开始的最长路即是答案
50 0 40 20 0 20 20 0 5 20 60

BFS即可 O(N+M)

10

40 10

15
75 80

? ? ?

例题:全零子矩阵

输入一个NxM的01矩阵,

?
?

1.求最大全零子矩阵 2.求全零子矩阵的个数 3.Q次询问包含某格子的全零子矩阵个数

0000100001011 0110100001001 1011000001111 1010010000000 1001110100000

?

N,M ≤ 1000 ; Q ≤ NM

? ? ?

例题:全零子矩阵·解

从上到下,从左到右枚举 维护up[i,j]表示(i,j)往上走有多少连续的零 通过对up[i]数组的扫描,可求出以(i,j)为右 下角的全零子矩阵个数或最大面积

?

? ?

例题:全零子矩阵·解

0000100000100000 0100011000000010 0001000000000000 0100000000001000 0000000010000000 4041322444330222 ← Up[4][] 00112224 ← SuffixMin

?
?

?

00001000 01000110 00010000 01000000

?
?

4041322444330222 ← Up[4][] 00112224 ← SuffixMin 用栈维护SuffixMin DR[4][8]=Sum{SuffixMin}=12

? ?

? ? ? ?

例题:全零子矩阵·解

求包含一个点的全零子矩阵个数 O(N2)-O(1)
同上扫描法求出DR[i,j]表示右下角为(i,j)的 全零子矩阵个数,同理求DL,UL,UR 通过DL和DR做扫描可求出D[i,j]表示底边过 (i,j)的全零子矩阵个数,同理求出U 通过D和U的扫描求出F[i,j]最终答案

?

? ?

题目大意

NxM的1~K数矩阵满足任意竖分割的左右, 出现不同数的个数相同。求方案数对 1000000007取模。
N,M≤2000; K≤106

?

? ?

题目大意

1 2 2 4 2 1 1 1 3 2 1 2

? ? ?

考试情况

20分 10分

8个 13个

? ?

分析规律

?

A C C C C C B A C C C C C B A C C C C C B A C C C C C B A C C C C C B |A|=|B|, C in A, C in B

A

B

? ? ? ? ? ?

考察点:组合数学,观察归纳,容斥原理

标记集合:A C B 最左列与最右列的特殊性 |A|=|B|,|A-B|=|B-A|

A C B

反证法:中间部分不会有新颜色出现 C ? A∩B

?

?

?

?

?

?

? ? ? ?

例题:约数相关

?
?

1.求N的约数个数 2.求N的约数和 3.求[A,B]的约数个数之和 4.求[A,B]的约数和之和
N≤109,A,B≤105

? ? ?

例题:约数相关

5.在A[1..N]一组数中选出K个不同的数 使得它们的GCD(最大公约数)最大 K ≤ N ≤ 105,Ai ≤ 105

?

?

END


相关文章:
冲刺NOIP2010模拟试题与解析(一)
冲刺NOIP2010模拟试题与解析(一)_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 冲刺NOIP2010模拟试题与解析(一)_学科竞赛_初中教育_教育专区。...
冲刺NOIP模拟试题与解析 提高组
冲刺NOIP 模拟试题与解析( 十一 ) 学校: 河南省焦作一中 出题人:刘晓刚 《NOI 导刊》 2011 年 9 月第 7 期 题目一览 题目 文件名 输入文件 输出文件 题目...
noip普及组复赛模拟试题15(附答案)
noip普及组复赛模拟试题15(附答案)_学科竞赛_初中教育_教育专区。【基础】班委确定 【试题描述】 经过紧张而激烈的选拔考试,编程班终于浮出水面,一共有 k 位同学...
冲刺NOIP2010模拟试题与解析(一)
冲刺NOIP2010模拟试题与解析(一)_公务员考试_资格考试/认证_教育专区。冲刺NOIP2010模拟试题与解析(一)模拟试题与解析 试题与解析( 冲刺 NOIP2010 模拟试题与解析(...
1995-2008 历届NOIP试题及详解
第 19 页 | 共 209 页 NOIP 1996 提高组 测试数据 第二届全国青少年信息学(计算机)奥林匹克分区联赛 复赛参考答案(高中组)题号 1.1 1.2 n=1 n=2 输入...
NOIP2011模拟试题及解析
NOIP2011模拟试题解析_工学_高等教育_教育专区。请多多支持~~NOIP2011 模拟试题解析 题目名称 可执行文件名 输入文件名 输出文件名 每个测试点时限 测试点数目...
NOIP初赛模拟试题及答案
NOIP初赛模拟试题答案_计算机硬件及网络_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 NOIP初赛模拟试题答案_计算机硬件及网络_IT/计算机_专业资料。...
noip普及组复赛模拟试题10答案
noip普及组复赛模拟试题10答案_学科竞赛_初中教育_教育专区。【试题描述】 选拔考试即将开始,同学们陆续进入考场,哇,考场好大啊。究竟 star 应该坐 在哪张位置呢?...
noip普及组复赛模拟试题23(答案)
noip普及组复赛模拟试题23(答案)_学科竞赛_初中教育_教育专区。小华的寒假作业上,有这样一个趣味填空题: 给出用等号连接的两个整数,如“1234=127”。当然,现在这...
noip普及组复赛模拟试题14(附答案)
noip普及组复赛模拟试题14(附答案)_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档noip普及组复赛模拟试题14(附答案)_学科竞赛_初中教育_教育...
更多相关标签:
noip初赛试题解析 | noip2016模拟试题 | noip2016初赛模拟试题 | noip初赛模拟试题 | pmp模拟试题与解析 | 护师模拟试题及解析 | 护师模拟试题 解析 | 模拟电路试题解析 |