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

信息学奥赛-入门级 题库

共 1088 道题 ,第 45 / 55 页 · 按题型筛选,点「查看答案」核对解析
881 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.2 运算符

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

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

答案与解析
参考答案

答:544

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

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

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

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

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

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

题目详情
888 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 2.1 数据类型

标题统计

【问题描述】

凯凯刚写了一篇美妙的作文,请问这篇作文的标题中有多少个字符?

注意:标题中可能包含大、小写英文字母、数字字符、空格和换行符。统计标题字

符数时,空格和换行符不计算在内。

【输入格式】

输入文件名为 title.in。

输入文件只有一行,一个字符串 s。

【输出格式】

输出文件名为 title.out。

输出文件只有一行,包含一个整数,即作文标题的字符数(不含空格和换行符)。

【输入输出样例 1】

【输入输出样例 1 说明】

标题中共有 3 个字符,这 3 个字符都是数字字符。

【输入输出样例 2】

【输入输出样例 2 说明】

标题中共有 5 个字符,包括 1 个大写英文字母,1 个小写英文字母和 2 个数字字符,

还有 1 个空格。由于空格不计入结果中,故标题的有效字符数为 4 个。

【数据规模与约定】

规定 |s| 表示字符串 s 的长度(即字符串中的字符和空格数)。

对于 40% 的数据,1 ≤ |s| ≤ 5,保证输入为数字字符及行末换行符。

对于 80% 的数据,1 ≤ |s| ≤ 5,输入只可能包含大、小写英文字母、数字字符及

行末换行符。

对于 100% 的数据,1 ≤ |s| ≤ 5,输入可能包含大、小写英文字母、数字字符、空

格和行末换行符。

答案与解析
参考答案

import java.util.Scanner;

public class P5015 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();

        int count = 0;

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

            if (s.charAt(i)==' '){

                count++;

            }

        }

        System.out.print(s.length()-count);

    }

}

题目详情
889 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.1 数论入门

龙虎斗

【问题描述】

轩轩和凯凯正在玩一款叫《龙虎斗》的游戏,游戏的棋盘是一条线段,线段上有 n个兵营(自左至右编号 1 ~ n),相邻编号的兵营之间相隔 1 厘米,即棋盘为长度为n − 1 厘米的线段。i 号兵营里有 ci 位工兵。

下面图 1 为 n = 6 的示例:

轩轩在左侧,代表“龙”;凯凯在右侧,代表“虎”。 他们以 m 号兵营作为分界,靠左的工兵属于龙势力,靠右的工兵属于虎势力,而第 m 号兵营中的工兵很纠结,他们不属于任何一方。

一个兵营的气势为:该兵营中的工兵数 × 该兵营到 m 号兵营的距离;参与游戏一方的势力定义为:属于这一方所有兵营的气势之和。

下面图 2 为 n = 6, m = 4 的示例,其中红色为龙方,黄色为虎方:

游戏过程中,某一刻天降神兵,共有 s1 位工兵突然出现在了 p1 号兵营。作为轩轩和凯凯的朋友,你知道如果龙虎双方气势差距太悬殊,轩轩和凯凯就不愿意继续玩下去了。为了让游戏继续,你需要选择一个兵营 p2,并将你手里的 s2 位工兵全部派往兵营 p2,使得双方气势差距尽可能小。

注意:你手中的工兵落在哪个兵营,就和该兵营中其他工兵有相同的势力归属(如果落在 m 号兵营,则不属于任何势力)。

【输入格式】

输入文件名为 fight.in。

输入文件的第一行包含一个正整数 n,代表兵营的数量。

接下来的一行包含 n 个正整数,相邻两数之间以一个空格分隔,第 i 个正整数代表编号为 i 的兵营中起始时的工兵数量 ci。

接下来的一行包含四个正整数,相邻两数间以一个空格分隔,分别代表 m, p1, s1, s2。

【输出格式】

输出文件名为 fight.out。

输出文件有一行,包含一个正整数,即 p2,表示你选择的兵营编号。如果存在多个编号同时满足最优,取最小的编号。

【输入输出样例 1】

【输入输出样例 1 说明】

见问题描述中的图 2。

双方以 m = 4 号兵营分界,有 s1 = 5 位工兵突然出现在 p1 = 6 号兵营。

龙方的气势为:

2 × (4 − 1) + 3 × (4 − 2) + 2 × (4 − 3) = 14

虎方的气势为:

2 × (5 − 4) + (3 + 5) × (6 − 4) = 18

