首页 › 题库 › 信息学奥赛 › 信息学奥赛-提高级

信息学奥赛-提高级 题库

共 842 道题 ,第 33 / 43 页 · 按题型筛选,点「查看答案」核对解析
641 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(大整数除法)给定两个正整数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

题目详情
642 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 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

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

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

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

可以将单个计算机接入到计算机网络中的网络接入通讯设备有( )。

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

下列算法中运用分治思想的有( )。

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

下图表示一个果园灌溉系统,有A、B、C、D四个阀门,每个阀门可以打开或关上,所有管道粗细相同,以下设置阀门的方法中,可以让果树浇上水的有( )。

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

参加NOI比赛,以下能带入考场的有( )。

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

一个 1×8 的方格图形(不可旋转)用黑、白两种颜色填涂每个方格。如果每个方格只能填涂一种颜色,且不允许两个黑格相邻,共有_________种填 涂方案。


答案与解析
参考答案

55

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

某中学在安排期末考试时发现,有7个学生要参加7门课程的考试,下表列出了哪些学生参加哪些考试(用√表示要参加相应的考试)。 最少要安排_________个不同的考试时间段才能避免冲突?

答案与解析
参考答案

3

题目详情
650 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
using namespace std;

int main() 
{
	int a[6] = {1, 2, 3, 4, 5, 6}; 
	int pi = 0;
	int pj = 5; 
	int t , i;
	while (pi < pj) {
		t = a[pi]; 
		a[pi] = a[pj]; 
		a[pj] = t; 
		pi++;
		pj--;
	}
	for (i = 0; i < 6; i++) 
	cout << a[i] << ",";
	cout << endl; 
	return 0;
}

输出:                       

答案与解析
参考答案

6,5,4,3,2,1,

题目详情
651 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
using namespace std;
int main() 
{
	char a[100][100], b[100][100]; 
	string c[100];
	string tmp;
	int n, i = 0, j = 0, k = 0, total_len[100], length[100][3];
		cin >> n; 
		getline(cin, tmp);
		for (i = 0; i < n; i++) { 
			getline(cin, c[i]);
			total_len[i] = c[i].size();
		}
		for (i = 0; i < n; i++) {
			j = 0;
			while (c[i][j] != ':') { 
				a[i][k] = c[i][j];
				k = k + 1; 
				j++;
			}
			length[i][1] = k - 1; 
			a[i][k] = 0;
			k = 0;
			for (j = j + 1; j < total_len[i]; j++) { 
				b[i][k] = c[i][j];
				k = k + 1;
			}
			length[i][2] = k - 1; 
			b[i][k] = 0;
			k = 0;
		}
		for (i = 0; i < n; i++) {
			if (length[i][1] >= length[i][2]) 
				cout << "NO,";
			else {
				k = 0;
				for (j = 0; j < length[i][2]; j++) { 
					if (a[i][k] == b[i][j])
						k = k + 1;
					if (k > length[i][1]) 
						break;
				}
				if (j == length[i][2]) 
					cout << "NO,";
				else
					cout << "YES,";
			}
	}
	cout << endl;
	return 0;
}

输入:

3 

AB:ACDEbFBkBD 

AR:ACDBrT

SARS:Severe Atypical Respiratory Syndrome 

输出:                                  

(注:输入各行前后均无空格)

答案与解析
参考答案

YES,NO,YES,

题目详情
652 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include<iostream> 
using namespace std;
int lps(string seq, int i, int j) { 
	int len1, len2;
	if (i == j) 
		return 1;
	if (i > j) 
		return 0;
	if (seq[i] == seq[j])
		return lps(seq, i + 1, j - 1) + 2; 
	len1 = lps(seq, i, j - 1);
	len2 = lps(seq, i + 1, j); 
	if (len1 > len2)
		return len1; 
	return len2;
}
int main() 
{
	string seq = "acmerandacm"; 
	int n = seq.size();
	cout << lps(seq, 0, n - 1) << endl; 
	return 0;
}

输出:          

答案与解析
参考答案

5

题目详情
653 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
#include <cstring> 
using namespace std;
int map[100][100];
int sum[100], weight[100]; 
int visit[100];
int n;
void dfs(int node) { 
	visit[node] = 1; 
	sum[node] = 1; 
	int v, maxw = 0;
	for (v = 1; v <= n; v++) {
		if (!map[node][v] || visit[v]) 
			continue;
		dfs(v);
		sum[node] += sum[v]; 
		if (sum[v] > maxw) 
			maxw = sum[v];
	}
	if (n - sum[node] > maxw) 
		maxw = n - sum[node];
	weight[node] = maxw;
}
int main() 
{
	memset(map, 0, sizeof(map)); 
	memset(sum, 0, sizeof(sum)); 
	memset(weight, 0, sizeof(weight)); 
	memset(visit, 0, sizeof(visit)); 
	cin >> n;
	int i, x, y;
	for (i = 1; i < n; i++) { 
		cin >> x >> y; 
		map[x][y] = 1; 
		map[y][x] = 1;
	}
	dfs(1);
	int ans = n, ansN = 0; 
	for (i = 1; i <= n; i++)
		if (weight[i] < ans) { 
			ans = weight[i]; 
			ansN = i;
		}
	cout << ansN << " " << ans << endl; 
	return 0;
}

输入:

1 1

1 2

1 3

2 4

2 5

2 6

3 7

7 8

7 11

6 9

9 10

输出:

                

答案与解析
参考答案

2 5

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

(交朋友)根据社会学研究表明,人们都喜欢找和自己身高相近的人做朋友。

