第二十三届全国青少年信息学奥林匹克联赛初赛含答案(WORD重新整理排版)-最新教育文档

4.

#include using namespace std; int main() { int n, m;

cin >> n >> m; int x = 1; int y = 1; int dx = 1; int dy = 1; int cnt = 0;

while (cnt != 2) { cnt = 0; x = x + dx; y = y + dy;

if (x == 1 || x == n) { ++cnt; dx = -dx;

if (y == 1 || y == m) { ++cnt; dy = -dy;

cout << x << \ return 0; 输入1： 4 3

输出1：__________（2分） 输入2：2019 1014

输出2：__________（3分） 输入3： 987 321

输出3：__________（3分）

五、完善程序 （共 共 2 题，每题 14 分 ， 共计 28 分 ）

100

1. （ 大整数除法） ）给定两个正整数p和q，其中p不超过10 ，q不超过100000，求 p 除以 q 的商和余数。（第一空 2 分，其余 3 分）

输入：第一行是 p 的位数 n，第二行是正整数 p，第三行是正整数 q。 输出：两行，分别是 p 除以 q 的商和余数。 #include 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';

第 6 页

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;

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

输入：第一行是结点数 n（不超过 100）和边数 m，接下来 m 行，每行两个整数 a，b，表示从结点 a 到结点 b 有一条有向边。结点标号从 0 到(n-1)。 输出：最长路径长度。

提示：先进行拓扑排序，然后按照拓扑序计算最长路径。 #include 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) ) { 第 7 页

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;

第 8 页

第二十三届全国青少年信息学奥林匹克联赛初赛

提高组参考答案

一、单项选择题（共15 题，每题1.5 分，共计22.5 分） 1 C 9 D 2 B 10 B 3 A 11 D 4 C 12 D 5 A 13 A 6 C 14 D 7 B 15 C 8 C 二、不定项选择题（共5 题，每题1.5 分，共计7.5 分；每题有一个或多个正确选项，没有部分分）

1 CD 2 C 3 D 4 BD 5 BD 三、问题求解（共2题，每题5分，共计10分） 1. 3

2. 4 （2 分）

9 （3 分）

四、阅读程序写结果（共4题，每题8分，共计32 分） 1. 15

2. 17 24 1 8 15 3. 8

4. 输出1：1 3 （2 分） 输出2：2019 1 （3 分） 输出3：1 321 （3 分）

五、完善程序（共计28分，以下各程序填空可能还有一些等价的写法，由各省赛区组织本省专家审定及上机验证，可以不上报CCF NOI科学委员会复核） 1 (1) (2) (3) (4) (5) 2 (1) (2) (3) (4) (5)

rest div q rest mod q * 10 + p[i] degree[b]:=degree[b]+1 或 inc(degree[b]) degree[i]=0 degree[i]:=degree[i]-1 或 dec(degree[i]) head:=head+1 或 inc(head) Pascal语言 C++语言 p[0] restrest rest / q rest % q * 10 + p[i] degree[b]=degree[b]+1 或 degree[b]++ 或 ++degree[b] degree[i]==0 或 !degree[i] degree[i]=degree[i]-1 或 degree[i]-- 或 --degree[i] head=head+1 或 head++ 或 ++head rest mod q rest % q C 语言 分值 2 3 3 3 3 3 3 3 3 2 ansans 第 9 页