首页 › 题库 › 信息学奥赛 › 10 数学基础

信息学奥赛-入门级 题库

共 59 道题 ,第 2 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 10 数学基础 清除
21 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

T1拼数

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
//循环字符串,将所有数字插入vector
//将vector排序
//倒序输出
string s;
vector<char> v;
int main() {
    cin >> s;
    for (char i : s) {
        if (i >= '0' && i <= '9') {
            v.push_back(i);
        }
    }
    sort(v.begin(), v.end(), greater<int>());
    for (char i : v) {
        cout << i;
    }
    return 0;
}
题目详情
22 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

T2座位


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, a, a1, k = 1;
    cin >> n >> m >> a1;
    for (int i = 1; i < n*m; i++) {
        cin >> a;
        if (a > a1) k++;
    }
    int lie = ceil(1.0 * k / n);
    int g = k % n;
    if (g == 0) g = n;  //特殊情况
    int hang;
    if (lie % 2 == 0) {  //偶数列:从下往上排
        hang = n - g + 1;
    } else {  //奇数列:从上往下排
        hang = g;
    }
    cout << lie << " " << hang;
    return 0;
}
题目详情
23 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

T3异或和


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5 + 5;
int n, k, a;
int dp[MAXN];
//存储每种异或和最后一次出现的下标
map<int, int> m;
int main() {
    cin >> n >> k;
    int qzh = 0;
    m[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a;
        qzh ^= a;
        dp[i] = dp[i-1];
        if (m.find(k ^ qzh) != m.end()) dp[i] = max(dp[i], dp[m[k ^ qzh]] + 1);
        m[qzh] = i;
    }
    cout << dp[n];
    return 0;
}
题目详情
24 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

T4多边形


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int MAXN = 5005;
int a[MAXN];
int cnt[MAXN][MAXN];
int dp[MAXN];
int n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    cnt[1][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 5001; j++) {
            cnt[i+1][j] = (cnt[i+1][j] + cnt[i][j]) % mod;
            cnt[i+1][min(j+a[i],5001)] = (cnt[i+1][min(j+a[i],5001)] + cnt[i][j]) % mod;
        }
    }
    //求dp
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i-1];
        for (int j = a[i]+1; j <= 5001; j++) dp[i] = (dp[i] + cnt[i][j]) % mod;
    }
    cout << dp[n];
    return 0;
}
题目详情
25 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

重新排列1234使得每一个数字都不在原来的位置上,一共有              种排法。

答案与解析
参考答案

9

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

}

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

}

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


}

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

}

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


}

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

 } 

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

公交换乘

【问题描述】

著名旅游城市B市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交 车的优惠方案:

1.在搭乘一次地铁后可以获得一张优惠票,有效期为45分钟,在有效期内可以 消耗这张优惠票,免费搭乘一次票价不超过地铁票价的公交车。在有效期内指 开始乘公交车的时间与开始乘地铁的时间之差小于等于45分钟,即:tbus-tsubway≤45

2.  搭乘地铁获得的优惠票可以累积,即可以连续搭乘若干次地铁后再连续使用优 惠票搭乘公交车。

3.  搭乘公交车时,如果可以使用优惠票一定会使用优惠票;如果有多张优惠票满 足条件,则优先消耗获得最早的优惠票。

现在你得到了小轩最近的公共交通出行记录,你能帮他算算他的花费吗?

【输入格式】

输入文件名为transfer . in。

输入文件的第一行包含一个正整数n,代表乘车记录的数量。

接下来的n行,每行包含3个整数,相邻两数之间以一个空格分隔。第i行的 第1个整数代表第i条记录乘坐的交通工具,0代表地铁,1代表公交车;第2个 整数代表第i条记录乘车的票价pricei;第三个整数代表第i条记录开始乘车的时 间ti (距0时刻的分钟数)。

我们保证出行记录是按照开始乘车的时间顺序给出的,且不会有两次乘车记录出现 在同一分钟。

【输出格式】

输出文件名为transfer . out。