当你将手中的 s

2 = 2 位工兵派往 p2 = 2 号兵营时,龙方的气势变为:

14 + 2 × (4 − 2) = 18

此时双方气势相等。

【输入输出样例 2】

【输入输出样例 2 说明】

双方以 m = 5 号兵营分界,有 s1 = 1 位工兵突然出现在 p1 = 4 号兵营。

龙方的气势为:

1 × (5 − 1) + 1 × (5 − 2) + 1 × (5 − 3) + (1 + 1) × (5 − 4) = 11

虎方的气势为:

16 × (6 − 5) = 16

当你将手中的 s2 = 1 位工兵派往 p2 = 1 号兵营时,龙方的气势变为:

11 + 1 × (5 − 1) = 15

此时可以使双方气势的差距最小。

【数据规模与约定】

1 < m < n, 1 ≤ p1 ≤ n。

对于 20% 的数据,n = 3, m = 2, ci = 1, s1, s2 ≤ 100。

另有 20% 的数据,n ≤ 10, p1 = m, ci = 1, s1, s2 ≤ 100。

对于 60% 的数据,n ≤ 100, ci = 1, s1, s2 ≤ 100。

对于 80% 的数据,n ≤ 100, ci, s1, s2 ≤ 100。

对于 100% 的数据,n ≤ 105, ci, s1, s2 ≤ 10^9。

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;


int n, m, p1, p2;

long long a[maxn], s1, s2, sum;


int main() {

    cin >> n;

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

    cin >> m >> p1 >> s1 >> s2;

    a[p1] += s1;

    p2 = 1;

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

        sum += ( (long long) (i - m) ) * a[i];

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

        if ( abs(sum + (i-m) * s2) < abs(sum + (p2-m) * s2) ) p2 = i;

    cout << p2 << endl;

    return 0;

}

题目详情
890 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.1 数论入门

 摆渡车

【问题描述】

有 n 名同学要乘坐摆渡车从人大附中前往人民大学,第 i 位同学在第 ti 分钟去等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费 m 分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。

凯凯很好奇,如果他能任意安排摆渡车出发的时间,那么这些同学的等车时间之和最小为多少呢?

注意:摆渡车回到人大附中后可以即刻出发。

【输入格式】

输入文件名为 bus.in。

第一行包含两个正整数 n,m,以一个空格分开,分别代表等车人数和摆渡车往返一趟的时间。

第二行包含 n 个正整数,相邻两数之间以一个空格分隔,第 i 个非负整数 ti 代表第 i 个同学到达车站的时刻。

【输出格式】

输出文件名为 bus.out。

输出一行,一个整数,表示所有同学等车时间之和的最小值(单位:分钟)。

【输入输出样例 1】

【输入输出样例 1 说明】

同学 1 和同学 4 在第 3 分钟开始等车,等待 0 分钟,在第 3 分钟乘坐摆渡车出发。摆渡车在第 4 分钟回到人大附中。

同学 2 和同学 3 在第 4 分钟开始等车,等待 0 分钟,在第 4 分钟乘坐摆渡车出发。摆渡车在第 5 分钟回到人大附中。

同学 5 在第 5 分钟开始等车,等待 0 分钟,在第 5 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。总等待时间为 0。

【输入输出样例 2】

【输入输出样例 2 说明】

同学 3 在第 1 分钟开始等车,等待 0 分钟,在第 1 分钟乘坐摆渡车出发。摆渡车在第 6 分钟回到人大附中。

同学 4 和同学 5 在第 5 分钟开始等车,等待 1 分钟,在第 6 分钟乘坐摆渡车出发。摆渡车在第 11 分钟回到人大附中。

同学 1 在第 11 分钟开始等车,等待 2 分钟;同学 2 在第 13 分钟开始等车,等待 0 分钟。他/她们在第 13 分钟乘坐摆渡车出发。自此所有同学都被送到人民大学。

总等待时间为 4。可以证明,没有总等待时间小于 4 的方案。

【数据规模与约定】

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

const int maxn = 4000400;


int n, m, t, maxt;

long long f[maxn], cnt[maxn];


