信息学奥赛-入门级 题库
优秀的拆分(power)
【题目描述】
一般来说,一个正整数可以拆分成若干个正整数的和。例如,1 = 1,10 =1 + 2 + 3 + 4 等。
对于正整数 n 的一种特定拆分,我们称它为“优秀的”,当且仅当在这种拆分下,n 被分解为了若干个不同的 2 的正整数次幂。注意,一个数 x 能被表示成 2 的正整数次幂,当且仅当 x 能通过正整数个 2 相乘在一起得到。
例如,10 = 8 + 2 = 2^3 + 2^1 是一个优秀的拆分。但是,7 = 4 + 2 + 1 =2^2 + 2^1 + 2^0 就不是一个优秀的拆分,因为 1 不是 2 的正整数次幂。
现在,给定正整数 n,你需要判断这个数的所有拆分中,是否存在优秀的拆分。若存在,请你给出具体的拆分方案。
【输入格式】
输入文件名为 power.in。
输入文件只有一行,一个正整数 n,代表需要判断的数。
【输出格式】
输出文件名为 power.out。
如果这个数的所有拆分中,存在优秀的拆分。那么,你需要从大到小输出这个拆分中的每一个数,相邻两个数之间用一个空格隔开。可以证明,在规定了拆分数字的顺序后,该拆分方案是唯一的。
若不存在优秀的拆分,输出“-1”(不包含双引号)。
【样例 1 输入】
6
【样例 1 输出】
4 2
【样例 1 解释】
6 = 4 + 2 = 2^2 + 2^1 是一个优秀的拆分。注意,6 = 2 + 2 + 2 不是一个优秀的拆分,因为拆分成的 3 个数不满足每个数互不相同。
【样例 2 输入】
7
【样例 2 输出】
-1
【数据范围与提示】
对于 20% 的数据,n ≤ 10。
对于另外 20% 的数据,保证 n 为奇数。
对于另外 20% 的数据,保证 n 为 2 的正整数次幂。
对于 80% 的数据,n ≤ 1024。
对于 100% 的数据,1 ≤ n ≤ 1 × 10^7。
直播获奖(live)
【题目描述】
NOI2130 即将举行。为了增加观赏性,CCF 决定逐一评出每个选手的成绩,并直播即时的获奖分数线。本次竞赛的获奖率为 w%,即当前排名前 w%的选手的最低成绩就是即时的分数线。
更具体地,若当前已评出了 p 个选手的成绩,则当前计划获奖人数为max(1, ⌊p × w%⌋),其中 w 是获奖百分比,⌊x⌋ 表示对 x 向下取整,max(x, y) 表示 x 和 y 中较大的数。如有选手成绩相同,则所有成绩并列的选手都能获奖,因此实际获奖人数可能比计划中多。
作为评测组的技术人员,请你帮 CCF 写一个直播程序。
【输入格式】
输入文件名为 live.in。
第 1 行两个正整数 n, w。分别代表选手总数与获奖率。
第 2 行有 n 个非负整数,依次代表逐一评出的选手成绩。
【输出格式】
输出文件名为 live.out。
只有一行,包含 n 个非负整数,依次代表选手成绩逐一评出后,即时的获奖分数线。相邻两个整数间用一个空格分隔。
【样例 1 输入】
10 60
200 300 400 500 600 600 0 300 200 100
【样例 1 输出】
200 300 400 400 400 500 400 400 300 300
【样例 1 解释】


