信息学奥赛-提高级 题库
(2.5分)若输入的第一个字符串长度由100个不同的字符构成,第二 个字符串是第一个字符串的倒序,输入的m为0,则输岀为()。
(4分)若两个字符串的长度均为n, 且0<m<n-1,且两个字符串的构 成相同(即任何一个字符在两个字符串中出现的次数均相同),则下列 说法正确的是()。提示:考虑输入与输出有多少对字符前后顺序不 一样。
强连通图的性质不包括( ):
每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正规图,其中包含欧拉回路的不同 2 正规图的数量为( )
有正实数构成的数字三角形排列形式如图所示。第一行的数为a1,1;第二行的数从左到右依次为a2,1,a2,2,第n行的数为an,1,an,2,…,an,n。从a1,1开始,每一行的数ai,j只有两条边可以分别通向下一行的两个数ai+1,j和ai+1,j+1。用动态规划算法找出一条从a1,1向下通道an,1,an,2,…,an,n中某个数的路径,使得该路径上的数之和最大。

令C[i][j]是从a1,1到ai,j的路径上的数的最大和,并且C[i][0]= C[0][j]=0,则C[i][j]=( )
G 是一个非连通简单无向图(没有自环和重边),共有 36 条边,则该图至少有( )个点。
设一个三位数
a, b, c 均为 1~9 之间的整数,若以 a、 b、 c 作为三角形的三条边可以构成等腰三角形(包括等边),则这样的 n 有( )个。
在一条长度为 1 的线段上随机取两个点,则以这两个点为端点的线段的期望长度是( )。
生产线测试
题目背景
工厂打算通过客户反馈来间接测试生产线,从而找到存在缺陷的生产线。工厂有n条生产线(编号0~n-1),已知其中恰有一条生产线存在缺陷。每一轮测试为,从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品,客户将要求退货(结果记为1),否则正常收货(记为0)。受售后压力限制,在所有发货批次中,最多只能有k次退货(即结果为1的次数≤k)。工厂的目标是,设计最少的间接测试轮数w(发货总批次),保证根据客户收货或退货的反馈结果,唯一确定存在缺陷的生产线。
以下程序实现了工厂的目标,包含两部分:
i) 确定w的最小值,并设计最优测试方案;
ii) 根据测试结果推断存在缺陷的生产线。
该程序确定w最小值的方法为:由于不同的生产线故障时,测试应当返回不同的结果,因此w轮测试的可能结果数不应少于生产线数量。
`test_subset()` 函数为抽象测试接口,输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现在此处未给出。
`test_subset()` 函数为抽象测试接口,输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现在此处未给出。
试补全程序。
密码锁(lock)
【题目描述】
小Y有一把五个拨圈的密码锁。如图所示,每个拨圈上是从0到9的数字。每个拨圈都是从0到9的循环,即9拨动一个位置后可以变成0或8,

图1:密码锁
因为校园里比较安全,小Y采用的锁车方式是:从正确密码开始,随机转动密码锁仅一次;每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。当小Y选择同时转动两个相邻拨圈时,两个拨圈转动的幅度相同,即小Y可以将密码锁从00115转成11115,但不会转成12115。
时间久了,小Y也担心这么锁车的安全性,所以小Y记下了自己锁车后密码锁的n个状态,注意这n个状态都不是正确密码。
为了检验这么锁车的安全性,小Y有多少种可能的正确密码,使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部n个状态。
【输入格式】
从文件lock.in中读入数据。
输入的第一行包含一个正整数n,表示锁车后密码锁的状态数。
接下来n行每行包含五个整数,表示一个密码锁的状态。
【输出格式】
输出到文件lock.out中。
输出一行包含一个整数,表示密码锁的这n个状态按照给定的锁车方式能对应多少种正确密码。
【样例1输入】
【样例1输出】
【样例1解释】
一共有81种可能的方案。
其中转动一个拨圈的方案有45种,转动两个拨圈的方案有36种。
【样例2】
见选手目录下的lock/lock2.in与lock/lock2.ans。