int main() {

    cin >> n >> m;

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

        cin >> t;

        cnt[t] ++;

        if (t > maxt) maxt = t;

    }

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

        long long tmp = 0;

        for (int j = 0; j < m && i-j >=0; j ++) {

            tmp += cnt[i-j] * ( (long long) j );

        }

        f[i] = tmp;

        if (i >= m) f[i] += f[i-m];

        for (int j = m+1; j <= 2*m && i - j >= 0; j ++) {

            tmp += cnt[i-j+1] * ( (long long) (j-1) );

            if (f[i-j] + tmp <= f[i]) f[i] = f[i-j] + tmp;

        }

    }

    long long ans = f[maxt];

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

        ans = min(ans, f[maxt+i]);

    }

    cout << ans << endl;

    return 0;

}

题目详情
891 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.1 数论入门

对称二叉树

【问题描述】

一棵有点权的有根树如果满足以下条件,则被轩轩称为对称二叉树:

1. 二叉树;

2. 将这棵树所有节点的左右子树交换,新树和原树对应位置的结构相同且点权相等。

下图中节点内的数字为权值,节点外的 id表示节点编号。

现在给出一棵二叉树,希望你找出它的一棵子树,该子树为对称二叉树,且节点数最多。请输出这棵子树的节点数。

注意:只有树根的树也是对称二叉树。本题中约定,以节点 T 为子树根的一棵“子树”指的是:节点 T 和它的全部后代节点构成的二叉树。

【输入格式】

输入文件名为 tree.in。

第一行一个正整数 n,表示给定的树的节点的数目,规定节点编号 1~n,其中节点1 是树根。

第二行 n 个正整数,用一个空格分隔,第 i 个正整数 vi 代表节点 i 的权值。接下来 n 行,每行两个正整数 li, ri,分别表示节点 i 的左右孩子的编号。如果不存在左 / 右孩子,则以 −1 表示。两个数之间用一个空格隔开。

【输出格式】

输出文件名为 tree.out。

输出文件共一行,包含一个整数,表示给定的树的最大对称二叉子树的节点数。

【输入输出样例 1】

【输入输出样例 1 说明】

最大的对称二叉子树为以节点 2 为树根的子树,节点数为 1。

【输入输出样例 2】

【输入输出样例 2 说明】

最大的对称二叉子树为以节点 7 为树根的子树,节点数为 3。

【数据规模与约定】

共 25 个测试点。

vi ≤ 1000。

测试点 1~3,n ≤ 10,保证根结点的左子树的所有节点都没有右孩子,根结点的右子树的所有节点都没有左孩子。

测试点 4~8,n ≤ 10。

测试点 9~12,n ≤ 10^5,保证输入是一棵“满二叉树”。

测试点 13~16,n ≤ 10^5,保证输入是一棵“完全二叉树”。

测试点 17~20,n ≤ 10^5,保证输入的树的点权均为 1。

测试点 21~25,n ≤ 10^6。

本题约定:

层次:节点的层次从根开始定义起,根为第一层,根的孩子为第二层。树中任一节点的层次等于其父亲节点的层次加 1。

树的深度:树中节点的最大层次称为树的深度。

满二叉树:设二叉树的深度为 h,且二叉树有 2^h − 1 个节点,这就是满二叉树。

完全二叉树:设二叉树的深度为 h,除第 h 层外,其它各层的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

答案与解析
参考答案

#include <iostream>

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;


int n;

struct node

{


    int v;

    int l,r;

}tree[maxn];

int sum[maxn]={0};

int count1=0;

int check(int l,int r)//判断二叉树是否对称

{

    if(l==r) return 1;

    if(tree[l].v==tree[r].v)

    {


        if(check(tree[l].l,tree[r].r)&&check(tree[l].r,tree[r].l))

           return 1;

    }

    return 0;


}

void  yu(int i)//统计结点数量

{

    int l=tree[i].l;

    int r=tree[i].r;

    if(i==-1) return ;

    sum[i]=1;

    yu(l);yu(r);

    sum[i]+=sum[l]+sum[r];



}

int main()

{

    cin>>n;

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

    {


        cin>>tree[i].v;

    }

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

    {

        cin>>tree[i].l>>tree[i].r;

    }

    yu(1);

    int ans=0;

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

    {


        if(check(tree[i].l,tree[i].r)) ans=max(ans,sum[i]);

    }

    cout<<ans<<endl;

    return 0;


}

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

成绩

【问题描述】

牛牛最近学习了 C++入门课程,这门课程的总成绩计算方法是:

总成绩 = 作业成绩 × 20% + 小测成绩 × 30% + 期末考试成绩 × 50%

牛牛想知道,这门课程自己最终能得到多少分。

【输入格式】

输入文件名为 score.in。