输出文件有一行,包含一个正整数,代表小轩出行的总花费

【 输入输出样例 1】

【输入输出样例1说明】

第一条记录,在第3分钟花费10元乘坐地铁。

第二条记录,在第46分钟乘坐公交车,可以使用第一条记录中乘坐地铁获得的优 惠票,因此没有花费。

第三条记录,在第50分种花费12元乘坐地铁。

第四条记录,在第96分钟乘坐公交车,由于距离第三条记录中乘坐地铁已超过45 分钟,所以优惠票已失效,花费3元乘坐公交车。

第五条记录,在第110分钟花费5元乘坐地铁。

第六条记录,在第135分钟乘坐公交车,由于此时手中只有第五条记录中乘坐地铁 获得的优惠票有效,而本次公交车的票价为6元,高于第五条记录中地铁的票价5元, 所以不能使用优惠票,花费6元乘坐公交车。

总共花费36元。

【输入输出样例2】

【输入输出样例2说明】

第一条记录,在第1分钟花费5元乘坐地铁。

第二条记录,在第16分钟花费20元乘坐地铁。

第三条记录,在第23分钟花费7元乘坐地铁。

第四条记录,在第31分钟乘坐公交车,此时只有第二条记录中乘坐的地铁票价高 于本次公交车票价,所以使用第二条记录中乘坐地铁获得的优惠票。

第五条记录,在第38分钟乘坐公交车,此时第一条和第三条记录中乘坐地铁获得  的优惠票都可以使用,使用获得最早的优惠票,即第一条记录中乘坐地铁获得的优惠票。

第六条记录,在第68分钟乘坐公交车,使用第三条记录中乘坐地铁获得的优惠票。 总共花费32元。

【数据规模与约定】

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

int n,opt,m,t,num=0,ans=0;

struct data {

int m,t;

bool ok;

} p[100001];

int main() {

scanf("%d",&n);

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

scanf("%d%d%d",&opt,&m,&t);

if(opt==0) {

num++;

p[num].m=m;

p[num].t=t;

p[num].ok=0;

ans+=m;

}

if(opt==1) {

bool ok=0;

for(int j=1; j<=num; j++) {

if(t-p[j].t<=45&&p[j].ok==0&&m<=p[j].m) {

p[j].ok=1;

ok=1;

break;

}

}

if(ok==0)

ans+=m;

}

}

printf("%d\n",ans);


return 0;

}

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

纪念品

【问题描述】

小伟突然获得一种超能力,他知道未来T天N种纪念品每天的价格。某个纪念品  的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。

每天,小伟可以进行以下两种交易无限次:

1. 任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;

2. 卖出持有的任意一个纪念品,以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当 日卖出换回金币。当然, 一直持有纪念品也是可以的。

T天之后,小伟的超能力消失。因此他一定会在第T天卖出所有纪念品换回金币。 小伟现在有M枚金币,他想要在超能力消失后拥有尽可能多的金币。

【输入格式】

输入文件名为souvenir . in。

第一行包含三个正整数T,N,M,相邻两数之间以一个空格分开,分别代表未来天数 T,纪念品数量N,小伟现在拥有的金币数量M。

接下来T行,每行包含N个正整数,相邻两数之间以一个空格分隔。第i行的N个正整数分别为Pi1,Pi2, …… ,Pin,其中Pi,j表示第i天第j种纪念品的价格。

【输出格式】

输出文件名为souvenir . out。

输出仅一行,包含一个正整数,表示小伟在超能力消失后最多能拥有的金币数量。

【输入输出样例1】

【 输入输出样例1说明】

最佳策略是:

第二天花光所有100枚金币买入5个纪念品1;

第三天卖出5个纪念品1,获得金币125枚;

第四天买入6个纪念品1,剩余5枚金币;

第六天必须卖出所有纪念品换回300枚金币,第四天剩余5枚金币,共305枚金币。

超能力消失后,小伟最多拥有305枚金币。

【输入输出样例2】

【输入输出样例2说明】

