首页 › 题库 › 信息学奥赛 › 信息学奥赛-入门级

信息学奥赛-入门级 题库

共 1088 道题 ,第 41 / 55 页 · 按题型筛选,点「查看答案」核对解析
801 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

#include <cstdio>

#include <cstring>

using namespace std;

char st[100];

int main() {

    scanf("%s", st);

    int n = strlen(st);

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

        if (n % i == 0) {

            char c = st[i - 1];

            if (c >= 'a')

                st[i - 1] = c - 'a' + 'A';

        }

    }

    printf("%s", st);

    return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
802 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

#include<cstdio>

using namespace std;

int n, m;

int a[100], b[100];

int main() {

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

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

        a[i] = b[i] = 0;

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

        int x, y;

        scanf("%d%d", &x, &y);

        if (a[x] < y && b[y] < x) {

            if (a[x] > 0)

                b[a[x]] = 0;

            if (b[y] > 0)

                a[b[y]] = 0;

            a[x] = y;

            b[y] = x;

        }

    }

    int ans = 0;

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

        if (a[i] == 0)

            ++ans;

        if (b[i] == 0)

            ++ans;

    }

    printf("%d", ans);

    return 0;

}

假设输入的n和m都是正整数,x和y都是在[1, n]的范围内的整数,完成下 面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
803 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

#include <iostream>

using namespace std;

const int maxn = 10000;

int n;

int a[maxn];

int b[maxn];

int f(int l, int r, int depth) {

    if (l > r)

        return 0;

    int min = maxn, mink;

    for (int i = l; i <= r; ++i) {

        if (min > a[i]) {

            min = a[i];

            mink = i;

        }

    }

    int lres = f(l, mink - 1, depth + 1);

    int rres = f(mink + 1, r, depth + 1);

    return lres + rres + depth * b[mink];

}