输入文件只有 1 行,包含三个非负整数A、B、C,分别表示牛牛的作业成绩、小测

成绩和期末考试成绩。相邻两个数之间用一个空格隔开,三项成绩满分都是 100 分。

【输出格式】

输出文件名为 score.out。

输出文件只有 1 行,包含一个整数,即牛牛这门课程的总成绩,满分也是 100 分。

【输入输出样例 1】

【输入输出样例 1 说明】

牛牛的作业成绩是 100 分,小测成绩是 100 分,期末考试成绩是 80 分,总成

绩是 100 × 20% + 100 × 30% + 80 × 50% = 20 + 30 + 40 = 90。

【输入输出样例 2】

【输入输出样例 2 说明】

牛牛的作业成绩是 60 分,小测成绩是 90 分,期末考试成绩是 80 分,总成绩是

60 × 20% + 90 × 30% + 80 × 50% = 12 + 27 + 40 = 79。

【数据说明】

对于 30% 的数据,A = B = 0。

对于另外 30% 的数据,A = B = 100。

对于 100% 的数据, 0 ≤ A、B、C ≤ 100 且 A、B、C 都是 10 的整数倍。

答案与解析
参考答案

#include<iostream>

 

using namespace std;

 

int main()

{

int A, B, C;

cin >> A >> B >> C; 

cout << A * 0.2 + B * 0.3 + C * 0.5;

return 0;

}

题目详情
893 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.1 数论入门

 图书管理员

【问题描述】

图书馆中每本书都有一个图书编码,可以用于快速检索图书,这个图书编码是一个

正整数。

每位借书的读者手中有一个需求码,这个需求码也是一个正整数。如果一本书的图

书编码恰好以读者的需求码结尾,那么这本书就是这位读者所需要的。

小 D 刚刚当上图书馆的管理员,她知道图书馆里所有书的图书编码,她请你帮她写

一个程序,对于每一位读者,求出他所需要的书中图书编码最小的那本书,如果没有他

需要的书,请输出-1。

【输入格式】

输入文件名为 librarian.in。

输入文件的第一行,包含两个正整数 n 和 q,以一个空格分开,分别代表图书馆里

书的数量和读者的数量。

接下来的 n 行,每行包含一个正整数,代表图书馆里某本书的图书编码。

接下来的 q 行,每行包含两个正整数,以一个空格分开,第一个正整数代表图书馆

里读者的需求码的长度,第二个正整数代表读者的需求码。

【输出格式】

输出文件名为 librarian.out。

输出文件有 q 行,每行包含一个整数,如果存在第 i 个读者所需要的书,则在第 i

行输出第 i 个读者所需要的书中图书编码最小的那本书的图书编码,否则输出-1。

【输入输出样例 1】

【输入输出样例 1 说明】

第一位读者需要的书有 2123、1123、23,其中 23 是最小的图书编码。第二位读者需要

的书有 2123、1123,其中 1123 是最小的图书编码。对于第三位,第四位和第五位读者,没

有书的图书编码以他们的需求码结尾,即没有他们需要的书,输出-1。

【数据规模与约定】

对于 20%的数据,1 ≤ n ≤ 2。

另有 20%的数据,q = 1。

另有 20%的数据,所有读者的需求码的长度均为 1。

另有 20%的数据,所有的图书编码按从小到大的顺序给出。

对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ q ≤ 1,000,所有的图书编码和需求码均

不超过 10,000,000。

答案与解析
参考答案

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

#define M 1000

int n,q;

int a[M+5],ans;

int main()

{

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

    for(int i=1;i<=n;i++)scanf("%d",&a[i]);

    sort(a+1,a+n+1);//从小到大排序

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

    {

        int x,y;

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

        int f=0;

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

        {

            if(a[j]%int(pow(10,x))==y)//取末尾编码

            {

                f=1;

                printf("%d\n",a[j]);

                break;

            }

        }

        if(f==0)printf("-1\n");

    }

    return 0;

}

题目详情
894 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.1 数论入门

棋盘

【问题描述】

有一个m × m的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在

要从棋盘的最左上角走到棋盘的最右下角。

任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的),你只能向上、下、

左、右四个方向前进。当你从一个格子走向另一个格子时,如果两个格子的颜色相同,那你

不需要花费金币;如果不同,则你需要花费 1 个金币。

另外,你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个

魔法不能连续使用,而且这个魔法的持续时间很短,也就是说,如果你使用了这个魔法,走

