首页 › 题库 › 信息学奥赛 › 1 数据结构进阶

信息学奥赛-提高级 题库

共 682 道题 ,第 27 / 35 页 · 按题型筛选,点「查看答案」核对解析
章节 1 数据结构进阶 清除
521 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

#include <cstdio>

using namepace std ;


const int maxn =1000;

int n;

int fa[maxn],cnt [maxn];


int getroot(int v ) {

if (fa[v] == v) return v;

return getroot(fa[v]);

}


int main ( ) {

cin >> n;

for (int i =0;i<n;++i){

fa[i]=i;

cnt[i]=1;

}

int ans = 0 ;

for (int i=0; i<n - 1; ++i){

int a,b,x,y,;

cin >>a>>b

x=getRoot(a);

y=getRoot(b);

ans +=cnt[x]cnt[y];

fa[x]=y;

cnt[y] +=cnt[x];

}

cout<<ans<<endl;

return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
522 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

本题t是s的子序列的意思是:从s中删去若干个字符,可以得到t;特别的,如果s=t,那么t也是s的子序列;空串是任何串的子序列。例如“acd”是“abcde”的子序列,“acd”是“acd”的子序列,但“adc”不是“abcde”的子序列。

S[x…y]表示s[x]…s[y]共y-x+1个字符构成的字符串,若x>y则s[x…y]是空串。t[x…y]同理。

#include <cstdio>

#include <algorithm>

using namespace std;

const int max1 = 202;

string s, t ;

int pre[max1], suf[max1]


int main() {

cin>>s>>t;

int slen =s. length(), tlen= t. length();

for (int I = 0 ,j = 0 ; i< slen; ++i) {

if (j< tlen&&s[i]t[j] ) ++j;

pre[i] = j;// t[0…j-1]是s[0…i]的子序列

 }

for (int I = slen -1 ,j= tlen -1; I >=0;–i) {

if(j>=0&& s[i] == t [j]) –j;

suf [i]= j; //t[j+1…tlen-1]是s[i…slen-1]的子序列

}

suf[slen] = tlen -1;

int ans = 0;

for (int i=0, j=0, tmp=o; i<=slen; ++i){

while(j<=slen && tmp >=suf[j] + 1) ++j;

ans =max(ans, j – I – 1);

tmp = pre[i];

}

cout <<ans << end1;

return 0;

}

提示:

t[0…pre[i]-1]是s[0…i]的子序列;

t[suf[i]+1…tlen-1]是s[i…slen-1]的子序列。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
523 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.4 并查集

(匠人的自我修养)一个匠人决定要学习n个新技术,要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最多能学会多少个新技术。

输入第一行有两个数,分别为新技术个数n(1≤n≤103),以及已有经验值(≤107)。

接下来n行。第i行的两个正整数,分别表示学习第i个技术所需的最低经验值(≤107),以及学会第i个技术后可获得的经验值(≤104)。

接下来n行。第i行的第一个数mi(0≤mi<n),表示第i个技术的相关技术数量。紧跟着m个两两不同的数,表示第i个技术的相关技术编号,输出最多能学会的新技术个数。

下面的程序已O(n2)的时间复杂完成这个问题,试补全程序。

#inclde

using namesoace std;

const int maxn = 1001;


int n;

int cnt [maxn]

int child [maxn] [maxn];

int unlock[maxn];

int unlock[maxn];

int threshold [maxn],bonus[maxn];


bool find(){

int target=-1;

for (int i = 1;i<=n;++i)

if(①&&②){

target = i;

break;

}

if(target-1)

return false;

unlock[target]=-1;

③;

for (int i=0;i<cut[target];++i)

④;

return true;

}


int main(){

scanf(“%d%d”,&n, &points);

for (int I =1; i<=n;++i={

cnt [i]=0;

scanf(“%d%d”,&threshold[i],&bonus[i];

}

for (int i=1;i<=n;++i={

int m;

scanf(“%d”,&m);

⑤;

for (int j=0; j<m ;++j={

int fa;

scanf(“%d”, &fa);

child [fa][cnt[fa]]=i;

++cnt[fa];

}

}

int ans = 0;

while(find())

++ans;

printf(“%d\n”, ans);

return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
524 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(取石子)Alice和Bob两个人在玩取石子游戏。他们制定了n条取石子的规则,第i条规则为:如果剩余石子的个数大于等于a[i]且大于等于b[il, 那么他们可以取走b[i]个石子。他们轮流取石子。如果轮到某个人取石子, 而他无法按照任何规则取走石子,那么他就输了。一开始石子有m个。请问先取石子的人是否有必胜的方法?

输入第一行有两个正整数,分别为规则个数n(1≤n≤64),以及石子个数m(≤10^7)。

接下来n行。第i行有两个正整数a[i]和b[i](1≤a[i]≤10^7,1≤b[i]≤64)

如果先取石子的人必胜,那么输出“Win”,否则输出“Loss”

提示:

 可以使用动态规划解决这个问题。由于b[i]不超过64,所以可以使用64位无符号整数去压缩必要的状态。

 status是胜负状态的二进制压缩,trans是状态转移的二进制压缩。

试补全程序。

代码说明:

 “~”表示二进制补码运算符,它将每个二进制位的0变成1、1变为0; 

 而“^”表示二进制异或运算符,它将两个参与运算的数中的每个对应的二进制位一一进行比较,若两个二进制位相同,则运算结果的对应二进制位为0,反之为1。

ull标识符表示它前面的数字是unsigned long long 类型。

#include <cstdio>

#include<algorithm>

using namespace std ;


const int maxn =64;


int n,m;

int a[maxn],b[maxn];

unsigned long long status ,trans;

bool win;


int main() {

scanf("%d%d", &n, &m);

for (int i = 0; i<n; ++i)

scanf("%d%d", &a[i], &b[i]);

for(int i = 0; i < n; ++i)

for(int j = i + 1; j < n; ++j)

if (a[i] > a[j]) {

swap(a[i],a[j]);

swap(b[i],b[j]);

}

status = ___(1)___;

trans = 0;

for(int i = 1, j = 0; i <= m; ++i) {

while (j < n && ___(2)___) {

___(3)___

++j;

}

win = ___(4)___;

___(5)___;

}

puts(win ? "Win" : "Loss");

return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
525 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

NOIP初赛中,选手可以带入考场的有( )。

答案与解析
正确答案:A,B
这道题暂未补解析。
题目详情
526 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

2-3树是一种特殊的树,它满足两个条件:

(1)每个内部结点有两个或三个子结点;

(2)所有的叶结点到根的路径长度相同。

如果一棵2-3树有10个叶结点,那么它可能有( )个非叶结点。

答案与解析
正确答案:C,D
这道题暂未补解析。
题目详情
527 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

下列说法中,是树的性质的有( )。

答案与解析
正确答案:A,B,D
这道题暂未补解析。
题目详情
528 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

下列关于图灵奖的说法中,正确的有( )。(2018年提高组)

答案与解析
正确答案:B,C,D
这道题暂未补解析。
题目详情
529 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

甲乙丙丁四人在考虑周末要不要外出郊游。

已知①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不去。如果周末丙去了,则甲________(去了/没去)(1 分),乙________(去了/没去)(1 分),丁________(去了/没去)(1 分),周末________(下雨/没下雨)(2 分)。(2018年提高组)

答案与解析
参考答案

去了

没去

没去

没下雨

题目详情
530 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

方程 a*b = (a or b) * (a and b),在 a,b 都取 [0, 31] 中的整数时,共有_____组解。(*表示乘法;or 表示按位或运算;and 表示按位与运算)(2018年提高组)

答案与解析
参考答案

454

题目详情
531 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

一只小猪要买 N 件物品(N 不超过 1000)。

它要买的所有物品在两家商店里都有卖。第 i 件物品在第一家商店的价格是a[i],在第二家商店的价格是 b[i],两个价格都不小于 0 且不超过 10000。如果在第一家商店买的物品的总额不少于 50000,那么在第一家店买的物品都可以打 95 折(价格变为原来的 0.95 倍)。

求小猪买齐所有物品所需最少的总额。

输入:第一行一个数 N。接下来 N 行,每行两个数。第 i 行的两个数分别代表 a[i],b[i]。

输出:输出一行一个数,表示最少需要的总额,保留两位小数。

试补全程序。(第一空 2 分,其余 3 分)


#include <cstdio>

#include <algorithm>

using namespace std;


const int Inf = 1000000000;

const int threshold = 50000;

const int maxn = 1000;


int n, a[maxn], b[maxn];

bool put_a[maxn];

int total_a, total_b;

double ans;

int f[threshold];


int main() {

scanf("%d", &n);

total_a = total_b = 0;

for (int i = 0; i < n; ++i) {

scanf("%d%d", a + i, b + i);

if (a[i] <= b[i]) total_a += a[i];

else total_b += b[i];

}

ans = total_a + total_b;

total_a = total_b = 0;

for (int i = 0; i < n; ++i) {

if (      (1)      ) {

put_a[i] = true;

total_a += a[i];

} else {

put_a[i] = false;

total_b += b[i];

}

}

if (      (2)      ) {

printf("%.2f", total_a * 0.95 + total_b);

return 0;

}

f[0] = 0;

for (int i = 1; i < threshold; ++i)

f[i] = Inf;

int total_b_prefix = 0;

for (int i = 0; i < n; ++i)

if (!put_a[i]) {

total_b_prefix += b[i];

for (int j = threshold - 1; j >= 0; --j) {

if (      (3)      >= threshold && f[j] != Inf)

ans = min(ans, (total_a + j + a[i]) * 0.95

                                +       (4)      );

f[j] = min(f[j] + b[i], j >= a[i] ?      (5)      : Inf);

}

}

printf("%.2f", ans);

return 0;

}

答案与解析
参考答案

(1)a[i] * 0.95 <= b[i] 或 b[i] >= a[i] * 0.95

(2)total_a >= threshold 或 threshold <= total_a 或 total_a >= 50000 或 50000 <= total_a

(3)total_a + j + a[i]

(4)f[j] + total_b - total_b_prefix

(5)f[j - a[i]]

题目详情
532 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

对于入栈顺序为a,b,c,d,e,f,g的序列,下列( )不可能是合法的出栈序列

答案与解析
正确答案:C
这道题暂未补解析。
题目详情
533 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

下列算法中,( )是稳定的排序算法。

答案与解析
正确答案:D
这道题暂未补解析。
题目详情
534 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

以下是面向对象的高级语言的有( )。

答案与解析
正确答案:B,D
这道题暂未补解析。
题目详情
535 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

以下和计算机领域密切相关的奖项有( )。

答案与解析
正确答案:B,D
这道题暂未补解析。
题目详情
536 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

如右图所示,共有13个格子。对任何一个格子进行一次操作,会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0,或由0变1)。现在要使得所有的格子中的数字都变为0,至少需要      次操作。

答案与解析
参考答案

3

题目详情
537 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

如下图所示,A到B是连通的。假设删除一条细的边的代价是1,删除一条粗的边的代价是2,要让A、B不连通,最小代价是_____(2分),最小代价的不同方案数是_______(3分)。(只要有一条删除的边不同,就是不同的方案)

答案与解析
参考答案

4

9

题目详情
538 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(大整数除法)给定两个正整数p和q,其中p不超过10100,q不超过100000,

求p除以q的商和余数。(第一空2分,其余3分)

输入:第一行是p的位数n,第二行是正整数p,第三行是正整数q。

输出:两行,分别是p除以q的商和余数。


#include <iostream>

using namespace std;


int p[100];

int n, i, q, rest;

char c;


int main() {

cin >> n;

for (i = 0; i < n; i++) {

cin >> c;

p[i] = c - '0';

}

cin >> q;

rest =      (1)      ;

i = 1;

while (      (2)      && i < n) {

rest = rest * 10 + p[i];

i++;

}

if (rest < q)

cout << 0 << endl;

else {

cout <<      (3)      ;

while (i < n) {

rest =      (4)      ;

i++;

cout << rest / q;

}

cout << endl;

}

cout <<      (5)      << endl;

return 0;

}

答案与解析
参考答案

(1)p[0]

(2)rest<q 或 q>rest

(3)rest / q

(4)rest % q * 10 + p[i]

(5)rest % q

题目详情
539 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(最长路径)给定一个有向无环图,每条边长度为1,求图中的最长路径长度。(第五空2分,其余3分)

输入:第一行是结点数n(不超过100)和边数m,接下来m行,每行两个整数a,b,表示从结点a到结点b有一条有向边。结点标号从0到(n-1)。

输出:最长路径长度。

提示:先进行拓扑排序,然后按照拓扑序计算最长路径。


#include <iostream>

using namespace std;


int n, m, i, j, a, b, head, tail, ans;

int graph[100][100]; // 用邻接矩阵存储图

int degree[100]; // 记录每个结点的入度

int len[100]; // 记录以各结点为终点的最长路径长度

int queue[100]; // 存放拓扑排序结果


int main() {

cin >> n >> m;

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

graph[i][j] = 0;

for (i = 0; i < n; i++)

degree[i] = 0;

for (i = 0; i < m; i++) {

cin >> a >> b;

graph[a][b] = 1;

                 (1)           ;

}

tail = 0;

for (i = 0; i < n; i++)

if (      (2)      ) {

queue[tail] = i;

tail++;

}

head = 0;

while (tail < n - 1) {

for (i = 0; i < n; i++)

if (graph[queue[head] ][i] == 1) {

                               (3)        ;

if (degree[i] == 0) {

queue[tail] = i;

tail++;

}

}

                  (4)        ;

}

ans = 0;

for (i = 0; i < n; i++) {

a = queue[i];

len[a] = 1;

for (j = 0; j < n; j++)

if (graph[j][a] == 1 && len[j] + 1 > len[a])

len[a] = len[j] + 1;

if (      (5)      )

ans = len[a];

}

cout << ans << endl;

return 0;

}

答案与解析
参考答案

(1)degree[b]=degree[b]+1 或 degree[b]++ 或 ++degree[b]

(2)degree[i]==0 或 !degree[i]

(3)degree[i]=degree[i]-1 或 degree[i]-- 或 --degree[i]

(4)head=head+1 或 head++ 或 ++head

(5)ans<len[a] 或 len[a]>ans

题目详情
540 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

以下属于无线通信技术的有( )。

答案与解析
正确答案:A,B,C
这道题暂未补解析。
题目详情