注意,在第 9 名选手的成绩评出之后,计划获奖人数为 5 人,但由于有并列,因此实际会有 6 人获奖。
【样例 2 输入】
10 30
100 100 600 100 100 100 100 100 100 100
【样例 2 输出】
100 100 600 600 600 600 100 100 100 100
【数据范围与提示】
测试点编号 n
1~3 = 10
4~6 = 500
7~10 = 2000
11~17 = 10000
18~20 = 100000
对于所有测试点,每个选手的成绩均为不超过 600 的非负整数,获奖百分比 w 是一个正整数且 1 ≤ w ≤ 99。
在计算计划获奖人数时,如用浮点类型的变量(如 C/C++中的 float、double,Pascal 中的 real、double、extended 等)存储获奖比例 w%,则计算 5 × 60% 时的结果可能为 3.000001,也可能为 2.999999,向下取整后的结果不确定。因此,建议仅使用整型变量,以计算出准确值。
表达式(expr)
【题目描述】
小 C 热衷于学习数理逻辑。有一天,他发现了一种特别的逻辑表达式。在这种逻辑表达式中,所有操作数都是变量,且它们的取值只能为 0 或 1,运算从左往右进行。如果表达式中有括号,则先计算括号内的子表达式的值。特别的,这种表达式有且仅有以下几种运算:
1. 与运算:a & b。当且仅当 a 和 b 的值都为 1 时,该表达式的值为1。其余情况该表达式的值为 0。
2. 或运算:a | b。当且仅当 a 和 b 的值都为 0 时,该表达式的值为0。其余情况该表达式的值为 1。
3. 取反运算:! a。当且仅当 a 的值为 0 时,该表达式的值为 1。其余情况该表达式的值为 0。
小 C 想知道,给定一个逻辑表达式和其中每一个操作数的初始取值后,再取反某一个操作数的值时,原表达式的值为多少。
为了化简对表达式的处理,我们有如下约定:
表达式将采用后缀表达式的方式输入。后缀表达式的定义如下:
1. 如果 E 是一个操作数,则 E 的后缀表达式是它本身。
2. 如果 E 是 E1 op E2 形式的表达式,其中 op 是任何二元操作符,且优先级不高于 E1、E2 中括号外的操作符,则 E 的后缀式为 E1′ E2′ op,其中 E1′、E2′ 分别为 E1、E2 的后缀式。
3. 如果 E 是 (E1) 形式的表达式,则 E1 的后缀式就是 E 的后缀式。同时为了方便,输入中:
a) 与运算符(&)、或运算符(|)、取反运算符(!)的左右均有一个空格,但表达式末尾没有空格。
b) 操作数由小写字母 x 与一个正整数拼接而成,正整数表示这个变量的下标。例如:x10,表示下标为 10 的变量 x10。数据保证每个变量在表达式中出现恰好一次。
【输入格式】
输入文件名为 expr.in。
第一行包含一个字符串 s,表示上文描述的表达式。
第二行包含一个正整数 n,表示表达式中变量的数量。表达式中变量的下标为 1,2, … , n。
第三行包含 n 个整数,第 i 个整数表示变量 xi 的初值。
第四行包含一个正整数 q,表示询问的个数。
接下来 q 行,每行一个正整数,表示需要取反的变量的下标。注意,每一个询问的修改都是临时的,即之前询问中的修改不会对后续的询问造成影响。
数据保证输入的表达式合法。变量的初值为 0 或 1。
【输出格式】
输出文件名为 expr.out。
输出一共有 q 行,每行一个 0 或 1,表示该询问下表达式的值。
【样例 1 输入】
x1 x2 & x3 |
3
1 0 1
3
1
2
3
【样例 1 输出】
1
1
0
【样例 1 解释】
该后缀表达式的中缀表达式形式为 (x1 & x2) | x3。
对于第一次询问,将 x1 的值取反。此时,三个操作数对应的赋值依次为0,0,1。原表达式的值为 (0 & 0) | 1 = 1。
对于第二次询问,将 x2 的值取反。此时,三个操作数对应的赋值依次为1,1,1。原表达式的值为 (1 & 1) | 1 = 1。
对于第三次询问,将 x3 的值取反。此时,三个操作数对应的赋值依次为1,0,0。原表达式的值为 (1 & 0) | 0 = 0。
【样例 2 输入】
x1 ! x2 x4 | x3 x5 ! & & ! &
5
0 1 0 1 1
3
1
3
5
【样例 2 输出】
0
1
1
【样例 2 解释】
该表达式的中缀表达式形式为 ( ! x1) & (! (( x2|x4) & ( x3 & (! x5) ) ))。
【数据范围与提示】
对于 20% 的数据,表达式中有且仅有与运算(&)或者或运算(|)。
对于另外 30% 的数据,|s| ≤ 1000,q ≤ 1000,n ≤ 1000。
对于另外 20% 的数据,变量的初值全为 0 或全为 1。
对于 100% 的数据,1 ≤ |s| ≤ 1 × 10^6,1 ≤ q ≤ 1 × 10^5,2 ≤ n ≤1 × 10^5。
其中,|s| 表示字符串 s 的长度。
方格取数(number)
【题目描述】
设有 n × m 的方格图,每个方格中都有一个整数。现有一只小熊,想从图的左上角走到右下角,每一步只能向上、向下或向右走一格,并且不能重复经过已经走过的方格,也不能走出边界。小熊会取走所有经过的方格中的整数,求它能取到的整数之和的最大值。
【输入格式】
输入文件名为 number.in。
第 1 行两个正整数 n, m。
接下来 n 行每行 m 个整数,依次代表每个方格中的整数。
【输出格式】
输入文件名为 number.out。
一个整数,表示小熊能取到的整数之和的最大值。
【样例 1 输入】
3 4
1 -1 3 2
2 -1 4 -1
-2 2 -3 -1
【样例 1 输出】
9
【样例 1 解释】