最佳策略是:

第一天花光所有金币买入10个纪念品1;

第二天卖出全部纪念品1得到150枚金币并买入8个纪念品2和1个纪念品3,剩 余1枚金币;

第三天必须卖出所有纪念品换回216枚金币,第二天剩余1枚金币,共217枚金币。 超能力消失后,小伟最多拥有217枚金币。

【数据规模与约定】

对于10%的数据,T=1。

对于30%的数据,T≤4,N≤4,M≤100,所有价格10≤Pij≤100。 

另有15%的数据,T≤100,N=1。

另有15%的数据,T=2,N≤100。

对于100%的数据,T≤100,N≤100,M≤,所有价格1≤Pij≤10⁴,数 据保证任意时刻,小明手上的金币数不可能超过10⁴。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

const int N = 1e2+10;

const int M = 1e4+10;

int t,n,m;

int val[N][N];

int f[N]; //第 x 天最多有多少钱

int tmp[M],mx;

void solve(){

f[1] = m;

for(int day = 2;day <= t;day++){

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

memset(tmp,0,sizeof tmp); mx = m;

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

for(int v = val[i][j]; v <= f[i];v++){

tmp[v] = max(tmp[v-val[i][j]]+val[day][j],tmp[v]);

mx = max(mx,tmp[v]+f[i]-v);

}

}

f[day] = max(f[day],mx);

}

f[day] = max(f[day],f[day-1]);

}

//for(int i = 1;i <= t;i++) printf("%d\n",f[i]);

printf("%d\n",f[t]);

}

int main(){

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

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

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

solve();

return 0;

}

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

买铅笔 (pencil)

【问题描述】

P 老师需要去商店买 n 支铅笔作为小朋友们参加NOIP 的礼物。她发现商店一共有 3 种包装的铅笔,不同包装内的铅笔数量有可能不同,价格也有可能不同。为了公平起 见,P 老师决定只买同一种包装的铅笔。

商店不允许将铅笔的包装拆开,因此P老师可能需要购买超过 n 支铅笔才够给小朋 友们发礼物。

现在P 老师想知道,在商店每种包装的数量都足够的情况下,要买够至少n 支铅 笔最少需要花费多少钱。

【输入格式】

从文件pencil.in 中读入数据。

输入的第一行包含一个正整数n ,表示需要的铅笔数量。

接下来三行,每行用两个正整数描述一种包装的铅笔:其中第一个整数表示这种 包装内铅笔的数量,第二个整数表示这种包装的价格。

保证所有的 7 个数都是不超过 10000 的正整数。

【输出格式】

输出到文件pencil.out 中。

输出一行一个整数,表示P 老师最少需要花费的钱。

【样例1输入】

57

2  2

50  30

30  27

【样例1输出】

54

【样例1说明】

铅笔的三种包装分别是:

●  2 支装,价格为 2 ;

●  50 支装,价格为 30 ;

●  30 支装,价格为 27 。

P老师需要购买至少57 支铅笔。

如果她选择购买第一种包装,那么她需要购买 29 份,共计 2 × 29 = 58 支,需要花 费的钱为 2 × 29 = 58 。

实际上,P老师会选择购买第三种包装,这样需要买 2 份。 虽然最后买到的铅笔数 量更多了,为 30 × 2 = 60 支,但花费却减少为 27 × 2 = 54 ,比第一种少。

对于第二种包装,虽然每支铅笔的价格是最低的,但要够发必须买 2 份,实际的 花费达到了 30 × 2 = 60 ,因此P老师也不会选择。

所以最后输出的答案是 54 。

【样例2输入】

9998

128  233

128  2333

128  666


【样例2输出】

18407


【样例3输入】

9999

101  1111

1  9999

1111  9999


【样例3输出】

89991

【子任务】

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难,可以尝试 只解决一部分测试数据。

每个测试点的数据规模及特点如下表:

上表中“整倍数”的意义为:若为“√” ,表示对应数据所需要的铅笔数量 n 一定是每 种包装铅笔数量的整倍数 (这意味着一定可以不用多买铅笔)。