现在有n名身高两两不相同的同学依次走入教室,调查人员想预测每个人在走入教室的瞬间最想和已经进入教室的哪个人做朋友。当有两名同学和这名同学的身高差一样时,这名同学会更想和高的那个人做朋友。比如一名身高为1.80米的同学进入教室时,有一名身高为1.79米的同学和一名身高为1.81米的同学在教室里,那么这名身高为1.80米的同学会更想和身高为1.81米的同学做朋友。对于第一个走入教室的同学我们不做预测。

由于我们知道所有人的身高和走进教室的次序,所以我们可以采用离线的做法来解决这样的问题,我们用排序加链表的方式帮助每一个人找到在他之前进入教室的并且和他身高最相近的人。(第一空2分,其余3分)

#include <iostream> 

using namespace std; 

#define MAXN 200000

#define infinity 2147483647


int answer[MAXN], height[MAXN], previous[MAXN], next[MAXN]; 

int rank[MAXN];

int n;


void sort(int l, int r) {

int x = height[rank[(l + r) / 2]], i = l, j = r, temp; 

while (i <= j)

{

while (height[rank[i]] < x) i++; 

while (height[rank[j]] > x) j--;

if (      (1)      ) {

temp = rank[i]; rank[i] = rank[j]; rank[j] = temp;

i++; j--;

}

}

if (i < r) sort(i, r); 

if (l < j) sort(l, j);

 }

int main()

{

cin >> n;

int i, higher, shorter; 

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

cin >> height[i]; 

rank[i] = i;

sort(1, n);

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

previous[rank[i]] = rank[i - 1];

                           (2)        ;

}

for (i = n; i >= 2; i--){

higher = shorter = infinity;

if (previous[i] !=0)

shorter = height[i] - height[previous[i]]; if 

(next[i] != 0)

                          (3)           ;

if (      (4)      )

answer[i] = previous[i];

else

answer[i] = next[i];

next[previous[i]] = next[i];

                (5)       ;

}

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

cout << i << ":" << answer[i]; 

return 0;

}

答案与解析
参考答案

(1)i<=j

(2)next[rank[i]]=rank[i+1]

(3)higher=height[next[i]]-height[i]

(4)shorter<higher

(5)previous[next[i]]=previous[i]

题目详情
655 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

 (交通中断)有一个小国家,国家内有n座城市和m条双向的道路,每条道路连接着两座不同的城市。其中1号城市为国家的首都。由于地震频繁可能导致某一个城市与外界交通全部中断。这个国家的首脑想知道,如果只有第i(i>1)个城市因地震而

导致交通中断时,首都到多少个城市的最短路径长度会发生改变。如果因为无法通过第i个城市而导致从首都出发无法到达某个城市,也认为到达该城市的最短路径长度改变。

对于每一个城市i,假定只有第i个城市与外界交通中断,输出有多少个城市会因此导致到首都的最短路径长度改变。

我们采用邻接表的方式存储图的信息,其中head[x]表示顶点x的第一条边的编号,next[i]表示第i条边的下一条边的编号,point[i]表示第i条边的终点,weight[i]表示第i条边的长度。(第一空2分,其余3分)


#include <iostream> 

#include <cstring> 

using namespace std;

#define MAXN 6000 

#define MAXM 100000

#define infinity 2147483647


int head[MAXN], next[MAXM], point[MAXM], weight[MAXM]; 

int queue[MAXN], dist[MAXN], visit[MAXN];

int n, m, x, y, z, total = 0, answer;


void link(int x,int y,int z) { 

total++;

next[total] = head[x]; 

head[x] = total; 

point[total] = y; 

weight[total] = z; 

total++;

next[total] = head[y]; 

head[y] = total; 

point[total] = x; 

weight[total] = z;

}

int main() {

int i, j, s, t; 

cin >> n >> m;

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

cin >> x >> y >> z; link(x, y, z);

}

for (i = 1; i <= n; i++) dist[i] = infinity;

                 (1)       ;

queue[1] = 1; 

visit[1] = 1; 

s = 1;

t = 1;

// 使用 SPFA 求出第一个点到其余各点的最短路长度

while (s <= t) {

x = queue[s % MAXN];

j = head[x];

while (j != 0) {

if (      (2)      ) {

dist[point[j]] = dist[x] + weight[j];

if (visit[point[j]] == 0) {

t++;

queue[t % MAXN] = point[j];

visit[point[j]] = 1;

}

}

j = next[j];

}

                      (3)         ;

s++;

}

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

queue[1] = 1;

memset(visit, 0, sizeof(visit));

visit[1] = 1;

s = 1;

t = 1;

while (s <= t) { // 判断最短路长度是否不变

x = queue[s];

j = head[x];

while (j != 0) {

if (point[j] != i &&      (4)      

&&visit[point[j]] == 0) {

              (5)       ;

t++;

queue[t] = point[j];

}

j = next[j];

}

s++;

}

answer = 0;

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

answer += 1 - visit[j];

cout << i << ":" << answer - 1 << endl;

}return 0;

}

答案与解析
参考答案

(1)dist[1]=0

(2) dist[x]+weight[j]<dist[point[j]]

(3)visit[x]=0

(4)dist[x]+weight[j]==dist[point[j]]

(5)visit[point[j]]=1

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

以下属于操作系统的有( )。

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

下列属于视频文件格式的有( )。

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

下列选项不是正确的IP地址的有( )。

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

下列有关树的叙述中,叙述正确的有( )。

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

以下图中一定可以进行黑白染色的有( )。(黑白染色:为各个结点分别指定黑白两种颜色之一,使相邻结点颜色不同。)

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