按上述走法,取到的数之和为 1 + 2 + (-1) + 4 + 3 + 2 + (-1) + (-1) = 9,可以证明为最大值。

注意,上述走法是错误的,因为第 2 行第 2 列的方格走过了两次,而根据题意,不能重复经过已经走过的方格。

另外,上述走法也是错误的,因为没有走到右下角的终点。
【样例 2 输入】
2 5
-1 -1 -3 -2 -7
-2 -1 -4 -1 -2
【样例 2 输出】
-10
【数据范围与提示】
对于 20% 的数据,n, m ≤ 5。
对于 40% 的数据,n, m ≤ 50。
对于 70% 的数据,n, m ≤ 300。
对于 100% 的数据,1 ≤ n, m ≤ 1000。方格中整数的绝对值不超过 10^4。
排水系统(water)
【题目描述】
对于一个城市来说,排水系统是极其重要的一个部分。有一天,小 C 拿到了某座城市排水系统的设计图。排水系统由 n 个排水结点(它们从 1 ∼ n 编号)和若干个单向排水管道构成。每一个排水结点有若干个管道用于汇集其他排水结点的污水(简称为该结点的汇集管道),也有若干个管道向其他的排水结点排出污水(简称为该结点的排出管道)。
排水系统的结点中有 m 个污水接收口,它们的编号分别为 1, 2, · · · , m,污水只能从这些接收口流入排水系统,并且这些结点没有汇集管道。排水系统中还有若干个最终排水口,它们将污水运送到污水处理厂,没有排出管道的结点便可视为一个最终排水口。
现在各个污水接收口分别都接收了 1 吨污水,污水进入每个结点后,会均等地从当前结点的每一个排出管道流向其他排水结点,而最终排水口将把污水排出系统。
现在小 C 想知道,在该城市的排水系统中,每个最终排水口会排出多少污水。该城市的排水系统设计科学,管道不会形成回路,即不会发生污水形成环流的情况。
【输入格式】
从文件 water.in 中读入数据。
第一个两个用单个空格分隔的整数 n,m。分别表示排水结点数与接收口数量。
接下来 n 行,第 i 行用于描述结点 i 的所有排出管道。其中每行第一个整数 di 表示其排出管道的数量,接下来 di 个用单个空格分隔的整数 a1, a2, · · · , adi 依次表示管道的目标排水结点。
保证不会出现两条起始结点与目标结点均相同的管道。
【输出格式】
输出到文件 water.out 中。
输出若干行,按照编号从小到大的顺序,给出每个最终排水口排出的污水体积。其中体积使用分数形式进行输出,即每行输出两个用单个空格分隔的整数 p,q,表示排出的污水体积为
要求 p 与 q 互素,q = 1 时也需要输出 q。
【样例 1 输入】
5 1
3 2 3 5
2 4 5
2 5 4
0
0
【样例 1 输出】
1 3
2 3
【样例 1 解释】

