首页 › 题库 › 信息学奥赛 › 4.1 函数定义调用

信息学奥赛-入门级 题库

共 101 道题 ,第 5 / 6 页 · 按题型筛选,点「查看答案」核对解析
章节 4.1 函数定义调用 清除
81 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.1 函数定义调用

#include <cstdlib>

#include <iostream>

using namespace std;


char encoder[26] = {'C','S','P',0};

char decoder[26];


string st;


int main()  {

  int k = 0;

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

    if (encoder[i] != 0) ++k;

  for (char x ='A'; x <= 'Z'; ++x) {

    bool flag = true;

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

      if (encoder[i] ==x) {

        flag = false;

        break;

      }

      if (flag) {

        encoder[k]= x;

        ++k;

      }

  }

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

     decoder[encoder[i]- 'A'] = i + 'A';

  cin >> st;

  for (int i = 0; i < st.length( ); ++i)

    st[i] = decoder[st[i] -'A'];

  cout << st;

  return 0;

}

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

#include <iostream>

using namespace std;


long long n, ans;

int k, len;

long long d[1000000];


int main() {

  cin >> n >> k;

  d[0] = 0;

  len= 1;

  ans = 0;

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

    ++d[0];

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

      if (d[j] == k) {

        d[j] = 0;

        d[j + 1] += 1;

        ++ans;

      }

    }

    if (d[len- 1] == k) {

      d[len - 1] = 0;

      d[len] =1;

      ++len;

      ++ans;

    }

  }

  cout << ans << endl;

  return 0;

}

假设输入的n是不超过2^62的正整数,k都是不超过10000的正整数,完成下面的判断题和单选题:     

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

(质因数分解)给出正整数n,请输出将n质因数分解的結果,结果从小 到大输出。

例如:输入n=120,程序应该输出2 2 2 3 5,表示120=2 X2X2X 3X5。输入保证2≤n≤10^9。提示:先从小到大枚举变量i,然后用i不停试 除n来寻找所有的质因子。

试补全程序。

#include <cstdio>

using namespace std;

int n, i;

int main() {

  scanf("%d", &n);

  for(i = ①; ② <=n; i ++){

    ③{

      printf("%d ", i);

      n = n / i;

    }

  }

  if(④)

    printf("%d ", ⑤);

  return 0;

}

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

(最小区间覆盖)给出n个区间,第i个区间的左右端点是[ai, bi]。现在 要在这些区间中选出若干个,使得区间[0,m]被所选区间的并覆盖(即每 一个0≤i≤m都在某个所选的区间中)。保证答案存在,求所选区间个数 的最小值。

输入第一行包含两个整数n和m(1≤n≤5000, 1≤m≤10^9 )

接下来n行,每行两个整数ai,bi(0≤ai, bi ≤ m)。

提示:使用贪心法解决这个问题。先用0(n^2)的时间复杂度排序,然后贪心 选择这些区间。

试补全程序。

#include <iostream>

using namespace std;

const int MAXN = 5000;

int n, m;

struct segment { int a, b; } A[MAXN];

void sort() // 排序

{

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

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

            if (①)

            {

                segment t = A[j];

                ②

            }

}

int main()

{

    cin >> n >> m;

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

        cin >> A[i].a >> A[i].b;

    sort();

    int p = 1;

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

        if (③)

            A[p++] = A[i];

    n = p;

    int ans = 0, r = 0;

    int q = 0;

    while (r < m)

    {

        while (④)

            q++;

        ⑤;

        ans++;

    }

    cout << ans << endl;

    return 0;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
85 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.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

题目详情
86 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.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

题目详情
87 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.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

题目详情
88 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 4.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

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

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

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

要求 getDivisor 函数的复杂度为0函数的复杂度为0(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])

题目详情
90 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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 ≤ 10^5。

#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]

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

01 #include <iostream>

02 using namespace std;

03

04 int n;

05 int a[1000];

06

07 int f(int x)

08 {

09 int ret = 0;

10 for (; x; x &= x - 1) ret++;

11 return ret;

12 }

13

14 int g(int x)

15 {

16 return x & -x;

17 }

18

19 int main()

20 {

21 cin >> n;

22 for (int i = 0; i < n; i++) cin >> a[i];

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

24 cout << f(a[i]) + g(a[i]) << ' ';

25 cout << endl;

26 return 0;

27 }

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

01 #include <iostream>

02 #include <string>

03 using namespace std;

04 

05 char base[64];

06 char table[256];

07 

08 void init()

09 {

10 for (int i = 0; i < 26; i++) base[i] = 'A' + i;

11 for (int i = 0; i < 26; i++) base[26 + i] = 'a' + i;

12 for (int i = 0; i < 10; i++) base[52 + i] = '0' + i;

13 base[62] = '+', base[63] = '/';

14 

15 for (int i = 0; i < 256; i++) table[i] = 0xff;

16 for (int i = 0; i < 64; i++) table[base[i]] = i;

17 table['='] = 0;

18 }