消消乐(game)
【题目描述】
小L现在在玩一个低配版本的消消乐,该版本的游戏是一维的,一次也只能消除两个相邻的元素。
现在,他有一个长度为n且仅由小写字母构成的字符串。我们称一个字符串是可消除的,当且仅当可以对这个字符串进行若干次操作,使之成为一个空字符串。
其中每次操作可以从字符串中删除两个相邻的相同字符,操作后剩余字符串会拼接在一起。
小L想知道,这个字符串的所有非空连续子串中,有多少个是可消除的。
【输入格式】
从文件game.in中读入数据。
输入的第一行包含一个正整数n,表示字符串的长度。
输入的第二行包含一个长度为n且仅由小写字母构成的的字符串,表示题目中询问的字符串。
【输出格式】
输出到文件game.out中。
输出一行包含一个整数,表示题目询问的答案。
【样例1输入】
【样例1输出】
【样例1解释】
一共有5个可消除的连续子串,分别是cc、acca、cc、bccb、accabccb。
【样例2】
见选手目录下的game/game2.in与game/game2.ans。
【样例3】
见选手目录下的game/game3.in与game/game3.ans。
【样例4】
见选手目录下的game/game4.in与game/game4.ans。

题解1:

题解2:

题解3:

(第k小路径)给定一张n个点m条边的有向无环图,顶点编号从0到n-1对于一条路径,我们定义"路径序列"为该路径从起点出发依次经过的顶点编号构成的序列。求所有至少包含一个点的简单路径中,“路径序列”字典序第k小的路径。保证存在至少k条路径。上述参数满足1≤n,m≤105和1≤k≤1018。
在程序中,我们求出从每个点出发的路径数量。超过1018的数都用1018表示。然后我们根据k的值和每个顶点的路径数量,确定路径的起点,然后可以类似地依次求出路径中的每个点。
试补全程序。

(归并第 k 小)已知两个长度均为 n 的有序数组 a1 和 a2(均为递增序,但不保证严格单调递增),并且给定正整数 k(1≤k≤2n),求数组 a1 和 a2 归并排序后的数组里第 k 小的数值。
试补全程序。
#include <bits/stdc++.h>
using namespace std;
int solve(int *a1, int *a2, int n, int k) {
int left1 = 0, right1 = n - 1;
int left2 = 0, right2 = n - 1;
while (left1 <= right1 && left2 <= right2) {
int m1 = (left1 + right1) >> 1;
int m2 = (left2 + right2) >> 1;
int cnt = ① ;
if ( ② ) {
if (cnt < k) left1 = m1 + 1;
else right2 = m2 - 1;
} else {
if (cnt < k) left2 = m2 + 1;
else right1 = m1 - 1;
}
}
if ( ③ ) {
if (left1 == 0) {
return a2[k - 1];
} else {
int x = a1[left1 - 1], ④ ;
return std::max(x, y);
}
} else {
if (left2 == 0) {
return a1[k - 1];
} else {
int x = a2[left2 - 1], ⑤ ;
return std::max(x, y);
}
}
}
(最优子序列)取m=6,给出长度为n的整数序列a1,a2,……an(0 ≤ ai<2m)。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1,b2,…,bk,定 义其子序列分值S为w(b1㊉b2)+w(b2㊉b3)+w(b3㊉b4)+……+w(bk-1㊉bk)。其中㊉表示按位异或。对于空子序列,规定其子序列分值为0。求一个子序列使得其子序列分值最大,输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1,a2,……,an。
提示:考虑优化朴素的动态规划算法,将前
位和后
位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。

(最优子序列)取m=6,给出长度为n的整数序列a1,a2,……an(0 ≤ ai<2m)。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1,b2,…,bk,定 义其子序列分值S为w(b1㊉b2)+w(b2㊉b3)+w(b3㊉b4)+……+w(bk-1㊉bk)。其中㊉表示按位异或。对于空子序列,规定其子序列分值为0。求一个子序列使得其子序列分值最大,输出这个最大值。
输入第一行包含一个整数n(1 ≤ n ≤ 40000).接下来一行包含n个整数 a1,a2,……,an。
提示:考虑优化朴素的动态规划算法,将前
位和后
位分开计算。
Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。
试补全程序。