到了这个暂时有颜色的格子上,你就不能继续使用魔法;只有当你离开这个位置,走到一个

本来就有颜色的格子上的时候,你才能继续使用这个魔法,而当你离开了这个位置(施展魔

法使得变为有颜色的格子)时,这个格子恢复为无色。

现在你要从棋盘的最左上角,走到棋盘的最右下角,求花费的最少金币是多少?

【输入格式】

输入文件名为 chess.in。

数据的第一行包含两个正整数 m,n,以一个空格分开,分别代表棋盘的大小,棋盘上

有颜色的格子的数量。

接下来的 n 行,每行三个正整数 x,y,c,分别表示坐标为(x,y)的格子有颜色 c。

其中 c=1 代表黄色,c=0 代表红色。相邻两个数之间用一个空格隔开。棋盘左上角的坐标

为(1, 1),右下角的坐标为(m, m)。

棋盘上其余的格子都是无色。保证棋盘的左上角,也就是(1,1)一定是有颜色的。

【输出格式】

输出文件名为 chess.out。

输出一行,一个整数,表示花费的金币的最小值,如果无法到达,输出-1。

【输入输出样例 1】

【输入输出样例 1 说明】

从(1,1)开始,走到(1,2)不花费金币

从(1,2)向下走到(2,2)花费 1 枚金币

从(2,2)施展魔法,将(2,3)变为黄色,花费 2 枚金币

从(2,2)走到(2,3)不花费金币

从(2,3)走到(3,3)不花费金币

从(3,3)走到(3,4)花费 1 枚金币

从(3,4)走到(4,4)花费 1 枚金币

从(4,4)施展魔法,将(4,5)变为黄色,花费 2 枚金币,

从(4,4)走到(4,5)不花费金币

从(4,5)走到(5,5)花费 1 枚金币

共花费 8 枚金币。

【输入输出样例 2】

【输入输出样例 2 说明】

从(1,1)走到(1,2),不花费金币

从(1,2)走到(2,2),花费 1 金币

施展魔法将(2,3)变为黄色,并从(2,2)走到(2,3)花费 2 金币

从(2,3)走到(3,3)不花费金币

从(3,3)只能施展魔法到达(3,2),(2,3),(3,4),(4,3)

而从以上四点均无法到达(5,5),故无法到达终点,输出-1

【数据规模与约定】

对于 30%的数据,1 ≤ m ≤ 5, 1 ≤ n ≤ 10。

对于 60%的数据,1 ≤ m ≤ 20, 1 ≤ n ≤ 200。

对于 100%的数据,1 ≤ m ≤ 100, 1 ≤ n ≤ 1,000。

答案与解析
参考答案

#include <iostream>

#include <bits/stdc++.h>

#include<set>

#include<string.h>

#include<algorithm>


using namespace std;

// 1 黄 0 红

int dis[4][2]={{-1,0},{1,0},{0,1},{0,-1}};

int n,m;

const int maxn=105;

struct node

{

    int x,y,c,v;

};

queue<node>q;

int yy[maxn][maxn],val[maxn][maxn];

int ans=0x7f7f7f7f;


void Init()

{


    memset(yy,-1,sizeof(yy));

    memset(val,0x7f,sizeof(val));

}

void dfs(int x,int y)

{


    node pq;

    pq.x=x,pq.y=y,pq.c=yy[x][y],pq.v=0;

    val[x][y]=0;

    q.push(pq);

    while(!q.empty())

    {

        node now=q.front();

        if(now.v>ans)

        {

            q.pop();

            continue;

        }

        if(now.x==m&&now.y==m)

        {

            ans=min(ans,now.v);

            q.pop();

            continue;

        }

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

        {

            int dx=now.x+dis[i][0],dy=now.y+dis[i][1];

            if(dx>0&&dy>0&&dx<=m&&dy<=m)

            {

                int bc=yy[now.x][now.y],dc=yy[dx][dy],mv=val[dx][dy],dv;

                if(bc>=0&&dc>=0)

                {

                    dv=now.v+(bc==dc?0:1);

                    if(mv>dv)

                    {

                        q.push((node){dx,dy,dc,dv});

                        val[dx][dy]=dv;

                    }

                }

                else if(dc<0&&bc>=0)

                {

                    dv=now.v+2;

                    if(mv>dv)

                    {

                        q.push((node){dx,dy,bc,dv});

                        val[dx][dy]=dv;

                    }

                }

                else if(bc<0&&dc>=0)

                {

                    dv=now.v+(now.c==dc? 0:1);

                     if(mv>dv)

                    {

                        q.push((node){dx,dy,dc,dv});

                        val[dx][dy]=dv;

                    }

                }

            }

        }

        q.pop();

    }

}