【数据范围】

对于所有测试点,保证

数据保证,污水在从一个接收口流向一个最终排水口的过程中,不会经过超过 10个中间排水结点(即接收口和最终排水口不算在内)。
字符串匹配(string)
【题目描述】
小 C 学习完了字符串匹配的相关内容,现在他正在做一道习题。
对于一个字符串 S,题目要求他找到 S 的所有具有下列形式的拆分方案数:S = ABC,S = ABABC,S = ABAB · · · ABC,其中 A,B,C 均是非空字符串,且 A 中出现奇数次的字符数量不超过 C 中出现奇数次的字符数量。
更具体地,我们可以定义 AB 表示两个字符串 A, B 相连接,例如 A = aab,B = ab,则 AB = aabab。
并递归地定义
例如 A = abb,则
则小 C 的习题是求
的方案数,其中 F(A) ≤ F(C),F(S ) 表示字符串 S中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 A、B、C 中有至少一个字符串不同。
小 C 并不会做这道题,只好向你求助,请你帮帮他。
【输入格式】
从文件 string.in 中读入数据。
本题有多组数据,输入文件第一行一个正整数 T 表示数据组数。
每组数据仅一行一个字符串 S,意义见题目描述。S 仅由英文小写字母构成。
【输出格式】
输出到文件 string.out 中。
对于每组数据输出一行一个整数表示答案。
【样例 1 输入】
3
nnrnnr
zzzaab
mmlmmlo
【样例 1 输出】
8
9
16
【样例 1 解释】
对于第一组数据,所有的方案为:
1. A=n,B=nr,C=nnr。
2. A=n,B=nrn,C=nr。
3. A=n,B=nrnn,C=r。
4. A=nn,B=r,C=nnr。
5. A=nn,B=rn,C=nr。
6. A=nn,B=rnn,C=r。
7. A=nnr,B=n,C=nr。
8. A=nnr,B=nn,C=r。
【样例 2 输入】
5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab
【样例 2 输出】
156
138
138
147
194
【数据范围】

对于所有测试点,保证
移球游戏(ball)
【题目描述】
小 C 正在玩一个移球游戏,他面前有 n + 1 根柱子,柱子从 1 ∼ n + 1 编号,其中1 号柱子、2 号柱子、· · ·、n 号柱子上各有 m 个球,它们自底向上放置在柱子上,n + 1号柱子上初始时没有球。这 n × m 个球共有 n 种颜色,每种颜色的球各 m 个。
初始时一根柱子上的球可能是五颜六色的,而小 C 的任务是将所有同种颜色的球移到同一根柱子上,这是唯一的目标,而每种颜色的球最后放置在哪根柱子则没有限制。
小 C 可以通过若干次操作完成这个目标,一次操作能将一个球从一根柱子移到另一根柱子上。更具体地,将 x 号柱子上的球移动到 y 号柱子上的要求为:
1. x 号柱子上至少有一个球;
2. y 号柱子上至多有 m − 1 个球;
3. 只能将 x 号柱子最上方的球移到 y 号柱子的最上方。
小 C 的目标并不难完成,因此他决定给自己加加难度:在完成目标的基础上,使用的操作次数不能超过 820000。换句话说,小 C 需要使用至多 820000 次操作完成目标。
小 C 被难住了,但他相信难不倒你,请你给出一个操作方案完成小 C 的目标。合法的方案可能有多种,你只需要给出任意一种,题目保证一定存在一个合法方案。
【输入格式】
从文件 ball.in 中读入数据。
第一行两个用空格分隔的整数 n,m。分别表示球的颜色数、每种颜色球的个数。
接下来 n 行每行 m 个用单个空格分隔的整数,第 i 行的整数按自底向上的顺序依次给出了 i 号柱子上的球的颜色。
【输出格式】
输出到文件 ball.out 中。
本题采用自定义校验器(special judge)评测。
你的输出的第一行应该仅包含单个整数 k,表示你的方案的操作次数。你应保证0 ≤ k ≤ 820000。
接下来 k 行每行你应输出两个用单个空格分隔的正整数 x, y,表示这次操作将 x 号柱子最上方的球移动到 y 号柱子最上方。你应保证 1 ≤ x, y ≤ n + 1 且 x , y。
【样例 1 输入】
2 3
1 1 2
2 1 2
【样例 1 输出】
6
1 3
2 3
2 3
3 1
3 2
3 2
柱子中的内容为:按自底向上的顺序依次给出柱子上每个球的颜色。
【样例 1 解释】

