-
NOIP
模拟试题
by yali middle
school
问题名称
文件名
序列
连分数
词链
Geodetic
集合
输入
输出
时限
2s
1s
1s
1s
分值
100
100
100
100
模拟一
序列
()
问题描述
有一个非递减的整数序列
S
1
，
S
2
，
S
3
< br>，……，
S
n+1
（
S
i
<=S
i+1
）
。定义序列
m
1<
/p>
，
m
2
，…，<
/p>
m
n
为
S
的“
M
序列”
，其中
m
i
=(S
i
+S
i+1
)/2
。
例如，
S=(1, 3, 3,
5)
，则
m=(2, 3,
4)
。
现在给你序列
m
，要你求有多少个
S
序列的“<
/p>
M
序列”是序列
m
。
输入
()
第一行一个整数
n
，
下接
n
行，每行一个整数
m
i
输出
()
一个整数，表示有多少个
S
序列的“
M
序列”是
序列
m
样例
3
2
5
9
4
样例说明：存在如下四个数列
S<
/p>
满足要求：
2
，
2
，
8
，<
/p>
10
；
1
，
3
，
7
，
11
；
0
，
4
，
6
，
12
；
< br>
-1
，
5
，
5
，
13
。
第
1
页
共
5
页
NOIP
模拟试题
by
yali middle school
数据范围
50%
的数据
n<=1000
，
m
i
<=20000
100%
的数据
2<=n<=100000
，
m
i
<=1
0
9
.
连分数
()
问题描述
Cindy
新学了无理数，老师教她了一种用有理数逼进无理数的方法：找到这
个无理数相应的无
限循环连分数。
例如，
我们可以通过分别取出连分数中的一层、两层、三层、……，而忽略其他部
分，
这样就可以得到一个有理数序列，
我们称之为该
连分数的渐近分数序列。
黄
金分割数
5
?
1
的渐近分数是
1/1
，
1/2
，
2/3
，
3/5
，
5/8
，
8/13……
。
2
Cindy
对其中的连分数形式尤为感兴趣，为了简化，她准备研究的连分数都
是如下形式的：<
/p>
p
1
?
p
2
?
?
p
n
?
p
1
?
1
1
1
1
1
p
2
?
?
她用一个简单的记号表示这种连
分数：
?
p
1
,
p
2
,
p<
/p>
3
,
?
,
p
n
?
。例如黄金分
割
数的连分数简记为
?
1
?
第
2
页
共
5
页
NOIP
模拟试题
by
yali middle school
对于每一个这样的连分数，
< br>都有其相应的渐近分数序列：
a
1
/b
1
，
a
2
/b
2
，
…
…
。
现在
Cindy
< br>的研究中出现了一个连分数
?
p
1
,
p
2
,<
/p>
p
3
,
?
,
p
n
?
，她希望你能帮她求
出它的渐近分数序列的第
m<
/p>
项。请用二元组
(a
m
< br>，
b
m
)
的形式给出答案，并且对于
答案的中的两个数，只需要输出它们模
9973
的余数即可。
输入
()
第一行为一个整数
n
，
m
，分别表示连分数的循
环节长度和需要求的渐近分
数的项数。下接
n
< br>行每行一个整数
p
i
，描述连分
数。
输出
()
空格分隔的两个整数
a
m
< br>、
b
m
。
样例
1 6
1
8 13
数据范围
60%
的数据，
m<=10
5
100%
的数据，
< br>n<=10
，
m
<=10
9
词链（
）
问题描述
给定一个仅包含小写字母的英文单
词表，
其中每个单词最多包含
50
个字
母。
如果一张由一个词或多个词组成的表中，
每个单词
（除了最后一个）
都是排
在它后面的单词的前缀，
则称此表为一个词链。
例如下面的单词
组成了一个词链：
i
int
integer
而下面的单词不组成词链：
integer
第
3
页
共
5
页
NOIP
模拟试题
by
yali middle school
intern
请在给定的单词表中取出一些词，
组成最长的词链。
最长的词链就是包含单
词数最多的词链。
数据保证给定的单词表中，单词互不相同，并且单词按字典顺序排列。
输入
()
第一行
一个整数
n
，表示单词表中单词数
下接
n
行每行一个单词。
< br>
输出
()
一个整数，表示最长词链长度。
样例
5
i
int
integer
intern
internet
4
数据范围
50%
的数据，
n<=1000
100%
的数据，
n<=10000
Geodetic
集合
()
问题描述
图
G
是一个无向连通图，没有自环，并且两点之间至多只有一条边。我们
定义顶点
v,u
最短路径就是从
v
到
u
经过边最少的路径。所有包含在
v-u
的最短
路径上的顶点被称为
v-u
的
Geodetic
顶点，这些顶点的集合记作
I(v,
u)
。
我们称集合
I(v, u)
为一个
Geodetic
集合。
例如下图中，
I(2, 5)={2, 3, 4,
5}
，
I(1, 5)={1, 3,
5}
，
I(2, 4)={2,
4}
。
第
4
页
共
5
页
NOIP
模拟试题
by
yali middle school
1
2
3
4
5
给定一个图
G
和若干点对
v,u
，请你分别求出
I(v,
u)
。
输入
()
第一行两个整数
< br>n,m
，分别表示图
G
的顶点数
和边数（顶点编号
1-n
）
下接
m
行，每行两个整数
< br>a,b
表示顶点
a
和
b
之间有一条无向边。
第
m+2
行有一个整数
k
，表示给定的点对数。
下接
k<
/p>
行，每行两个整数
v,u
。
输出
()
共
k
行，每行对应输入文件中每一个点对
v,
u
，按顶点编号升序输出
I(v, u)
。
同一行的每个数之间用空格分隔。
样例
5
6
1 2
1 3
2 3
2 4
3 5
4 5
3
2 5
5 1
2 4
2 3 4 5
1 3 5
2 4
数据范围
第
5
页
共
5
页
NOIP
模拟试题
by
yali middle school
100%
的数据，
n<=40
各题简要分析：
sequence
序列：
令
S
序列的第一项为
k
，那么后面几项就可以写成关于
k
的多项式：
S1=k
S2=2*m1-k
S3=2*m2-2*m1+k
……
然后根据
S
序列的非递减性质，有
S1<=S2<=S3<=
…
.
所以有
k<=2*m1-k
2*m1-k<=2*m2-2*m1+k
……
可以得到
n
个关于
k
的不等式，而且都是有规
律的，可以在
O(n)
的时间内解出形如
a<=k<=b
的结果。
由于
k
的值和
S
序列是一一对应的，所以
k
的取值的个数
(b-a)
就是满足要求的
S
序列
的
个数。
faction
连分数：
本题是原创的，重点考察递推和用矩阵乘法优化递推。
由递推式：
x
m
?
y
m
1
x
p
k
?
m
?
< br>1
y
m
?
1
k = (m-1) mod
n + 1
可得
x
m
?
y
m
?
1
;
y
m
?
p
k
*
y
m
?
1
?
x
m
直接按照这个递推式计算，复杂度
O(m)
，预计得分
60%
。
上面的递推式对应的矩阵运算是：
?
0
(
x
m
,
y
m
)
?
(
x
m
?
1
< br>,
y
m
?
1
)
*
?
?
1
?
1
?
?
p
k
?
?
所以有
?
?
0
(
x
m
,
y
m
)
?
(
0
,
1
)
*
c
< br>*
?
?
?
?
?
k
?
n
?
1
1
1
?
?
?
?
p
k
?
?
?
?
m
?
< br>?
n
?
?
?
其中
c
是
(m
mod n)
部分的余式矩阵的乘积。
由于计算矩阵幂时间复杂度为
O(logm)
，
所以总的算法复杂度是
O(n+logm)
，
预计得分
100%
。
第
6
页
共
5
页
NOIP
模拟试题
by
yali middle school
Link
词链：
本题用动态规划是容易的，设
f(i)
表示
前
i
个单词可以构成包含第
i
个单词的最长词链。
F(i)=max{1
，
F(j)+1,
当
wo
rd[j]
是
word[i]
的前缀<
/p>
}
Ans=max{F(i)}
这样算法的复杂度是
O(n
2
)
，预计得分
50%
。
其实本题有很简单的贪心算法。
用一个
栈存储当前的以第
i
个单词结尾的最长词链，第
i+1
个单词加在栈的结尾（通过
出栈保持栈所存储的
是一个词链）
。
例如：
i
栈
：
i
int
栈：
i
int
integer
栈：
i
int
interger
intern
栈：
i
int
intern
< br>（
interger
出栈）
internet
栈：
i
int
intern
internet
可以证
明，在第
i
个单词插入后，当前在栈中的词链就是包含第
i
个单词的最长词链。
这样由于每个单词进栈出栈分别一次，所以算法的复杂度是
O(n)
贪心算法预计得分
100%
Geodetic
集合：
本题是由
pku
上一道试题改编的，
考察图的有关知识。
算法就是从每个点出发进行
BFS
扩展，按得到的
BFS
序列进
行递推。
设
min[i, j]
为从
i
到
j
的最短路长度
设
f[i, j]
表示从
i
到
j
点的最短路覆盖的节
点集合，
f[i, j] = f[i, k] U {j}
k={1..n} and
(min[i, k]+1=min[i,
j]
）
and
(k,j)
存在
对于输
入的每个
v,u
对，输出
f[v,u]
中的所有点就可以了。
第
7
页
共
5
页
NOIP
模拟试题
by
yali middle school
模拟二
题目名称
程序名称
输入文件
输出文件
测试点个数
时间限制
奖金
/exe
5
1
秒
编码
/exe
10
1
秒
工作
/exe
10
1
秒
求和
/exe
10
1
秒
第
8
页
共
5
页
NOIP
模拟试题
by
yali middle school
奖金（
/exe
）
【题目描述】
由于无敌的凡凡在
2005
年世界英俊帅气
男总决选中胜出，
Yali
Company
< br>总经理
Mr.Z
心情好，
决定给
每位员工发奖金。
公司决定以每个人本年在公司的贡献为标准来计算他们得
到奖金的多少。
于是
Mr
.Z
下令召开
m
方会谈。每位参加会谈
的代表提出了自己的意见：
“我认为员工
a
的奖金应该比
b
高！
”
Mr.Z
决定要找出一种奖金方案，满足各位代表的意见，且同时使得
总奖金数最少。每位员工奖金最少为
100
元。
【输入】
第一行两个整数
< br>n,m
，表示员工总数和代表数；
以下
m
行，
每行<
/p>
2
个整数
a,b
，
表示某个代表认为第
a
号员工奖金应
该比第
b
号员工高。
【输出】
若无法找到合法方案，则输出“
Poor Xed
”
；否则输出一个数表示最少总奖金。
【样例输入】
2 1
1 2
【样例输出】
201
【数据范围】
80
％的数据满足
n<=1000
，
m<=2000
；
100
％的数据满足
n<=10000
，
m<=20000
。
第
9
页
共
5
页
NOIP
模拟试题
by
yali middle school
编码（
/exe
）
【问题描述】
DEX
国刚刚截获了
KCAJ
国与
AW
AW
国之间的
e
1
。
D
国
S302
情报机构情报
员
007
2
手里正拿着写有
K
国与
A
国之间
Message
的文件。
“什么？！居然被加
密了！
！
”
007
忍不住说道，
“
KCAJ
，你会出
路的！
”
幸运的是
K
国与
A
国此次通讯时间远远超过了<
/p>
007
所估计的
30s
< br>，因此
007
又截获了
大量的<
/p>
Message
。通过对这些
Messa
ge
的研究，
007
发现了其中的秘密
：
每一条
e
原
本由
8
个
32-bit
的正整数
N1..N8
组成，本来这
< br>8
个整数可以由计
算机直接破解得出相应的文字。但对于
每条信息，
K
国与
A
< br>国另外使用了不同的密钥
M
来
再
次加密。所谓“密钥”其实也是一个
32-bit
的整数，在传
递讯息的时候，是将
N1 Xor
M
、
N2 Xor
M
、…、
N8 Xor
M
、
N9 Xor M
这
9
个整数传给对方（其中
N9
为
N1~N8
这
8
< br>个整数
的和
Mod
2^32
）
。
有了上面的发现，
007
马上意识到他可以
破解出
Message
了！
这实在是一
个简单的工作，
007
决定让你——也就是他的助手来完成此工
作。
【输入】
输入文件按顺序输入
9
个整数
N1..N9
。每个整数用
16
进制表示。
【输出】
输出仅
一个数，即密钥
M
。同样用
16
进制表示。
【样例输入】
3 4 4 7 7
b a 2 2e
【样例输出】
6
【数据范围】
40
< br>％的数据满足
M<=500
；
100
％的数据满足
M<2^32
；
1
2
e
是
Seceret
Message
的缩写，绝对不是
Short
Message
的缩写
此人极度神秘，目前只知道他的代号为
302.007
第
10
页
共
5
页
NOIP
模拟试题
by
yali middle school
工作（
/exe
）
【题目描述】
这次故事的主角是
HG
！
< br>转眼
4
年过去了，
HG
本科毕业了，
于是找了份工作。
每天
HG
会收到一份任务清单，清单上列出了
n
个可能需要他完成的任务。每个任务包含
3
个
信息：
Ti
、
Ai
、
Bi
，
Ti
表示完成此任务需要的时间，
Ai
表示此任务的到达时间，
Bi
表示此任务的
最晚完成时间。
在某一时刻若
HG
手上没有任务，
那么他可以选择一个已经到达且还能够在
Bi
时
刻之前（或者恰好在
Bi
时刻）完成的任务来做。
由于
HG
有
点懒（纯属虚构
:D
）
，他想尽量少的
减少他的总工作时间，但是他不能在可
以做任务的时候故意不做（这样会被炒鱿鱼的
>_<
）
，那么他该如何挑选任务来做呢？
你的任务就是求出
HG
的最少工作时间（即总共有多少时间
HG
在做任务）
。
【输入】
第一行一个整数
< br>n
表示任务数。
以下<
/p>
n
行，每行三个整数
Ti,Ai,Bi<
/p>
。
（
n<=1000
，
0<=Ai,Bi<=1500
，
Ti>=1
）
【输出】
输出仅一个数，即最少工作时间。
【样例输入】
3
15 0 25
50 0 90
45 15 70
【样例输出】
50
【数据范围】
Ti>=1
，
0<=Ai,Bi<=1200
；
30%
的数据满足
n<=5
；
60
％的数据满足
n<=500
；
100
％的数据满足
n<=1000
。
【说明】
输入数据保证
Bi-Ai
要大于等于<
/p>
Ti
，且小于
2Ti
。
第
11
页
共
5
页
NOIP
模拟试题
by
yali middle school
求和（
/exe
）
【题目描述】
高斯在他还是小
P
< br>孩的时候就求出了
1+2+
…
+
n
＝
n*(n+1)/2
；
LT
在他
还是小
P
孩的时候就知道
1/(1*2
)+1/(2*3)+
…
+1/((n-1)*n)
＝
1-1/n
；
现在，在你还是小
P
孩的时候，你要求出
S
＝
1
1
＋
?
＋
1
?
2
?
?
?
< br>m
n
?
(
n
?
1
)
?
?
?
(
n
?
m
?
1
)
【输入】
输入两
个整数
n,m
。
【输出】
输出占
两行，第一行一个整数
X
，第二行整数
Y
，表示
S
＝
X/Y
，且
X,Y
互质。
【样例输入】
1 2
【样例输出】
1
2
【数据范围】
m>1
，
n>0
；
50%
的数据满足
n<=50
；
100%
的数据满足
n+m<=500
。
模拟试题说明
奖金（
Reward
）
出题意图：
图论是
每年分区联赛必考内容，
本题是一道基础的图论题，
此题重点考
察选手以下几方
面：
?
根据问题建立图论模型，并应用图论知识解题
?
对邻接表的掌握
?
对拓扑排序算法的掌握
?
简单递推
第
12
页
共
5
页
NOIP
模拟试题
by
yali middle school
简要解答：
首先构
图，若存在条件“
a
的钱比
b
多”则从
b
引一条有向指向
a
；
然后拓扑排序，若无法完成排序则
表示问题无解（存在圈）
；
若可以得到完整的拓扑序列，则按序列顺序进行递推：
设
f[i]
表示第
i
个人能拿的最少奖金数；
首先所
有
f[i]=100
（题目中给定的最小值）
< br>；
然后按照拓扑顺序考察每个点
i
，若存在有向边
(j,i)
，则表示
f[i]
必须比
f
[j]
大，因
此我们令
f[i] =
Max { f[i] , f[j]+1 }
即可；
递推完成之后所有
f[i]
的值也就确定了
，而答案就等于
f[1]+
…
+f[n
]
。
编码（
Encode
）
出题意图：
递推题
几乎也是分区联赛的必考题，本题考察选手运用递推思想解题的能力。
简要解答：
本题目的是求出
M
，换言之只要确定
M
转换成二进制后每一位是
0
还是
1
即可。
首先我们把
32-bit
整数二进制位从低位到高位编号为第
1
位到第
32
位；
设输入
的
9
个整数为
A[1]..A[9]<
/p>
，即
A[1]=N1 Xor
M
，
A[2]=N2 Xor
M
……
A[9]=N9 Xor
M
；
A[i
,j]
＝
0
或
1
，表示
A[i]
转化为
2
进制后第
j
位上的数字；
之后类似做竖式加法，设
F[I,J]
表示计算
N1~N8
的第
i
位到第
32
位的和，且第
1
位到
第
i-1
位做加法进位到第
i
位后余下
j
，这种情况下
8
个数的和是不是可能等于
N9
。
F[I,J]=0
或
1
，
0
表示不可能，
1
表示可能。
那么如何递推呢？
显然我
们需要枚举
M
的第
i
< br>位数字是
0
还是
1
：
1
、
M
的第
i
位数字是
0
：
则
N1..N9
第
i
位上的数字分别为
A[1,i] Xor
0
，
A[2,i] Xor
0
，……，
A[9,i] Xor 0
，我们
用
B[1]..B[9]
来表示
；
则根据竖式加法规则，必然有（
B
[1]+B[2]+
…
+B[8]+J
）
Mod 2 = B[9]
，否则
M
第
i
位数
字不
可能为
0
；
若满足
条件，令
X=(B[1]+
…
+B[8
]+J) Div 2
，则
X
为进位到
第
i+1
位时余下的数，此时
取
F[I,J] = Max { F[I,J] , F[I+1,X] }
2
、
M
的第
i
位数字是
1
：
则
N1.
.N9
第
i
位上的数字分别为
A[1,i] Xor 1
，
A[2,i]
Xor 1
，……，
A[9,i] Xor 1
，我们
用
B[1]..B[9]
表示；
则必然有
(B[1]+B[2]+
…
+B[8]+J) Mod 2=B
[9]
，否则
M
第
i
位不能为
1
；
< br>
若满足条件，令
Y=(B[1]+<
/p>
…
+B[8]+J) Div 2
，则<
/p>
Y
为进位到第
i+1
位时余下的数，此时
取
F[I,J] = Max {
F[I,J] , F[I+1,Y] }
第
13
页
共
5
页
NOIP
模拟试题
by
yali middle school
边界条件即
F[33,x]
＝
1
；
在求
F[I,J]
< br>时顺便记录
F[I,J]=1
时
M
的第
i
位是
0
还是
1
，则只要求出
F[1,0]
＝
1
后，便
可根据记录推出
M
的具体数值。
工作（
Work
）
出题意图：
考察选手对动态规划的掌握
简要解答：
此题是一道较简单的动态规划问题；
设
F[i]
表示从开始时刻工作到第
i
时刻初（或者说是第
i-1
时刻末）
，当前空闲，目前最
少工作时间是多少。
若
F[i]=
无穷大则表示此种情况不可能
；
设
S
表示
工作开始的时刻（即最早的一个工作的到达时间）
，则
F[S]
=0
；
很容易写出动态规划方程：
F[i]
= Min { F[i-T[j]] + T[j]
且
A[j]<= i-T[j]
<= B[j]
F[i-1]
且第
i-1
时刻无工作可以做
}
问题的答案即
F[E+1]
，
E
表示工作的最晚
可能结束时间，即
E=Max{B[i]}
。
< br>
求和（
< br>Sum
）
出题意图：
考察选
手的数学解题能力，
及对高精度加法、
减法、
< br>高精度×单精度、
高精度÷单精度
的掌握。
简要解答：
定义
X
那么原题即求
0
容易证明：
X
则
?
y
?
Y
?
1
，这里
x,y
都为整数，
x>=0
，
y>=2
；
(
< br>x
?
1
)(
x
?
2
)
?
(
x
?
y<
/p>
)
?
m
?
1
?
m
?
?
?
(
n
?
1
)
?
m
?
(
y
?
1
)
?<
/p>
(
y
?
1
)
(
x
?
1
)
x
?
?
?
(
y
?
1
)
?
(
y
?
1<
/p>
)
第
14
页
共
5
页
NOIP
模拟试题
by
yali middle school
0
?
m
?
1
?
m
?
?
?
(
n
?
1
)<
/p>
?
m
?
1
?
(
m
?
1
)
?
(
m
?
1
)
?
(
m
?
1
)
?
(
m<
/p>
?
1
)
(
1
?
0
)
?
?
?
(
n
?
(
n
?
1
)
)
?
(
m
?
1<
/p>
)
?
?
1
?
(
m
?
1
)
?
(
n
?
0
?
(
m
?
1
)
)
?
(
m<
/p>
?
1
)
根据上式直接高精度计算即可。
第
15
页
共
5
页
NOIP
模拟试题
by
yali middle school
模拟三
一、任务分配
图书馆按顺序排列有<
/p>
N
本书需要维护，每本书的总页数不相同。现有
< br>M
位员工。可以
给每个员工分配连续的一段书籍，让他进
行维护。
现在的问题是，
怎么样分配，工作任务最
重（需要维护的页数最多）的人维护的页数尽量少。
输入：第一行两个数，
N
、
M
。接下来
N
行，每行一个整数，表示一本书的页数。
输出：任务最重的人最少需要维护的页数。
样例：
5
3
3
2
4
1
5
5
数据范围：
N<=10
5
，
M<=N
。一本书的页数最多
10
4
。时间限制为
1s
。
二、求逆序对
给定一个序列
a1,a2,
…
,an
，如果存在
i
并且
ai>aj
，那么我们称之为逆序对，求逆序对
的数目
输入：第一行为
n,
表示序列长度，接
下来的
n
行，第
i+1
行表示序列中的第
i
个数。
输出：所有逆序对总数
.
样例：
deseq. in
4
3
2
3
2
3
5
数据范围：
N<=10
5
。
A
i
<=10
。时间限制为
1s
。
三、最优乘车
某人从起点去目的地开会，期间需要转乘公共汽车，他比较讨
厌专车，
因此，
要求你设
计它如何乘车
，使得在转车次数最少的情况下，花费最小。已知起点在公交车站
1
，终点在
公交车站
N
。
输入：
第一行为二个
数
n,m
，分别表示该城市中的公共汽车站点个数和线路的条数
。
第
16
页
共
5
页
NOIP
模拟试题
by
yali middle school
接下来的一个
n*n
维矩阵
D
，分别描述了这个城市
n
个站点的交通网络。数字
0
表示没有连通，
非
0
数字表示
两个站点之间的直达距离。
每条道路都是双向的，
也就是
数据保证
D
ij
=D
ji
。
接下
来的
m
行，每行由若干不超过
n
的整数组成，描述了一条公共汽车的行车线
路。
每条公交车线路都是往返行驶。
输出：
第一行为最少转车次数
第二行为最少乘车代价（乘车距离最短）
。
样例：
3
2
0 1 3
1 0 1
3 1
0
1 2 3
3 1
1 2
数据范围：
N<=1000<
/p>
。
M<=100
。时间限制为
5s
。
四、营救
铁塔尼号遇险了！
他发出了求救信号。
距离最近的哥伦比亚号收
到了讯息，
时间就是生
命，必须尽快赶到那里。
通过侦测，
哥伦比亚号获
取了一张海洋图。
这张图将海洋部分化成
n*n
个比较小的单位，
其中用
1
标
明的是陆地，用
0
标明是海洋。
船只能
从一个格子，移到相邻的四个格子。
为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。
输入：
第一行为
n,
下面是一个
n*n
的
0
，
1
矩阵，表示海洋地图
最后一行为四个小于
n
的整数，分别表示哥伦比亚号和铁塔尼号的位置。
输出：
哥伦比亚号到铁塔尼号的最短距离，答案精确到整数。
样例：
3
001
101
100
1 1 3 3
4
数据范围：
N<=1000
。时间限制为
1s
。
第
17
页
共
5
页
NOIP
模拟试题
by
yali middle school
模拟四
本套试题所有题目的空间限制都为
5
12MB
。
1
，
2
，
4
题
时间限制都为
1s
，
3
题时间限制为
2s
第一题：
money
Dog
同学喜欢去购物，
但是他不想花很多钱，
所以他
总是挑那些打折的东西来买，
现在
给出他买的所有东西的一个购
物清单，以及每个物品打几折，问他这次购物一共花了多少
钱？
输入文件（
）
第一行一个
n(1<=n<=100)
表示
dog
一共买了多少个东西。
<
/p>
后面紧接
n
行，每行描述购买的一种物品
：
每行
2
个
整数
ai
，
bi
（
1<=ai<=10000,1<=bi<=10
）
输出文件（
）
一行，一个实数为
dog
一共花了多少
钱，答案保留
2
位小数
样例
Input
：
2
10000 10
1 1
Output
：
10000.10
第二题：
sqrt
给出一个正整数<
/p>
n
（
1
）
，求当
x
，
y
都为正整数，方程
sqrt(n)=sqrt(x)-sqrt(y)
的解中，
x
的最大值是多少？
输入文件（
）
一行，一个正整数
n
输出文件（
）
一行，一个满足条件的最大的
x
的解。
第
18
页
共
5
页
NOIP
模拟试题
by
yali middle school
样例：
input
4
output
9
第三题：
work
当前有
n
（
n<=12
）个工作
，和
8
个工人。现在每个工作需要占用一个工人的从
[a
，
b]
这个区间的时
间（一个工人自然不可能在同一个时间做
2
个不同的工作）
，且一个工作不一
定是所有工人都能够完成的。
现在给出每个工作的描述，
问是否存在一种安排方案使得所有
工作都能完成。
输入文件（
）
输出文件有多组数据。第一行一个数
tot
表示数据的组数，后面紧接
tot
组数据。
对于每一组数据的第一行有一个整数
n
，
表示工作的数目。
后面
n
行每行描述一个工作。
对于一个工作
，
a
，
b
，<
/p>
k
，
h1
，
h2
……
hk
来描
述，表示这个工作需要占用一个工人
[a
，
b]
的时间，并且能够完成这个工作的工人只有
k
个，标号分别是
h1
，
h2
……
hk
。
输出文件（
）
对于每组输入数据，输出一行
YES
（
如果可以安排一种方案使得工作完成）
或者是
NO
（无法安排一种方案）
样例：
input
2
2
1 1 1 1
2 2 1 1
2
1 2 1 1
2 2 1 1
output
YES
NO
第
19
页
共
5
页
NOIP
模拟试题
by
yali middle school
第四题：
number
有一种序列按照如下定义：
1
．
1
在这个序列中
2
．这个序列是按照从小到大的顺序排列的
3
．如果一个数
i
出现在这个序列中，那么
2i+1
和
4i+5
也一定存在在这个序列中。
现在要求你先一个程序将这个序列前
n
个数字连接成一
个长串，并且在这个基础上，
从得到的长串中删除
m
个数字，使得这个长串的字典序最大。
输入文件（
）
输入文件一行，
2
个整数
n
，
m
输出文件（
）
输出文件
2
行，第一行是未删除数字之
前的原串。
第二行是删除数字之后的数字串
样例：
input
4 2
output
1379
79
模拟试题说明
money
:
主要目标送分
直接模拟。
sqrt
:
主要考察数学知识。
对于每
个给出的
n
，
肯定能够写成
p*sqrt(q)
的形式，
那么可以肯定的得到
y=q,
那么
x
肯定是
(p+1)*(p+1)*q
时间复杂度
O
（
1
）
,
空间复杂度
O
（
1
）
work
:
主要考察
dp
首先将
每个事件分离成
2
个事件点，然后按照时间先后顺序排序。
f[i][j]
为一个
bool
数组，表示当前处理完第
i
个事件点，
j
（是个工人的集合，最大
2^8-1
）这个状态是否有可能达到
第
20
页
共
5
页
NOIP
模拟试题
by
yali middle school
转移：
f[i][j]=f[i-1][j-k] or
如果当前第
i
个事件点是事件开始点
f[i-1][j+k]
如果当前第
i
个事件点是事件结束点
k
是能够
完成事件点所代表的事件的工人标号
最后输出
f[2*n][0]
number:
主要考察构造
首先是
要构造出整个序列。这里使用
2
个指针就可以完成。
指针
i,j
分向指在当前序列中的某个位置
，初始指向
1
每次判断
2*i+1
与
4*j+5
的大小关系，取小的那个放在当前序列的
最后一个，并将
其所代表的指针向后推移一位
直到构造完毕。
然后进行删除操作。这个问题在以
前的某年的
noip
试题中出现过，
这
里不做过多赘
述。
第
21
页
共
5
页
NOIP
模拟试题
by
yali middle school
模拟五
1
诸侯安置
源程序名
empire.???
（
pas,
c, cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
很久以前，有一个强大的帝国，它的国土成正方形状，如图
2
—
2
所示。
这个国家有若干诸侯。
由于这些诸侯
都曾立下赫赫战功，
国王准备给他们每人一块
封地
(
正方形中的一格
)
。但是
，这些诸侯又非常好战，当两个诸侯位于同一行或同一列时，
他们就会开战。
如下图
2
—
3
为
n
＝
3
时的国土，
阴影部分表示诸侯所处的位置。
前两幅图中
的诸侯可以互相攻击，第三幅则不可以。
致使国家动荡不安。
因此，
他希望通过合
国王自然不愿意看到他的诸侯们互
相开战，
理的安排诸侯所处的位置，使他们两两之间都不能攻击。
现在，给出正方形的边长
n
，以及需要
封地的诸侯数量
k
，要求你求出所有可能的安置
方案数。
(
n
≤
l00
，
k
≤
2n
2
-
2n+1
)
由于方案数可能很多，你只需要输
出方案数除以
504
的余数即可。
【输入】
仅一行，两个整数
n
和
k
，中间用一空格隔开。
【输出】
一个整数，表示方案数除以
504
的余数。
【样例】
2 2
4
【样例说明】
第
22
页
共
5
页
NOIP
模拟试题
by
yali middle school
四种安置方案如图
2
-
4
所示。
注意：镜面和旋转的情况属于不同的方案。
2
取火柴游戏
源程序名
match.???
（
pas, c,
cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
输入<
/p>
k
及
k
个整数<
/p>
n1
，
n2
，…
，
nk
，表示有
k
堆火柴棒，第
i
堆火柴棒的根数为
ni
；
接着便是你和计算机取火柴棒的对弈游戏。
取的规则如下：
每次可以从一堆中取走若干根火
柴，
也可以一堆全部取走，但不允许跨堆取，也不允许不取。
谁取走最后一根火柴为胜利者。
例如：
k
＝
2
，
n
1
＝
n
2
＝
2
，
A
代表你，
P
代表计算机，
若决定
A
先取：
A
：
(2,2)
→
(1,2)
{
从一堆中取一根
}
P
：
(1,2)
→
(
1,1) {
从另一堆中取一根
}
A
：
(1,1)
→
(1,0)
P
：
(1,0)
→
(0,0)
{P
胜利
}
如果决定
A
后取：
P
：
(2,2)
→
(2,0)
A
：
(2,0)
→
0,0)
{A
胜利
}
又如
k
＝
3
< br>，
n1=1
，
n2
＝
2
，
n3
＝
3
，
A
决定后取：
P
：
(1,2,3)
→
(0,2,3)
A
：
(0,2,3)
→
(0,2,2)
A
已将游戏归结为
(2,2)
的情况，不管
P
如何取
A
都必胜。
编一个程序，在给出初始状态之后，判断是先取必胜还是先取
必败，如果是先取必胜，
请输
出第一
次该如何取。如果是先取必败，则输出“
lose
”
。
【样例
1
】
3
4 3
{
表示第一次从第
3
< br>堆取
4
个出来，
必胜
}
3 6 9
3 6 5
{
第一次取后的状态
}
【样例
2
】
4
lose
{
先取必败
}
15 22 19 10
第
23
页
共
5
页
NOIP
模拟试题
by
yali middle school
3
地毯填补问题
源程序名
blank.???
（
pas, c,
cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
相传在一个古老的阿拉伯国家里，
有一座宫殿。
宫殿
里有个四四方方的格子迷宫，
国王
选择驸马的方法非常特殊，<
/p>
也非常简单：
公主就站在其中一个方格子上，
只要谁能用地毯将
除公主站立的地方外的所有地方盖上，
美
丽漂亮聪慧的公主就是他的人了。
公主这一个方格
不能用地毯盖
住，毯子的形状有所规定，只能有四种选择
(
如图
4-l)
：
（
1
）
（
2
）
（
3
）
（
4
）
2
并且每一方格只能用一层地毯，迷宫的大小为
(2
k
)
的方形。当然，也不能让
公主无限制的
在那儿等，对吧？由于你使用的是计算机，所以实现时间为
1s
。
【输入】
输入文件共
2
行。
第一行：
k
，即给定被填补迷宫的大小为
2
k
(<
/p>
0
<
k
≤
10
)
；
第二行：
x y
，即给出公主所在方格的坐标
(
x
为行坐标，
y
为列坐标
)
，
x
和
y
< br>之间有一
个空格隔开。
【输出】
将迷宫填补完整的方案：
每一补
(
行<
/p>
)
为
x y c
(
x
，
y
为
毯子拐角的行坐标和列坐标，
c
为
使用
毯子的形状，具体见上面的图
1
，毯子形状分别用
1
、
2
、
< br>3
、
4
表示，
< br>x
、
y
、
c
之间用一
个空格隔开
)
。
【样例】
3
5 5 1
3 3
2 2 4
1 1 4
1 4 3
4 1 2
4 4 1
2 7 3
1 5 4
1 8 3
3 6 3
4 8 1
7 2 2
5 1 4
6 3 2
8 1 2
8 4 1
7 7 1
第
24
页
共
5
页
NOIP
模拟试题
by
yali middle school
6 6 1
5 8 3
8 5 2
8 8 1
第
25
页
共
5
页
NOIP
模拟试题
by
yali middle school
4
K
-
联赛
源程序名
kleague.???
（
pas,
c, cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
K
-
联赛职业足球俱乐部的球迷们都是有组
织的训练有素的啦啦队员，就像红魔啦
啦队一样
(
2002
年韩日世界杯上韩国队的啦啦队
)
。这个赛季，经过很多场比赛以后，球迷
们希望知道他们支持的球队是否
还有机会赢得最后的联赛冠军。
换句话说，
球队是否可以通
过某种特定的比赛结果最终取得最高的积分
(
获胜场次最多
)
。
(
允许出现多支队并列第一的
情况。
)
< br>
现在，给出每个队的胜负场数，
w
i
和
d
i
，分别表示
team
i
的胜场和负场<
/p>
(
1
≤
i
≤
n
)
。还给
出
a
i,j
，表示<
/p>
team
i
和
t
eam
j
之间还剩多少场比赛要进行
(
1
≤
i,j
≤
n
)
。这里，
n
表示参加联赛的
队数，
所有的队分别
用
1
，
2
，<
/p>
…，
n
来编号。
你的任务是找出所有还有可能获得冠军的球队。
所有队参加的
比赛数是相同的，并且为了简化问题，你可以认为不存在平局
(
比赛结果
只有胜或负两种
)
。
【输入】
第一行一个整数
n
(
1
≤
n
≤
25
)
，表示联赛中的队数。
第二行
2n
个数，
w
1
，
d
1
，
w
2<
/p>
，
d
2
，……，
w
n
，
d
n
，所有的数不超过
100
。
第三行
n
2
个数，
a
1,1
，
a
1,2
，…，
a
1,n
，
a
2,1
，…，
a<
/p>
2,2
，
a
2,
n
，…，
a
n,1
，
a
n,2
，…，
a
n,n
，所有
的数都不超过
10
。
a
i,
j
=a
j,i
，如果
< br>i=j
，则
a
i,j
=0
。
【输出】
仅一行，输出所有可能获得冠军的球队，按其编号升序输出，中间用空格分隔。
【样例
1
】
3
1 2
3
2 0 1 1 0 2
0 2 2 2 0 2 2 2 0
【样例
2
】
3
1 2
4 0 2 2 0 4
0 1 1 1 0 1 1 1 0
【样例
3
】
4
2 4
0 3 3 1 1 3 3 0
0 0 0 2 0 0 1 0 0 1 0 0 2 0 0 0
第
26
页
共
5
页
NOIP
模拟试题
by
yali middle school
5
小木棍
源程序名
stick.???
（
pas, c,
cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过
5
0
。
现在，
他
想把小木棍拼接成原来的样子，
但是却忘记了自己开始时有多少根木棍和它们
的长度。
给出每段小木棍的长度，编程帮他
找出原始木棍的最小可能长度。
【输入】
输入文件共有二行。
第一行为一个单独的整数
N
表示看过以后的小木柜的
总数，其中
N
≤
60
< br>，第二行为
N
个用空个隔开的正整数，表示
N
跟小木棍的长度。
【输出】
输出文件仅一行，表示要求的原始木棍的最小可能长度。
【样例】
9
6
5 2 1 5 2 1 5
2 1
第
27
页
共
5
页
NOIP
模拟试题
by
yali middle school
6
平板涂色
源程序名
paint.???
（
pas, c,
cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
CE
数码公司开发了一种名为自动涂色机（
APM
）的产品。它能用预定的颜色给一块由
不同尺寸且互不覆盖的矩形构成的
平板涂色。
│
──→
x
0
1
2
3
4
5
6
0
│
Red
Blue
↓
(
B
)
1
y
(
A
)
Blue
Red
2
(
E
)
Blue
(
D
)
3
(
C
)
4
Red
Blue
(
G
)
5
(
F
)
为了涂色，
APM
< br>需要使用一组刷子。每个刷子涂一种不同的颜色
C
。
APM
拿起一把有颜色
C
< br>的刷子，并给所有颜色为
C
且符合下面限制的矩形涂色：
为了避免颜料渗漏使颜色混合，
一个
矩形只能在所有紧靠它上方的矩形涂色后，
才能涂
色。例如图中
矩形
F
必须在
C
和
D
涂色后才能涂色。注意，每一个矩形必须立刻涂满，不<
/p>
能只涂一部分。
写一个
程序求一个使
APM
拿起刷子次数最少的涂色方案。注意，如果
一把刷子被拿起
超过一次，则每一次都必须记入总数中。
【输入】
文件
第一行为矩形的个数
N
。
下面有
N
行描述了
N
个矩形。
每个矩形有
5
个整
数描述，左上角的
y
坐标和
x
坐标，右下角的
y
坐标和
x
坐标，以及预定颜色。
颜色号为
1
到
20
的整数。
平板的左上角坐标总是
(
0,
0
)
。
<
/p>
坐标的范围是
0..99
。
N
小于
16
。
【输出】
输出至文件
，文件中记录拿起刷子的最少次数。
【样例】
7
3
0
0 2 2 1
0 2 1 6 2
2 0 4 2 1
1 2 4 4 2
1 4 3
6 1
4 0 6 4 1
3 4 6 6 2
第
28
页
共
5
页
6
NOIP
模拟试题
by
yali middle school
模拟试题说明
1
诸侯安置
【算法分析】
重新描
述一下问题，
其实就是在一个边长为
2n
-
1
的正菱形
(
如上图
2
-
2
为
n
＝
3
的情形
)
上摆放
k
个棋子，
使得任意两个棋子都不在同一行、
同一列。
试问：
这样的摆法共有多少种
?
看到这道题目，我们就会立即想起一道经典的老题目：
n
皇后问题。这道题目与
n
皇后
问题非常相似。
但有两个不同点：一是
n
< br>皇后问题可以斜着攻击对方棋子，
而本题不能；二
是
n
皇后问题是在
n
，
n
的正方形棋盘上面放置
k
个皇后，
而本题却是在一个正菱形上摆放。
我们
试着先将
n
皇后变为不可斜攻的，再作思考，如果不能够斜着攻
击，
n
皇后的公式是：
(
C
(
k,n
))
2
*k!
。但是本题不是一个正方形，所以这个公
式对本题好像没有任何帮助。看来只
能够从另外一个角度思考问题了。
< br>
首先想到在
2n
-
1
列中任意取出
k
列进行具体分析，这样一来问题就转化成：有一个长
为
k
的数列
(
无重复元素
)
，
每一个数在一个不定的区间
[a,b]
当中，
第
i
个数一定在区间
[a
i
,
b
i
]
之间，求这样的数列有多少种<
/p>
?
如果就是这个问题，那么比较难解决，但若把这个数列放在
本题中，
就比较简单。
因为题目中任意两个区间都是一种包含关系。
可以先把区间按照长
度排一下序，就可以看出来，再用乘法原理进行求解即可。
但是，
n
最多可
到
100
，
k
最多可
到
50
，
穷举要进行
< br>C
(
50,100
)
种方案
!
显然无法在规定的
时间内出解
!
那么怎么办呢
?
再
继续分析一下问题发现，里面有重叠子问题。
如果一个列作为最后一列，且这一
列以及前面所有列共放置
p
个诸侯，设
有
q
种情况
，那么这一列后面的所有列共放置
p+1
个棋子的方案数都要用
到
q
，从而引用乘法原理。而且在穷举
过程中，这一个工作做了许多遍，所以干脆用递推。
递推前，先把图形转化为类似图
2
-
5
的形式
(
即列排序
)
。<
/p>
设
f[i,j]
表示以第
i
列为最后一列，放置
j<
/p>
个棋子的总方案数，得出公式：
f
[
i
,
j
]
?
?
f
[
i
?
k
< br>,
j
?
1
]
*
(
i
?
j
?
1
)
k
?
1
i
?
j
不过还要注意，当
k
≥
2n
-
< br>1
时，问题无解。
2
取火柴游戏
【算法分析】
从问题
的描述分析，
可以将问题中的
k
堆火柴
棒抽象为
k
个非负整数，
而每取一次火
柴
棒可抽象为使其中的一个自然数变小，
当所有的数都变为
0
时，
游戏结束，
最后—次取火柴
棒的人为胜方。
当
k
较小，
且
k
堆火柴棒也都较小时，
可使用递推的方法来处理这个问题，
具体做法是
从终了状态
(
全零
)
反推出初始状态的值是先取必胜还是先取必败，
因为某一状态的值可以从
它的所有的取一次后的下一状态得到，
如果某状态的所有的下一状态都为先取必败，
则这一
< br>状态为先取必胜，否则为先取必败。
但当<
/p>
k
和
ni
都很大
时，上述方法很难行得通，为了解决这个问题，首先引进关于
n
个
非负整数的奇偶状态的定义：
如果把
n
个非负整数都化成二进制数，
然后对
n
个二进制数按
第
29
页
共
5
页
NOIP
模拟试题
by
yali middle school
位相加
(
不进行进位
)
，
若每一位
相加的结果都为偶数，
则称这
n
个非负
整数的状态为偶状态，
否则称之为奇状态。
可以证明：
任何一个偶状态在某一个数变小后一定成为奇状态，
而对任
何一个奇状态，
必定可以通过将某一个数的值变小，
使得改变后的状态成为偶状态。
前一种
情况是显然的，
因为一个数变小以后其对应的二进制数至少有一位发生改变。
这一位的改
变
就破坏了原来的偶状态。后一种情况可以通过构造的方法来证明，首先对任何一个奇状
态，
从高位向低位寻找到第一位按位加之和为奇数的二进制位，
设这一位为第
k
位，
则
n
个数的
对应的二进制数中至少存在一个数，其第
k
位为
1
，将这个
二进制数的第
k
位变成
0
，则所
有二进制数的第
k
位
上的数字之和就变成了偶数。
然后再对这个数的比
k
位低的所有位作如
下调整：
如果所有二进制数在该
位按位加之和为偶数，
则不改变该位的值，
否则改变该数在
该位的值，若原来的值为
0
，则改为
1
，若原来的值为
1
，则改为
0
，这样就构造出了一个偶
状
态，并且被改变的那个数一定变小了，因为这个数被改变的所有二进制位中的最高位从
1
变成了
0
。
如
n
＝
3
时，
三堆火柴棒的数量分别为
3
，
6
，
9
，
则
3
＝
(
0011
)
2
，
6
＝
(
0
110
)
2
，
9
＝
(
1001
)
2
，
最高位之和为
1
，其中
9
对应的二进制数的
最高位为
1
，将其变为
0
，次高位之和也是
1
，
9<
/p>
对应的二进制数的次高位为
0
，根据证明
过程将其变为
1
，最后二位数字之和均为偶数，无
需作任何改变，
这样
9
＝<
/p>
(
1001
)
2
被变成了
(
0101
< br>)
2
=5
，
显然，
3=
(
0011
)
2
，
6=
(
0110
)
2
，
5=
(
0101
)
2
是一个偶状态。
有了前面的分析，一种贪心算法就出来了。程序中用
n
个包含
16
个元素的数组（线性
表）来存放对每个非负整数对应的二进制数，如
b[i,
0]
存放第
i
个数的最低位，
n
个数的状
态取决于它们对应的二进制数的各位
数字之和的奇偶性，
而各位数字之和的奇偶性只需用
0
和
1
来表示，
0
表示偶，
1
表示奇。最后的状态
(
全
0
)
< br>为偶状态，所以开始状态为偶状态时，
先取必败，因为先取后局面变成了奇状态，
后取方一定可将字取成偶状态，直至取光为止。
反之则先取必胜。
【后记】
大家都知道国际象棋特
级大师卡斯帕罗夫与
IBM
公司研制的“深蓝”超级计算机进行
国际象棋人机大战的事吧
!
有了以
上算法后，
我们也可以编写出这样一个游戏程序。
让程序代表计
算机与人做取火
柴棒游戏，由人或计算机先取，要求你编的程序能够尽可能使计算机获胜
。
3
地毯填补问题
【知识准备】
分治思想和递归程序设计。
【算法分析】
拿到这个问题后，便有一种递归重复的感觉。首先对最简单的情况
(
即
k
＝
1
)
进行分析：
公主只会在
4
个方格中的一个：
左上角
：则使用
3
号毯子补，毯子拐角坐标位于
(
2, 2
)
；
{
下面就简称为毯子坐标
}
左下角
：则使用
2
号毯子补，毯子拐角坐标位于
(
1,
2
)
；
右上角
：则使用
1
号毯子补，毯子拐角坐标位于
(
2,
1
)
；
右下角
：则使用
4
号毯子补，毯子拐角坐标位于
(
1,
1
)
；
其实这
样不能说明什么问题，
但是继续讨论就会有收获，
即讨论
k
＝
2
的情况
(
如图
4
-
1
)
：
#
#
#
●
第
30
页
共
5
页
NOIP
模拟试题
by
yali middle school
#
○
#
#
#
#
#
○
○
#
#
#
我们假
设公主所在的位置用实心圆表示，即上图中的
(
1, 4
)
，那么我们就可以把
1
号毯
子放在
(
2, 3
)
处，这样就将
(
1,
3
)
至
(
2,
4
)
的
k
＝<
/p>
1
见方全部覆盖
(
#
表示地毯
)
。接下来就是
3
个
k=1
的见方继续
填满，
这样问题就归结为
k
＝
1
的情况了，
但是有一点不同的是：
没有
“公
主”了，每一个
k=1
的小见方都会留下一个空白
(
即
上图中的空心圆
)
，那么空白就有：
1
*3
＝
3
个，组合后便又是一个地毯形
状。
好了，
现在有感觉了吧，我们用分治
法来解决它！对于任意
k
>
1
的宫殿，均可以将其化
分为
4
< br>个
k/2
大小的宫殿，
先看一下
公主站的位置是属于哪一块，
因为根据公主所在的位置，
我们可
以确定中间位置所放的毯子类型，
再递归处理公主所站的那一块，
直到出现边界条件
k
＝
1
的情况，然后在公主边上铺上一块合适的地毯，递归结束。
由于要递归到每一格，复杂度就是面积，就是
O
(
2
2*k
*k
< br>)
。
4
K
-
联赛
【算法分析】
看一个
队是否有希望夺冠，
首先，
这个队此后的比赛自然是赢越多越好
，
所以先让这个
队把以后的比赛都赢下来，
算出这个队最高能拿多少分。
下面关键就看是否有可能让其他队
的积分都低于刚才计算出的最高分。
建立一
个网络，所有的球队作为图中的节点，每两个队之间的比赛也作为图中的节点。
从网络的
源各连一条边到“比赛的节点”
，容量为两队间还剩的比赛场数。从“每个队的节
点”都连一条边到网络的汇，容量为这个队当前的积分与最高分之差。
如果一个“比赛的节
点”代表的是
A
与
B
之间的比赛，那么从这个节点连两条边分别到“
A
队的节点”和“
B
队的节
点”
，容量为无穷大。
如果这
个网络的最大流等于所有还未进行的比赛的场次之和，
那么需要我们判断的那个
队抗有可能夺得冠军。
本题要
我们找出所有可能夺冠的队，
那么只需枚举所有的球队，
判断它
们是否有可能夺
冠即可。
5
小木棍
【问题分析】
搜索的顺序是枚举原始木棍的长度，
从小到大或从大到小均可。
但注意从大到小枚举的
时候，可以剪枝，如果长度为
k
·
L
的原始木棍尝试失败的话，长度为
L
的就不必尝试了，
因为必然也是失败的。
得到了原始木棍的长度后，
一个一个
的去枚举拼它的方案。注意，
枚举要按字典序，举
个例子说，<
/p>
就是不允许出现第一个木棍是由第
2
、<
/p>
5
、
6
个小木棍
拼成，而第二个木棍是由第
1
、
3
、
4
个小木棍拼成（
2
、
5
、
6
的字典序大于
1
、
3
、
4
）
。
枚举的过程中，有一个比较强的剪枝：如果放入一个长度为<
/p>
len
的小木棍后，正好拼成
了一个原始
长度的木棍，
但是拼后面的木棍失败，
那么就没有必要再枚举比
len
短的木棍了。
因为一段整空间被
一个刚好长度的木棍去填总是不亏的。
（为方便起见，可以事先将小木棍
降序排列）
6
平板涂色
第
31
页
共
5
页
NOIP
模拟试题
by
yali middle school
【问题分析】
指数型动态规划。
由于<
/p>
N
小于
16
，故
可以以一个
N
-
bit
的二进制数
A
作为状态，其中每个二进制位表示
一个格子的涂色情况，二进制位
0
表示该格子
未被涂色，二进制
1
表示该格子已被涂色。
用
F[A]
表示要得到状态
A
，最少需要改变多少次颜色。对于每个状态
A
，通过枚举涂
色方案来推新的状态。
第
32
页
共
5
页
NOIP
模拟试题
by
yali middle school
模拟六
1
单向双轨道
源程序名
track.???
（
pas, c,
cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
如图所
示
l
，某火车站有
B
< br>，
C
两个调度站，左边入口
A<
/p>
处有
n
辆火车等待进站
< br>(
从左
到右以
a
、
b
、
c
、
d
编号
)
，右边是出口
D
，规定在这一段，火车从
A
进入经过
B
、
< br>C
只能从
左向右单向开，并且
B
、
C
调度站不限定所能停放的车辆数。
出口
入口
D
A
B
C
从文件
输入
n
及
n
个
小写字母的一个排列，该排列表示火车在出口
D
处形成的从左到
右的火车编号序列。输出为一系列操作过程，每一行形如“
h
L
R
”的字母序列，其中
h
为
火车编号，
L
为
h
车原先所在位置
(
位置都以
A
、
B
、
C
、
D
表示
)
，
R<
/p>
为新位置。或者输出
‘
NO
’表示不能完成这样的调度。
【输入】
一个数
n
(
1
<
n
<
27
)
及由
n
个小写字母组成的字符串。
【输出】
可以调度则输出最短的调度序列，不可以调度时则输出‘
NO
’
。
【样例】
3
c A B
cba
b A C
a A
D
b C
D
c B
D
2
餐巾
源程序名
napkin.???
（
pas,
c, cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
一个餐厅在相继的
N
天里，第
i
天需要
Ri
块餐巾
(
i=l
，<
/p>
2
，…，
N
)<
/p>
。餐厅可以从三种途径
获得餐巾。
第
33
页
共
5
页
NOIP
模拟试题
by
yali middle school
(1)
购买
新的餐巾，每块需
p
分；
(2)
把用过的餐巾送到快洗部，洗一块需
m
天，
费用需
f
分
(f
。
如
m=l
时，第一天送
到快洗部的餐巾第二天
就可以使用了，送慢洗的情况也如此。
(3)
把餐巾送到慢洗部，洗一块需
n
天
(n>m)
，费用需
s
分
(s
。
在每天结束时，
餐厅必须决定
多少块用过的餐巾送到快洗部，
多少块送慢洗部。
在每天
开始时，
餐厅必须决定是否购买新餐巾及多少，
使洗好的和新购的餐巾之和满足当天的需求
量
Ri
，并使
N
天总的费用最小。
【输入】
输入文
件共
3
行，
第
1
行为总天数；
第
2
< br>行为每天所需的餐巾块数；
第
3
行为每块餐巾
的新购费用
p
，快洗所需
天数
m
，快洗所需费用
f
，慢洗所需天数
n
，慢洗所需费用
< br>s
。
【输出】
输出文件共
n+1
行。第
1
行为最小的费用。下
面的
n
行为从第
1
天开始每天需要的总
餐巾数、
需购买的新餐巾数、
结束时往快、
慢洗部送洗的餐巾数以及用到的来自快洗的餐巾
数和来自慢洗的餐巾数。
【样例】
3
64
3
2 4
3 3 1 2 0 0
10 1 6 2 3
2 1
2 0 1 0
4 0 0 0 2 2
3
求方程的根
源程序名
equation.???
（
pas,
c, cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
输入<
/p>
m
，
n
，
p
，
a
，
b
，求方程
f
(
x
)
＝
m
x
+n
x
-
p
x
＝
0
在
[a,b]
内的根。
m
，
n
，
p
，
a
，
b
< br>均为
整数，且
a
<
b
；
m
，
< br>n
，
p
都大于等于
1
。如果有根，则输出，精确到
1E
-
11
；如果无方程根，
则输
出“
NO
”
。
【样例】
2 3 4 1 2
1.5071265916E+00
2.9103830457E
-
11
4
间谍网络
(AGE)
源程序名
age.???
（
pas, c,
cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
由于外国间谍的大量渗入，国家安全正处于高度的危机之中。如果
A
间谍手中掌
第
34
页
共
5
页
NOIP
模拟试题
by
yali middle school
握着关于
B
间谍的犯罪证据，则称
A
可以揭发
B
。有些间谍收受贿赂，只要给他们一定数
量的美元
，他们就愿意交出手中掌握的全部情报。所以，如果我们能够收买一些间谍的话，
我们就
可能控制间谍网中的每一分子。
因为一旦我们逮捕了一个间谍，
他手中掌握的情报都
将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
我们的反间谍机关提供了一份资料，
色括所有已知的受贿的间谍，
以及他们愿意收受的
具体数额。<
/p>
同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。
假设总
共有
n
个间谍
(
n
不超过
3000
)
，每个间谍分别用
1
到
300
0
的整数来标识。
请根据
这份资料，
判断我们是否有可能控制全部的间谍，
如果可以，<
/p>
求出我们所需要支
付的最少资金。否则，输出不能被控制的一个间
谍。
【输入】
输入文件
第一行只有一个整数
n
。
第二行
是整数
p
。表示愿意被收买的人数，
1
≤
p
≤
n
。
接下来的
p
行，
每行有两个整数，
第一个数是一
个愿意被收买的间谍的编号，
第二个数
表示他将会被收买的数额
。这个数额不超过
20000
。
紧跟着一行只有一个整数
r
，
1
≤
r
≤
< br>8000
。
然后
r
行，
每行两个正整数，
表示数对
(
A, B
)
，
< br>A
间谍掌握
B
间谍的证据。
【输出】
答案输出到
。
如果可以控制所有间谍，第一行输出
YES
，并在第二行输出所需要支付的贿金最小值。
否则输出
NO
，并在第二行输出不能控制的间谍中，编号最小的间谍编号。
【样例
1
】
3
YES
2
110
1 10
2 100
2
1
3
2 3
【样例
2
】
4
NO
2
3
1 100
4 200
2
1
2
3 4
5
拼字游戏
源程序名
scrabble.???
（
pas,
c, cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
有一个未知的
4
×
4
的拼盘
M
，它的每个元素都是正整数。给出
4
行元素的总和，
4
列
第
35
页
共
5
页
NOIP
模拟试题
by
yali middle school
元素的总和以及两条对角线元素总和。
另外还给出了拼盘中任意
4
个位置的元素值，
它们的
位置在输入文件中给定。
编写一个程序求出拼盘中另外
12<
/p>
个位置的正整数的值，要求这些元素的行之和，列之
和以及对角线
之和与输入文件中给定的值相一致。
【输入】
输入文件包含用空格隔开的
22
个正整数。
前四个数字分别表示四行中每一行元素的总和，
接下来的
4
个数字分别表示
4
列中每列
元素的总和。接下来的数字表示主对角线元素的总和，即
M
(
0,
0
)
+M
(
1,1
)
+M
(
2,
< br>2
)
+M
(
3,
3
)
。
然后的数字
(
第
10
个数字
)
表示逆对角线上元数之和，
即
M
(
0, 3
)
+M
(
1, 2
)
+M
(
2, 1
)
+M
(
3, <
/p>
0
)
。剩下的部分还包含
12
个数字，被分成三个一组的形式
i
，
j
，
k
。表示
M
(
i,j
)
=k
。
你可以假设任何行对角线或列之和不会超过
< br>300
。
另外还可假设对于给定的输入文件总
是存在解决方案。
【输出】
输出文件应包含按
4
×
4
的形式输出的
16
个数字，同一行的四个数字用一个
空个隔开。
注意：
对于给定的输入文件，
可能有一个以上可能的解决方案。
任何一个方案都是可接受的。
【样例】
130 120 172 140
157 93 144 168 66 195 0 1 15 1 3 49 2 2 16 3 0 33
22
15 28 65
49 1 21 49
53 76 16 27
33 1 79 27
6
血缘关系
源程序名
family.???
（
pas,
c, cpp
）
可执行文件名
输入文件名
输出文件名
【问题描述】
我们正
在研究妖怪家族的血缘关系。
每个妖怪都有相同数量的基因，
但
是不同的妖怪的
基因可能是不同的。
我们希望知道任意给定的两
个妖怪之间究竟有多少相同的基因。
由于基
因数量相当庞大，直
接检测是行不通的。
但是，我们知道妖怪家族的家谱，
所以我们
可以根
据家谱来估算两个妖怪之间相同基因的数量。
妖怪之间的基因继承关系相当简单：如果妖怪
C
是妖怪
A
和
B
的孩子，则
C
的任意一
个基因只能
是继承
A
或
B
的基因，
继承
A
或
B
的概率各占
50
％。
所有基因可认为是相互独
立的，每个基因的继承关系不受别的基因影响。<
/p>
现在，我们来定义两个妖怪
X
和
Y
的基因相似程度。例如，有一个家族，这个家族中有
两个毫无关系
(
没有相同基因
)
的妖怪
A
和
B
，及它们的孩子
C
和
D
。那么
C
和
D
相似程度
是多少呢？因为
C
和
D
的基因都来自
A
和
B
，从概率来说，各占
50
％。所以，依概率计算
C
和
D
平均有
50
％的相同基因，
C
和
D
的基因相似程度为
50
％。
需要注意的是，
如果
A
和
B
之间存在相同基因的话，
C
和
D
的基因相似程度就不再是
50
％了。
你的任务是写一个程序，
对于给定的家谱以及成对出现的妖怪，
计算它们之间的基因相
第
36
页
共
5
页
-
-
-
-
-
-
-
-
-
上一篇：高中政治必修一经济生活知识框架
下一篇：K3单据模板Faction字段说明文档