答案与解析
参考答案

#include <iostream>

#include <algorithm>

using namespace std;

int main(){

    int want, pcl[3], prc[3], sum = 1;            //pcl 为三种铅笔的个数,prc 为三种铅笔的价格

    cin >> want >> pcl[0] >> prc[0] >> pcl[1] >> prc[1] >> pcl[2] >> prc[2];

    for(int i = 0; i < 3; i++){                   //遍历三种铅笔

        while(pcl[i]*sum < want) sum++;           //循环求出 sum,即最小购买的包数

        prc[i] *= sum;                            //求出每种铅笔的最终花费

        sum = 1;                                  //sum 重置

    }

    sort(prc,prc+3);                              //将三个花费排序,得到最小花费

    cout << prc[0];

    return 0;

}

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

 金币

【问题描述】

国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天),每天收到两枚金币;之后三天(第四、五、六天),每天收到三枚金币;之后四天(第七、八、九、十天),每天收到四枚金币……;这种工资发放模式会一直这样延续下去:当连续 N 天每天收到 N 枚金币后,骑士会在之后的连续 N+1 天里,每天收到 N+1 枚金币。

请计算在前 K 天里,骑士一共获得了多少金币。

【输入格式】

输入文件名为 coin.in。

输入文件只有 1 行,包含一个正整数 K,表示发放金币的天数。

【输出格式】

输出文件名为 coin.out。

输出文件只有 1 行,包含一个正整数,即骑士收到的金币数。

【输入输出样例 1】

【输入输出样例 1 说明】

骑士第一天收到一枚金币;第二天和第三天,每天收到两枚金币;第四、五、六天,每天收到三枚金币。因此一共收到 1+2+2+3+3+3=14 枚金币。

【输入输出样例 2】

【数据说明】

对于 100%的数据,1 ≤ K ≤ 10,000。

答案与解析
参考答案

# include<stdio.h>

int main()

{

int m,n,k,s=0,count=1,flag=1;

scanf("%d",&k);

for(m=1;m<=k;count++,flag++){

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

s+=count;m++;

if(m>k) break;

}

}

printf("%d",s);

return 0;

 } 

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

珠心算测验

【问题描述】

珠心算是一种通过在脑中模拟算盘变化来完成快速运算的一种计算技术。珠心算训练,既能够开发智力,又能够为日常生活带来很多便利,因而在很多学校得到普及。

某学校的珠心算老师采用一种快速考察珠心算加法能力的测验方法。他随机生成一个正整数集合,集合中的数各不相同,然后要求学生回答:其中有多少个数,恰好等于集合中另外两个(不同的)数之和?

最近老师出了一些测验题,请你帮忙求出答案。

【输入】

输入文件名为 count.in。

输入共两行,第一行包含一个整数 n,表示测试题中给出的正整数个数。

第二行有 n 个正整数,每两个正整数之间用一个空格隔开,表示测试题中给出的正整数。

【输出】

输出文件名为 count.out。

输出共一行,包含一个整数,表示测验题答案。

【输入输出样例】

【样例说明】

由 1+2=3,1+3=4,故满足测试要求的答案为 2。注意,加数和被加数必须是集合中的两个不同的数。

【数据说明】

对于 100%的数据,3 ≤ n ≤ 100,测验题给出的正整数大小不超过 10,000。

答案与解析
参考答案

#include <bits/stdc++.h>

#define MAXN 1e6+2

#define inf 0x3f3f3f3f

#define rep(x, a, b) for(int x=a; x<=b; x++)

#define per(x, a, b) for(int x=a; x>=b; x--)

using namespace std;

const int NC = 1e5+2;

//queue<int> que;

int num[200];

int cot;

int n;

bool visit[200];

 

int main()