【数据范围】

对于所有测试点,保证 2 ≤ n ≤ 50,2 ≤ m ≤ 400。
微信步数(walk)
【题目描述】
小 C 喜欢跑步,并且非常喜欢在微信步数排行榜上刷榜,为此他制定了一个刷微信步数的计划。
他来到了一处空旷的场地,处于该场地中的人可以用 k 维整数坐标 (a1, a2, · · · , ak)来表示其位置。场地有大小限制,第 i 维的大小为 wi,因此处于场地中的人其坐标应满足 1 ≤ ai ≤ wi(1 ≤ i ≤ k)。
小 C 打算在接下来的 P = w1 × w2 × · · · × wk 天中,每天从场地中一个新的位置出发,开始他的刷步数计划(话句话说,他将会从场地中每个位置都出发一次进行计划)。
他的计划非常简单,每天按照事先规定好的路线行进,每天的路线由 n 步移动构成,每一步可以用 ci 与 di 表示:若他当前位于 (a1, a2, · · · , aci, · · · , ak),则这一步他将会走到 (a1, a2, · · · , aci + di, · · · , ak),其中 1 ≤ ci ≤ k,di ∈ {−1, 1}。小 C 将会不断重复这个路线,直到他走出了场地的范围才结束一天的计划。(即走完第 n 步后,若小 C 还在场内,他将回到第 1 步从头再走一遍)。
小 C 对自己的速度非常有自信,所以他并不在意具体耗费的时间,他只想知道 P天之后,他一共刷出了多少步微信步数。请你帮他算一算。
【输入格式】
从文件 walk.in 中读入数据。
第一行两个用单个空格分隔的整数 n,k。分别表示路线步数与场地维数。
接下来一行 k 个用单个空格分隔的整数 wi,表示场地大小。
接下来 n 行每行两个用单个空格分隔的整数 ci,di,依次表示每一步的方向,具体意义见题目描述。
【输出格式】
输出到文件 walk.out 中。
仅一行一个整数表示答案。答案可能很大,你只需要输出其对 109 + 7 取模后的值。
若小 C 的计划会使得他在某一天在场地中永远走不出来,则输出一行一个整数 -1。
【样例 1 输入】
3 2
3 3
1 1
2 -1
1 1
【样例 1 输出】
21
【样例 1 解释】
从 (1, 1) 出发将走 2 步,从 (1, 2) 出发将走 4 步,从 (1, 3) 出发将走 4 步。
从 (2, 1) 出发将走 2 步,从 (2, 2) 出发将走 3 步,从 (2, 3) 出发将走 3 步。
从 (3, 1) 出发将走 1 步,从 (3, 2) 出发将走 1 步,从 (3, 3) 出发将走 1 步。
共计 21 步。
【样例 2 输入】
5 4
6 8 6 5
3 1
2 1
1 1
2 1
2 -1
【样例 2 输出】
10265
【数据范围】

对于所有测试点,保证 1 ≤ n ≤ 5 × 105,1 ≤ k ≤ 10,1 ≤ wi ≤ 109,di ∈ {−1, 1}。