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

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


相关文章:
noip普及组复赛模拟试题14(附答案)
noip普及组复赛模拟试题14(附答案)_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档noip普及组复赛模拟试题14(附答案)_学科竞赛_初中教育_教育...
noip普及组复赛模拟试题10答案
noip普及组复赛模拟试题10答案_学科竞赛_初中教育_教育专区。【试题描述】 选拔考试即将开始,同学们陆续进入考场,哇,考场好大啊。究竟 star 应该坐 在哪张位置呢?...
noip普及组初赛模拟试卷(附答案)考前模拟
noip普及组初赛模拟试卷(附答案)考前模拟_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档noip普及组初赛模拟试卷(附答案)考前模拟_学科竞赛_初中...
NOIP2010模拟试题与解析
NOIP2010模拟试题与解析NOIP2010模拟试题与解析隐藏>> NOIP 提高组复赛模拟题(二) 提高组复赛模拟题 组复赛模拟题(题目 试题名称 文件名 输入文件名 输出文件名 ...
noip普及组复赛模拟试题24(答案)
noip普及组复赛模拟试题24(答案)_学科竞赛_初中教育_教育专区。1.质因数分解(prime.cpp/c/pas) 【问题描述】已知正整数 n 是两个不同的质数的乘积,试求出较...
noip普及组复赛模拟试题34(附答案)
noip普及组复赛模拟试题34(附答案)_学科竞赛_初中教育_教育专区。1. 近来见习魔法师们在进行一项有关二进制数的研究,研究涉及的一个统计问题令他们大 伤脑筋。问...
noip普及组编程模拟试题1(答案)
noip普及组编程模拟试题1(答案)_学科竞赛_初中教育_教育专区。一、问题描述: 考虑在 0 和 1 之间的所有分母不大于 N 的最简分数。下面是 N = 5 时的情况:...
清北学堂NOIP2010模拟试题与详细解析(13)
清北学堂NOIP2010模拟试题与详细解析(13)_IT/计算机_专业资料。清北学堂NOIP2010试题与详细解析十三) 冲刺 NOIP 2010 模拟试题与解析 (十三)试题名称 防护伞 外星...
2011第17届NOIP试题及解析
2011第17届NOIP试题解析_学科竞赛_高中教育_教育专区。第十七届 NOIP2011 提高...输入:30 输出:___ 答案:1 2 5 13 34 解析:模拟一下,发现是隔一个输出...
noip普及组初赛模拟试卷14(附答案)
noip普及组初赛模拟试卷14(附答案)_学科竞赛_初中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 noip普及组初赛模拟试卷14(附答案)_学科竞赛_初中教育_教育...
更多相关标签:
pmp模拟试题与解析 | 护师模拟试题 解析 | 护师模拟试题及解析 | noip试题 | noip2016复赛试题 | noip普及组试题精选 | noip初赛试题 | noip2016初赛试题 |