{

    cin>>n;

  rep(i, 1, n)

  {

    cin>>num[i];

  }

  sort(num+1, num+1+n);

  rep(i, 1, n)

  {

      rep(j, i+1, n)

      {

          if(num[i] != num[j])

          {

              rep(k, j+1, n)

              {

                  if(num[i]+num[j] == num[k] && !visit[k])

                  {

                      cot++;

                      visit[k] = true;

                  }

              }

          }

      }

  }

  cout<<cot;

    return 0;

}

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

比例简化

【问题描述】

在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示支持的有 1498 人,反对的有 902 人,那么赞同与反对的比例可以简单的记为1498:902。

不过,如果把调查结果就以这种方式呈现出来,大多数人肯定不会满意。因为这个比例的数值太大,难以一眼看出它们的关系。对于上面这个例子,如果把比例记为 5:3,虽然与真实结果有一定的误差,但依然能够较为准确地反映调查结果,同时也显得比较直观。

现给出支持人数 A,反对人数 B,以及一个上限 L,请你将 A 比 B 化简为 A’比 B’,要求在 A’和 B’均不大于 L 且 A’和 B’互质(两个整数的最大公约数是 1)的前ᨀ下,A’/B’ ≥ A/B且 A’/B’ - A/B 的值尽可能小。

【输入】

输入文件名为 ratio.in。

输入共一行,包含三个整数 A,B,L,每两个整数之间用一个空格隔开,分别表示支持人数、反对人数以及上限。

【输出】

输出文件名为 ratio.out。

输出共一行,包含两个整数 A’,B’,中间用一个空格隔开,表示化简后的比例。

【输入输出样例】

【数据说明】

对于 100%的数据,1 ≤ A ≤ 1,000,000,1 ≤ B ≤ 1,000,000,1 ≤ L ≤ 100,A/B ≤ L。

答案与解析
参考答案

#include <iostream>

#include <cstdio>

#include <string>

#include <queue>

#include <cstring>

#include <cmath>

#include <cctype>

#include <vector>

#include <algorithm>

#include <map>

#include <stack>


using namespace std;

typedef long long ll;

typedef pair<int,int> pa;

const int N=100005;

const int mod=99999997;

int x,y,l;

int a,b;

int gcd(int x,int y)

{

    if(x<y) return gcd(y,x);

    if(y==0) return x;

    return gcd(y,x%y);

}

int main()

{

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

    double t1,t2,t3;

    t1=x*1.0/y;

    t3=l*1.0;

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

    {

        for(int k=1;k<=l;k++)

        {

            t2=i*1.0/k;

            if(t2>=t1 &&gcd(i,k)==1 && t2-t1<t3)

            {

                a=i;

                b=k;

                t3=t2-t1;

            }

        }

    }

    printf("%d %d\n",a,b);

    return 0;

}

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

小朋友的数字

【问题描述】

有 n 个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。

作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。

请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 p 取模后

输出。

【输入】

输入文件为 number.in。

第一行包含两个正整数 n、p,之间用一个空格隔开。

第二行包含 n 个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。

【输出】

输出文件名为 number.out。

输出只有一行,包含一个整数,表示最大分数对 p 取模的结果。

【输入输出样例 1】

【输入输出样例说明】

小朋友的特征值分别为 1、3、6、10、15,分数分别为 1、2、5、11、21,最大值 21对 997 的模是 21。

【输入输出样例 2】

【输入输出样例说明】

小朋友的特征值分别为-1、-1、-1、-1、-1,分数分别为-1、-2、-2、-2、-2,最大值

-1 对 7 的模为-1,输出-1。

【数据范围】

对于 50%的数据,1 ≤ n ≤ 1,000,1 ≤ p ≤ 1,000所有数字的绝对值不超过 1000;

对于 100%的数据,其他数字的绝对值均不超过


答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

#define int __int128

int read(){

int x=0,f=1;

char c=getchar();

while(c>'9'||c<'0'){

if(c=='-'){

f=-1;

}

c=getchar();

}

while(c<='9'&&c>='0'){

x=x*10+c-'0';

c=getchar();

}

return x*f;

}