int main()

{


    cin>>m>>n;

    Init();

    int x,y,c;

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

    {

        cin>>x>>y>>c;

        yy[x][y]=c;


    }

    dfs(1,1);

    if(ans==0x7f7f7f7f)

        cout<<-1<<endl;

    else

        cout<<ans<<endl;

    return 0;


}

题目详情
895 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.1 数论入门

跳房子

【问题描述】

跳房子,也叫跳飞机,是一种世界性的儿童游戏,也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下:

在地面上确定一个起点,然后在起点右侧画 n 个格子,这些格子都在同一条直线上。每个格子内有一个数字(整数),表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳,跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳,依此类推。规则规定:

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏,获得的分数为曾经到达过的格子中的数字之和。

现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷,它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人,如果他花 g 个金币改进他的机器人,那么他的机器人灵活性就能增加 g,但是需要注意的是,每次弹跳的距离至少为 1。具体而言,当g < d时,他的机器人每次可以选择向右弹跳的距离为 d-g, d-g+1, d-g+2,…,d+g-2,d+g-1,d+g;否则(当g ≥ d时),他的机器人每次可以选择向右弹跳的距离为 1,2,3,…,d+g-2,d+g-1,d+g。

现在小 R 希望获得至少 k 分,请问他至少要花多少金币来改造他的机器人。

【输入格式】

输入文件名为 jump.in。

第一行三个正整数 n,d,k,分别表示格子的数目,改进前机器人弹跳的固定距离,以及希望至少获得的分数。相邻两个数之间用一个空格隔开。

接下来 n 行,每行两个正整数xi, si,分别表示起点到第i个格子的距离以及第i个格子的分数。两个数之间用一个空格隔开。保证xi按递增顺序输入。

【输出格式】

输出文件名为 jump.out。

共一行,一个整数,表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k 分,输出-1。

【输入输出样例 1】

【输入输出样例 1 说明】

花费 2 个金币改进后,小 R 的机器人依次选择的向右弹跳的距离分别为 2,3,5,3,4,3,先后到达的位置分别为 2,5,10,13,17,20,对应 1, 2, 3, 5, 6, 7 这 6 个格子。这些格子中的数字之和 15 即为小 R 获得的分数。

【输入输出样例 2】

【输入输出样例 2 说明】

 由于样例中 7 个格子组合的最大可能数字之和只有 18 ,无论如何都无法获得 20 分。

【数据规模与约定】

本题共 10 组测试数据,每组数据 10 分。对于全部的数据满足1 ≤ n ≤ 500000, 1 ≤ d ≤2000, 1 ≤ xi, k ≤ 10^9, |si| < 10^5。

对于第 1,2 组测试数据,n ≤ 10;

对于第 3,4,5 组测试数据,n ≤ 500

对于第 6,7,8 组测试数据,d = 1

答案与解析
参考答案

#include<bits/stdc++.h>


using namespace std;

#define INF 1e18

typedef long long ll;

struct node{

ll pos=0,value=0;

}a[500005];

ll n,d,k;

ll dp[500005];

bool check(ll minn,ll maxx){

for(int i=1;i<=n;i++) dp[i]=-INF;

dp[0]=0LL;

deque<int> q;

int now=0;

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

while(a[i].pos-a[now].pos>maxx&&now<i) now++;

while(a[i].pos-a[now].pos<=maxx&&a[i].pos-a[now].pos>=minn&&now<i){

while(!q.empty()&&(dp[q.back()]<=dp[now]||a[i].pos-a[q.back()].pos>maxx)) q.pop_back();

q.push_back(now);

now++;

}

while(!q.empty()&&a[i].pos-a[q.front()].pos>maxx) q.pop_front();

if(!q.empty()) dp[i]=dp[q.front()]+a[i].value;

if(dp[i]>=k) return true;

}

return false;

}

int main()

{

cin>>n>>d>>k;

for(ll i=1;i<=n;i++) cin>>a[i].pos>>a[i].value;

ll l=1,r=a[n].pos;

while(l<r){

ll mid=(l+r)>>1;

if(check(max((long long)1,d-mid),d+mid)) r=mid;

else l=mid+1; 

}

cout<<(r==INF?-1:r);

return 0;

 } 

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

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

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

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

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

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