int main() {

    cin >> n;

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

        cin >> a[i];

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

        cin >> b[i];

    cout << f(0, n - 1, 1) << endl;

    return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
804 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(矩阵变幻)有一个奇幻的矩阵,在不停的变幻,其变幻方式为:数字0变成 矩阵

0  0

0  1

数字1变成矩阵

1  1

1  0

最初该矩阵只有一个元素0,变幻n次后,矩阵会变成什么样?

例如,矩阵最初为:[0]:矩阵变幻1次后:

0  0

0  1

矩阵变幻2次后:

0  0  0  0

0  1  0  1

0  0  1  1

0  1  1  0

输入一行一个不超过10的正整数n输出变幻n次后的矩阵。试补全程序。

提示:

“«” 表示二进制左移运算符,例如(11)_2 «2 = (1100)_2(11)2«2=(1100)2;而“^”表示二进制异或运算符,它将两个参与运算的数中的每个对应的二进制 位一进行比较,若两个二进制位相同,则运算结果的对应二进制位为0 ,反之 为1。

#include <cstdio>

using namespace std;

int n;

const int max_size = 1<<10;

int res[max_size][max_size]; 

void recursive(int x, int y, int n,int t){

    if(n==0){

        res[x][y]= ① ;

        return ;

    }

    int step = 1<< (n-1);

    recursive( ②,n-1,t);

    recursive(x,y+step,n-1,t);

    recursive(x+step,y,n-1,t);

    recursive( ③ ,n-1,!t);

}

int main(){

    scanf("%d",&n);

    recursive(0,0,④ );

    int size = ⑤;

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

        for(int j=0;j<size;j++)

            printf("%d",res[i][j]);

        puts(" ");

    }

    return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
805 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(计数排序)计数排序是一个广泛使用的排序方法。下面的程序使用双关键字 计数排序,将n对10000以内的整数,从小到大排序。

例如有三对整数(3, 4) (3, 4)、(2, 4) (2, 4)、(3, 3) (3, 3),那么排序之后应该是 (2, 4) (2, 4)、(3, 3) (3, 3)、(3, 4) (3, 4)。

输入第一行为nn接下来nn行,第ii行有两个数a[i]a[i]和b[i]b[i]分别表 示第ii对整数的第一关键字和第二关键字。

从小到大排序后输出。

数据范围

提示:应先对第二关键字排序,再对第一关键字排序。数组。ord[ ]存储第二关键 字排序的结果,数组res[ ]存储双关键字排序的结果。

试补全程序。

#include <cstdio>

#include <cstring> using namespace std; const int maxn = 10000000; const int maxs = 10000;


int n; unsigned a[maxn], b[maxn],res[maxn], ord[maxn]; unsigned

cnt[maxs + 1]; int main() {

    scanf("%d", &n);

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

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

    memset(cnt, 0, sizeof(cnt));

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

        ①; // 利用 cnt 数组统计数量

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

        cnt[i + 1] += cnt[i];

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

        ②; // 记录初步排序结果

    memset(cnt, 0, sizeof(cnt));

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

        ③; // 利用 cnt 数组统计数量

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

        cnt[i + 1] += cnt[i];

    for (int i = n - 1; i >= 0; --i)

        ④ // 记录最终排序结果

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

        printf("%d %d", ⑤);


    return 0; }


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
806 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

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

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


答案与解析
参考答案

去了

没去

没去

没下雨

题目详情
807 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

从1到2018这2018个数中, 共有        个包含数字8的数。

包含数字8的数是指有某一位是“8”的数,  例如“2018”与“188”。

答案与解析
参考答案

544

题目详情
808 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型
#include <cstdio>
char st[100];
int main() {
	scanf("%s", st);
	for (int i = 0; st[i]; ++i) {
		if ('A' <= st[i] && st[i] <= 'Z')
			st[i] += 1;
	}
	printf("%s\n", st);
	return 0;
}

输入: QuanGuoLianSai

输出:                                     

答案与解析
参考答案

RuanHuoMianTai

题目详情
809 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型
#include <cstdio>
int main() {
	int x;
	scanf("%d", &x);
	int res = 0;
	for (int i = 0; i < x; ++i) {
		if (i * i % x == 1) {
			++res;
		}
	}
	printf("%d", res);
	return 0;
}

输入: 15

输出:         

答案与解析
参考答案

4

题目详情
810 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型
#include <iostream>
using namespace std;
int n, m;
int findans(int n, int m) {
	if (n == 0) return m;
	if (m == 0) return n % 3;
	return findans(n - 1, m) - findans(n, m - 1) + findans(n - 1, m - 1);
}
int main(){
	cin >> n >> m;
	cout << findans(n, m) << endl;
	return 0;
}

输入: 5 6

输出:          

答案与解析
参考答案

8

题目详情
811 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型
#include <cstdio>
int n, d[100];
bool v[100];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", d + i);
		v[i] = false;
	}
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (!v[i]) {
			for (int j = i; !v[j]; j = d[j]) {
				v[j] = true;
			}
			++cnt;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

输入: 10 7 1 4 3 2 5 9 8 0 6

输出:          

答案与解析
参考答案

6

题目详情
812 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(最大公约数之和)下列程序想要求解整数n的所有约数两两之间最大公约 数的和对10007求余后的值,试补全程序。(第一空 2 分,其余 3 分)

举例来说,4的所有约数是1,2,4 。1和2的最大公约数为1;2和4的最大公约 数为2;1和4的最大公约数为1。于是答案为1+2+1=4。

要求 getDivisor 函数的复杂度为o(√n),gcd 函数的复杂度为为o(log max(a, b))。


#include <iostream>

using namespace std;

const int N = 110000, P = 10007;

int n;

int a[N], len;

int ans;

void getDivisor() {

len = 0;

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

if (n % i == 0) {

a[++len] = i;

if (     (2)      != i) a[++len] = n / i;

}

}

int gcd(int a, int b) {

if (b == 0) {

                       (3)           ;

}

return gcd(b,      (4)     );

}

int main() {

cin >> n;

getDivisor();

ans = 0;

for (int i = 1; i <= len; ++i) {

for (int j = i + 1; j <= len; ++j) {

ans = (      (5)     ) % P;

}

}

cout << ans << endl;

return 0;

}

答案与解析
参考答案

(1)i * i

(2)n / i

(3)return a

(4)a % b

(5)ans + gcd(a[i], a[j])

题目详情
813 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

对于一个1到n的排列p(即1到n中每一个数在p中出现了恰好一次),令qi为第i个位置之后第一个比pi值更大的位置,如果不存在这样的位置,则qi  = n + 1。

举例来说,如果n=5且p为1  5  4   2  3,则q为2  6  6  5  6。

下列程序读入了排列p,使用双向链表求解了答案。试补全程序。(第二空2分,其余3分)

数据范围 1≤n≤105。


#include <iostream>

using namespace std;

const int N = 100010;

int n;

int L[N], R[N], a[N];

int main() {

cin >> n;

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

int x;

cin >> x;

                 (1)      ;

}

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

R[i] =      (2)     ;

L[i] = i - 1;

}

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