19 

20 string decode(string str)

21 {

22 string ret;

23 int i;

24 for (i = 0; i < str.size(); i += 4) {

25 ret += table[str[i]] << 2 | table[str[i + 1]] >> 4;

26 if (str[i + 2] != '=')

27 ret += (table[str[i + 1]] & 0x0f) << 4 | table[str[i + 

2]] >> 2;

28 if (str[i + 3] != '=')

29 ret += table[str[i + 2]] << 6 | table[str[i + 3]];

30 }

31 return ret;

32 }

33 

34 int main()

35 {

36 init();

37 cout << int(table[0]) << endl;

38 

39 string str;

40 cin >> str;

41 cout << decode(str) << endl;

42 return 0;

43 }

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

const int n = 100000;
const int N = n + 1;

int m;
int a[N], b[N], c[N], d[N];
int f[N], g[N];

void init()
{
    f[1] = g[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!a[i]) {
            b[m++] = i;
            c[i] = 1, f[i] = 2;
            d[i] = 1, g[i] = i + 1;
        }
        for (int j = 0; j < m && b[j] * i <= n; j++) {
            int k = b[j];
            a[i * k] = 1;
            if (i % k == 0) {
                c[i * k] = c[i] + 1;
                f[i * k] = f[i] / c[i * k] * (c[i * k] + 1);
                d[i * k] = d[i];
                g[i * k] = g[i] * k + d[i];
                break;
            }
            else {
                c[i * k] = 1;
                f[i * k] = 2 * f[i];
                d[i * k] = g[i];
                g[i * k] = g[i] * (k + 1);
            }
        }
    }
}

int main()
{
    init();

    int x;
    cin >> x;
    cout << f[x] << ' ' << g[x] << endl;
    return 0;
}

假设输入的 x 是不超过 1000 的自然数,完成下面的判断题和单选题:

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

(Josephus 问题)有 n个人围成一个圈,依次标号 0 至n-1。从 0 号开始,依次 0, 1, 0, 1, … 交替报数,报到 1 的人会离开,直至圈中只剩下一个人。求最后剩下人的编号。

试补全模拟程序。

01 #include <iostream>

02 

03 using namespace std;

04 

05 const int MAXN = 1000000;

06 int F[MAXN];

07 

08 int main() {

09 int n;

10 cin >> n;

11 int i = 0, p = 0, c = 0;

12 while (①) {

13 if (F[i] == 0) {

14 if (②) {

15 F[i] = 1;

16 ③;

17 }

18 ④;

19 }

20 ⑤;

21 }

22 int ans = -1;

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

24 if (F[i] == 0)

25 ans = i;

26 cout << ans << endl;

27 return 0;

28 }

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

(矩形计数)平面上有 n 个关键点,求有多少个四条边都和 x 轴或者 y 轴平行的矩形,满足四个顶点都是关键点。给出的关键点可能有重复,但完全重合的矩形只计一次。

试补全枚举算法。

01 #include <iostream>

02 

03 using namespace std;

04 

05 struct point {

06 int x, y, id;

07 };

08 

09 bool equals(point a, point b) {

10 return a.x == b.x && a.y == b.y;

11 }

12 

13 bool cmp(point a, point b) {

14 return ①;

15 }

16 

17 void sort(point A[], int n) {

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

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

20 if (cmp(A[j], A[j - 1])) {

21 point t = A[j];

22 A[j] = A[j - 1];

23 A[j - 1] = t;

24 }

25 }

26

28 int t = 0;

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

30 if (②)

31 A[t++] = A[i];

32 return t;

33 }

34 

35 bool binary_search(point A[], int n, int x, int y) {

36 point p;

37 p.x = x;

38 p.y = y;

39 p.id = n;

40 int a = 0, b = n - 1;

41 while (a < b) {

42 int mid = ③;

43 if (④)

44 a = mid + 1;

45 else

46 b = mid;

47 }

48 return equals(A[a], p);

49 }

50 

51 const int MAXN = 1000;

52 point A[MAXN];

53 

54 int main() {

55 int n;

56 cin >> n;

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

58 cin >> A[i].x >> A[i].y;

59 A[i].id = i;

60 }

61 sort(A, n);

62 n = unique(A, n);

63 int ans = 0;

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

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

66 if (⑤ && binary_search(A, n, A[i].x, A[j].y) && 

binary_search(A, n, A[j].x, A[i].y)) {

67 ans++;

68 }

69 cout << ans << endl;

70 return 0;

71 }

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
96 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
97 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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]的范围内的整数,完成下 面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
98 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
99 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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;

}

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
100 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 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; }


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情