蓝桥杯C/C++百校真题赛（3期）Day3(考勤刷卡、最大和)

Q1 考勤刷卡

问题描述

小蓝负责一个公司的考勤系统, 他每天都需要根据员工刷卡的情况来确定 每个员工是否到岗。

当员工刷卡时, 会在后台留下一条记录, 包括刷卡的时间和员工编号, 只 要在一天中员工刷过一次卡, 就认为他到岗了。

现在小蓝导出了一天中所有员工的刷卡记录, 请将所有到岗员工的员工编 号列出。

输入格式

输入的第一行包含一个正整数 n n n, 表示一天中所有员工的刷卡记录的条数。 接下来 n n n 行, 每行包含一条刷卡记录, 每条刷卡记录的格式为:

HH:MM:SS ID

其中 HH:MM: SS 表示刷卡时间, HH 为一个 0 到 23 之间的两位十进制整数 (可能含前导 0 ) 表示时, MM 为一个 0 到 59 之间的两位十进制整数 (可能含前 导 0) 表示分, SS 为一个 0 到 59 之间的两位十进制整数 (可能含前导 0 ) 表 示秒, ID 为一个不含前导 0 的整数表示员工的编号。

所有记录按照刷卡时间升序排列, 可能同一时刻有多人刷卡。

输出格式

输出若干行, 每行包含一个整数, 按照从小到大的顺序输出, 表示到岗员 工的编号。

分析:与时间无关，只要记录哪些编号出现过就可以了，用map同时可以满足排序要求.

/*
* @Author: gorsonpy
* @Date:   2023-01-15 11:52:59
* @Last Modified by:   gorsonpy
* @Last Modified time: 2023-01-15 11:55:34
*/
#include<iostream>
#include<map>
using namespace std;

map<int, bool> m;
int main()
{
    int n;
    cin >> n;

    for(int i = 0; i < n; ++i)
    {
        string s;
        int id;
        cin >> s >> id;
        m[id] = true;
    }

    for(auto t : m) cout << t.first << endl;
    return 0;
}

Q2 最大和

问题描述

小蓝在玩一个寻宝游戏, 游戏在一条笔直的道路上进行, 道路被分成了 n n n 个方格, 依次编号 1 至 n n n, 每个方格上都有一个宝物, 宝物的分值是一个整数 (包括正数、负数和零), 当进入一个方格时即获得方格中宝物的分值。小蓝可 以获得的总分值是他从方格中获得的分值之和。

小蓝开始时站在方格 1 上并获得了方格 1 上宝物的分值, 他要经过若干步 到达方格 n n n。

当小蓝站在方格 p p p 上时, 他可以选择跳到 p + 1 p+1 p+1 到 p + D ( n − p ) p+D(n-p) p+D(n−p) 这些方格 中的一个, 其中 D ( 1 ) = 1 , D ( x ) ( x > 1 ) D(1)=1, D(x)(x>1) D(1)=1,D(x)(x>1) 定义为 x x x 的最小质因数。

给定每个方格中宝物的分值, 请问小蓝能获得的最大总分值是多少。

输入格式

输入的第一行包含一个正整数 n n n 。

第二行包含 n n n 个整数, 依次表示每个方格中宝物的分值。

输出格式

输出一行包含一个整数, 表示答案。

分析:根据题意一个人的走法只能向前无法后退,所以可以按照递推的顺序把f算出来，d的计算可以先筛出质数然后再查询质数表看哪些是因子.

/*
* @Author: gorsonpy
* @Date:   2023-01-15 12:55:28
* @Last Modified by:   gorsonpy
* @Last Modified time: 2023-01-15 13:38:56
*/
#include<iostream>
using namespace std;

const int N = 1e4 + 10;
int primes[N], w[N], n, d[N], cnt, f[N];
bool st[N];

void init()
{
    for(int i = 2; i < N; ++i)
    {
        if(!st[i]) primes[cnt ++] = i;

        for(int j = 0; primes[j] <= N / i; ++j)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }

    d[1] = 1;
    for(int i = 2; i <= 1e4; ++i)
    {
        int j = 0;
        while(j + 1 < cnt && i % primes[j]) ++j;
        d[i] = primes[j];
    }
}
int main()
{
    init();

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> w[i];
    for(int i = 1; i <= n; ++i) f[i] = -1e6;

    f[1] = w[1];

    for(int i = 1; i <= n - 1; ++i)
    {
        for(int j = i + 1; j <= i + d[n - i] && j <= n; ++j)
        {
            if(f[j] == -1e6) f[j] = w[j] + f[i];
            else f[j] = max(w[j] + f[i], f[j]);
        }
    }

    cout << f[n] << endl;
    return 0;
}