L[       (3)     ] = L[a[i]];

R[L[a[i]]] = R[      (4)     ];

}

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

cout <<      (5)      << " ";

}

cout << endl;

return 0;

}

答案与解析
参考答案

(1)a[x] = i

(2)i + 1

(3)R[a[i]]

(4)a[i]

(5)R[i]

题目详情
814 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

一个人站在坐标(0,0)处,面朝x轴正方向。

第一轮, 他向前走1单位距离,然后右转;第二轮,他向前走2单位距离,然后右转;第三轮,他向前走3单位距离,然后右转……他一直这么走下去。请问第2017轮后,他的坐标是:(   ,   ) 。(请在答题纸上用逗号隔开两空答案)

答案与解析
参考答案

1009, 1008

题目详情
815 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

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

答案与解析
参考答案

3

题目详情
816 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型
#include <iostream>
using namespace std;

int main() {
	int t[256];
	string s;
	int i;
	cin >> s;
	for (i = 0; i < 256; i++)
		t[i] = 0;
	for (i = 0; i < s.length(); i++)
		t[s[i]]++;
	for (i = 0; i < s.length(); i++)
		if (t[s[i]] == 1) {
			cout << s[i] << endl;
			return 0;
		}
	cout << "no" << endl;
	return 0;
}


输入: xyzxyw

输出:            

答案与解析
参考答案

z

题目详情
817 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型
#include <iostream>
using namespace std;

int g(int m, int n, int x) {
	int ans = 0;
	int i;
	if (n == 1)
		return 1;
	for (i = x; i <= m / n; i++)
		ans += g(m - i, n - 1, i);
	return ans;
}

int main() {
	int t, m, n;
	cin >> m >> n;
	cout << g(m, n, 0) << endl;
	return 0;
}


输入: 7 3

输出:          

答案与解析
参考答案

8

题目详情
818 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型
#include <iostream>
using namespace std;

int main() {
	string ch;
	int a[200];
	int b[200];
	int n, i, t, res;
	cin >> ch;
	n = ch.length();
	for (i = 0; i < 200; i++)
		b[i] = 0;
	for (i = 1; i <= n; i++) {
		a[i] = ch[i - 1] - '0';
		b[i] = b[i - 1] + a[i];
	}
	res = b[n];
	t = 0;
	for (i = n; i > 0; i--) {
		if (a[i] == 0)
			t++;
		if (b[i - 1] + t < res)
			res = b[i - 1] + t;
	}
	cout << res << endl;
	return 0;
}


输入: 1001101011001101101011110001

输出:             

答案与解析
参考答案

11

题目详情
819 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型
#include <iostream>
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 << " " << y << endl;
	return 0;
}


输入 1:4 3

输出 1:                 (3 分)

输入 2:2017 1014

输出 2:                 (5 分)

答案与解析
参考答案

输出 1:1 3

输出 2:2017 1

题目详情
820 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

(快速幂)请完善下面的程序,该程序使用分治法求xp mod m的值。(第一空 2 分,其余 3 分)

输入:三个不超过10000的正整数x,p,m。

输出:xp mod m的值。

提示:若p为偶数,xp=(x2)p/2;若p为奇数,xp=x*(x2)(p-1)/2。


#include <iostream>

using namespace std;


int x, p, m, i, result;


int main() {

cin >> x >> p >> m;

result =    (1)   ;

while (   (2)  ) {

if (p % 2 == 1)

result =   (3)   ;

p /= 2;

x =   (4)   ;

}

cout <<   (5)   << endl;

return 0;

}

答案与解析
参考答案

(1)1

(2)p>0 或 p!=0 或 p

(3)result * x % m

(4)x * x % m

(5)result

题目详情