void write(int x){

    if(x<0) putchar('-'),x=-x;

    if(x>9) write(x/10);

    putchar(x%10+'0');

}

int n,p,f[1000006],ca,te[1000006],score[1000006],ans;

signed main(){

// freopen("number.in","r",stdin);

// freopen("number.out","w",stdout);

n=read();

p=read();

ca=read();

te[1]=f[1]=ca;

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

ca=read();

f[i]=max(ca,f[i-1]+ca);

}

int maxx=f[1];

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

te[i]=max(f[i],maxx);

if(f[i]>maxx){

maxx=f[i];

}

}

score[1]=te[1];

int temp=score[1]+te[1];

ans=score[1];

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

score[i]=temp;

temp=max(temp,score[i]+te[i]);

ans=max(ans,score[i]);

}

write(ans%p);

return 0;

}

题目详情
39 简答题 偏难 信息学奥赛 ·信息学奥赛-入门级 · 10.2 排列组合

车站分级

【问题描述】

一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)

例如,下表是 5 趟车次的运行情况。其中,前 4 趟车次均满足要求,而第 5 趟车次由于停靠了 3 号火车站(2 级)却未停靠途经的 6 号火车站(亦为 2 级)而不满足要求。

现有 m 趟车次的运行情况(全部满足要求),试推算这 n 个火车站至少分为几个不同的级别。

【输入】

输入文件为 level.in。

第一行包含 2 个正整数 n, m,用一个空格隔开。

第 i + 1 行(1 ≤ i ≤ m)中,首先是一个正整数 si(2 ≤ si ≤ n),表示第 i 趟车次有 si 个停靠站;接下来有 si个正整数,表示所有停靠站的编号,从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

【输出】

输出文件为 level.out。

输出只有一行,包含一个正整数,即 n 个火车站最少划分的级别数。

【输入输出样例】

【数据范围】

对于 20%的数据,1 ≤ n, m ≤ 10;

对于 50%的数据,1 ≤ n, m ≤ 100;

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

答案与解析
参考答案

#include<bits/stdc++.h>

#define in  read()

#define N 10009

#define M 9000009 

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read(){

    char ch=nc();int sum=0;

    while(!(ch>='0'&&ch<='9'))ch=nc();

    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();

    return sum;

}

int n,m,du[N],chu[N];

int nxt[M],to[M],head[N],cnt=0;

void add(int x,int y){nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}

int s[N],g[1009][1009],dis[N];

bool vis[1009];

int main(){

n=in;m=in;

int i,j,k;

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

k=in;

memset(vis,0,sizeof(vis));

for(j=1;j<=k;++j){

int hh=in;

s[j]=hh;vis[hh]=1;

}

for(j=s[1];j<=s[k];++j){

if(!vis[j]){

for(int p=1;p<=k;++p){

if(!g[s[p]][j]){

g[s[p]][j]=1;

add(s[p],j);

du[j]++;

}

}

}

}

}

queue<int> q;

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

if(!du[i]) dis[i]=1,q.push(i);

int ans=-1;

while(!q.empty()){

int u=q.front();q.pop();

for(int e=head[u];e;e=nxt[e]){

int v=to[e];

dis[v]=dis[u]+1;

ans=max(ans,dis[v]);

du[v]--;

if(!du[v]) q.push(v);

}

}

cout<<ans;

return 0;

}

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

质因数分解

【问题描述】

已知正整数 n 是两个不同的质数的乘积,试求出较大的那个质数。

【输入】

输入文件名为 prime.in。

输入只有一行,包含一个正整数 n。

【输出】

输出文件名为 prime.out。

输出只有一行,包含一个正整数 p,即较大的那个质数。

【输入输出样例】

【数据范围】

对于 60%的数据,6 ≤ n ≤ 1000。

对于 100%的数据,

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int t;

    scanf("%d",&t);

    int i,j;

    for(i=2;i<=sqrt(t);i++)

    {

        if(t%i==0)

        {

            cout<<t/i<<endl;

            break;

        }

    }

    return 0;

}

题目详情