2022年十三届蓝桥杯国赛（C/C++大学B组）个人题解

去年国赛基本都是暴力，最后国三都没拿到（我是废物），今年感觉比去年难了不少，而且时间没有安排好，第一题就被卡了好久，然后G题概率论也分析了好久，导致最后三题都没时间做了，总之就是一点暴力分都没骗到，希望做的题能多对几道吧，希望能拿个国三。10个循环暴力明显超时，有一点思路大概是最小数的范围在0-197之间，可能需要根据数的范围来做？然后就不会了。枚举时分秒，分别计算秒针、分针、时针与0时的夹角度

PolarDay.

22931人浏览 · 2022-06-19 13:16:34

PolarDay. · 2022-06-19 13:16:34 发布

2022年十三届蓝桥杯国赛（C/C++大学B组）个人题解

更新：成绩出来了，估分50分左右，最后拿了个国二，还差点到国一，有点出乎意料，挺满意了挺满意了。

去年国赛基本都是暴力，最后国三都没拿到（~~我是废物~~ ），今年感觉比去年难了不少，而且时间没有安排好，第一题就被卡了好久，然后G题概率论也分析了好久，导致最后三题都没时间做了，总之就是一点暴力分都没骗到，希望做的题能多对几道吧，希望能拿个国三。

试题 A: 2022

【问题描述】
将 2022 拆分成 10 个互不相同的正整数之和，总共有多少种拆分方法？
注意交换顺序视为同一种方法，例如 2022 = 1000 + 1022 和 2022 =1022 + 1000 就视为同一种方法。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

10个循环暴力明显超时，有一点思路大概是最小数的范围在0-197之间，可能需要根据数的范围来做？然后就不会了。

试题 B: 钟表

【问题描述】
在 12 小时制的钟表中，有分针、时针、秒针来表示时间。记分针和时针之间的夹角度数为 A（0 ≤ A ≤ 180）、分针和秒针之间的夹角度数为 B （0 ≤ B ≤ 180）。而恰好在 s 时 f 分 m 秒时，满足条件 A = 2B 且 0 ≤ s ≤ 6； 0 ≤ f < 60；0 ≤ m < 60，请问 s, f, m 分别是多少。
注意时针、分针、秒针都围绕中心匀速转动。
提交格式为三个由一个空格隔开的整数，分别表示 s, f, m。如 3 11 58表示3 点 11 分 58 秒。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为三个由一个空格隔开的整数，在提交答案时只填写为三个由一个空格隔开的整数，填写多余的内容将无法得分。

枚举时分秒，分别计算秒针、分针、时针与0时的夹角度数
秒针的夹角度数为：360 * m / 60；（一圈360度，秒针转了m / 60圈）
分针的夹角度数为：360 * f / 60 + 6 * m / 60；（分针转了f / 60圈，另外每两分钟之间相差6度（60秒），已经过了m秒，故再加上 6 * m / 60度）
时针的夹角度数：360 * s / 12 + 30 * (f * 60 + m) / 3600; （时针转了s / 12圈，另外每两小时之间相差30度（3600秒），已经过了f * 60 + m秒，故再加上30 * (f * 60 + m) / 3600度）

分针与时针之间的夹角度数即为分针与0时的夹角度数减去时针与0时的夹角度数的绝对值，同时要取小于180度的夹角值
分针和秒针的夹角同理

结果：4 48 0

代码：

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    double md, fd, sd;
    for (double m = 0; m < 60; m++)
    {
        md = 360 * m / 60;

        for (double f = 0; f < 60; f++)
        {
            fd = 360 * f / 60;
            fd += 6 * m / 60;

            for (double s = 0; s <= 6; s++)
            {
                sd = 360 * s / 12;
                sd += 30 * (f * 60 + m) / 3600;

                double A = fabs(fd - sd);
                A = min(A, 360 - A);
                double B = fabs(fd - md);
                B = min(B, 360 - B);
                if (A == 2 * B)
                {
                    cout << s << " " << f << " " << m << endl;
                }
            }
        }
    }
    return 0;
}

试题 C: 卡牌

【问题描述】
这天，小明在整理他的卡牌。
他一共有 n 种卡牌，第 i 种卡牌上印有正整数数 i(i ∈ [1, n])，且第 i 种卡牌现有 a_i 张。
而如果有 n 张卡牌，其中每种卡牌各一张，那么这 n 张卡牌可以被称为一套牌。小明为了凑出尽可能多套牌，拿出了 m 张空白牌，他可以在上面写上数i，将其当做第 i 种牌来凑出套牌。然而小明觉得手写的牌不太美观，决定第 i种牌最多手写 b_i 张。
请问小明最多能凑出多少套牌？
【输入格式】
输入共 3 行，第一行为两个正整数 n, m。
第二行为 n 个正整数 a₁, a₂, …, a_n。
第三行为 n 个正整数 b₁, b₂, …, b_n。
【输出格式】
一行，一个整数表示答案。
【样例输入】
4 5
1 2 3 4
5 5 5 5
【样例输出】
3
【样例说明】
这 5 张空白牌中，拿 2 张写 1，拿 1 张写 2，这样每种牌的牌数就变为了3, 3, 3, 4，可以凑出 3 套牌，剩下 2 张空白牌不能再帮助小明凑出一套。
【评测用例规模与约定】
对于 30% 的数据，保证 n ≤ 2000 ；
对于 100% 的数据，保证 n ≤ 2 × 10⁵; a_i, b_i ≤ n; m ≤ n² 。

~~比赛的时候忘记sort结构体数组怎么写了，又敲了个vector~~
先按照牌的现有张数排序，然后二分能凑出多少套牌

判断是否能凑出x套牌时，从小到大枚举，如果当前的现有的牌数大于x那么直接退出即可（剩下的也都大于x），如果现有牌数+最多可手写牌数小于x的话直接返回false，剩下的使用x-现有牌数张空白牌转换为当前牌，如果转换后的空白牌小于0说明空白牌不够也返回false

代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;
int n;
ll m;
struct card
{
    int a, b;
    card(int aa = 0, int bb = 0)
    {
        a = aa;
        b = bb;
    }
};
vector<card> vc;
bool cmp(card a, card b)
{
    return a.a < b.a;
}

bool jd(int x)
{
    ll tm = m;
    for (int i = 0; i < n; i++)
    {
        if (vc[i].a >= x)
            break;
        if (vc[i].a + vc[i].b < x)
            return false;
        tm -= (x - vc[i].a);
        if (tm < 0)
            return false;
    }
    return true;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        card t;
        cin >> t.a;
        vc.push_back(t);
    }
    for (int i = 0; i < n; i++)
        cin >> vc[i].b;

    sort(vc.begin(), vc.end(), cmp);

    //二分可能取到的最小值
    int l = vc[0].a, r = 5 * n + 5;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (jd(mid))
            l = mid;
        else
            r = mid - 1;
    }
    cout << l;
    return 0;
}

试题 D: 最大数字

【问题描述】
给定一个正整数 N。你可以对 N 的任意一位数字执行任意次以下 2 种操作：
1.将该位数字加 1。如果该位数字已经是 9，加 1 之后变成 0。
2.将该位数字减 1。如果该位数字已经是 0，减 1 之后变成 9。
你现在总共可以执行 1 号操作不超过 A 次，2 号操作不超过 B 次。
请问你最大可以将 N 变成多少？
【输入格式】
第一行包含 3 个整数：N, A, B。
【输出格式】
一个整数代表答案。
【样例输入】
123 1 2
【样例输出】
933
【样例说明】
对百位数字执行 2 次 2 号操作，对十位数字执行 1 次 1 号操作。
【评测用例规模与约定】
对于 30% 的数据，1 ≤ N ≤ 100; 0 ≤ A, B ≤ 10
对于 100% 的数据，1 ≤ N ≤ 10¹⁷; 0 ≤ A, B ≤ 100

不会，比赛的时候随便敲上了个能过样例的，现在看来有点离谱，不放上来误导大家了

试题 E: 出差

【问题描述】
A 国有 N 个城市，编号为 1 . . . N。小明是编号为 1 的城市中一家公司的员工，今天突然接到了上级通知需要去编号为 N 的城市出差。由于疫情原因，很多直达的交通方式暂时关闭，小明无法乘坐飞机直接从城市 1 到达城市 N，需要通过其他城市进行陆路交通中转。小明通过交通信息网，查询到了 M 条城市之间仍然还开通的路线信息以及每一条路线需要花费的时间。
同样由于疫情原因，小明到达一个城市后需要隔离观察一段时间才能离开该城市前往其他城市。通过网络，小明也查询到了各个城市的隔离信息。（由于小明之前在城市 1，因此可以直接离开城市 1，不需要隔离）
由于上级要求，小明希望能够尽快赶到城市 N，因此他求助于你，希望你能帮他规划一条路线，能够在最短时间内到达城市 N。
【输入格式】
第 1 行：两个正整数 N, M，N 表示 A 国的城市数量，M 表示未关闭的路
线数量
第 2 行：N 个正整数，第 i 个整数 Ci 表示到达编号为 i 的城市后需要隔离
的时间
第 3 . . . M + 2 行：每行 3 个正整数，u, v, c，表示有一条城市 u 到城市 v 的
双向路线仍然开通着，通过该路线的时间为 c
【输出格式】
第 1 行：1 个正整数，表示小明从城市 1 出发到达城市 N 的最短时间（到
达城市 N，不需要计算城市 N 的隔离时间）
【样例输入】
4 4
5 7 3 4
1 2 4
1 3 5
2 4 3
3 4 5
【样例输出】
13
【样例说明】
[1(5)] --4-- [2(7)]
|　　　　　｜
|　　　　　｜
5　　　　　3
|　　　　　｜
|　　　　　｜
[3(3)] --5-- [4(4)]
路线 1：1 -> 2 -> 4，时间为 4+7(隔离)+3=14
路线 2：1 -> 3 -> 4，时间为 5+3(隔离)+5=13
【评测用例规模与约定】
对于 100% 的数据，1 ≤ N ≤ 1000 , 1 ≤ M ≤ 10000, 1 ≤ Ci ≤ 200, 1 ≤ u, v ≤ N, 1 ≤ c ≤ 1000

dijkstra求最短路，建图的时候要把隔离时间加上，N点的隔离时间设为0（~~这大概是本次比赛最简单的一道题了，但是感觉自己对dijkstra的板子还是不熟，希望能做对吧~~ ）

代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e3 + 10;
const int M = 1e4 + 10;
int n, m;
bool vis[N];
int geli[N];
int edge[N][N];
int dis[N];

int dijkstra()
{
    vis[1] = true;
    for (int k = 1; k <= n; k++)
    {
        int d = 0x3f3f3f3f;
        int t = -1;
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i])
            {
                if (dis[i] < d)
                {
                    d = dis[i];
                    t = i;
                }
            }
        }
        vis[t] = true;
        for (int i = 1; i <= n; i++)
        {
            if (!vis[i] && edge[t][i] != 0)
            {
                if (dis[t] + edge[t][i] < dis[i])
                    dis[i] = dis[t] + edge[t][i];
            }
        }
    }
    return dis[n];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> geli[i];
    geli[n] = 0;
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    int u, v, c;
    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v >> c;
        edge[u][v] = c + geli[v];
        if (u == 1)
            dis[v] = min(dis[v], edge[u][v]);
        edge[v][u] = c + geli[u];
        if (v == 1)
            dis[u] = min(dis[u], edge[v][u]);
    }
    cout << dijkstra();

    return 0;
}

试题 F: 费用报销

【问题描述】
小明在出差结束后返回了公司所在的城市，在填写差旅报销申请时，粗心的小明发现自己弄丢了出差过程中的票据。
为了弥补小明的损失，公司同意小明用别的票据进行报销，但是公司财务要求小明提交的票据中任意两张的日期差不小于 K 天，且总金额不得超过实际差旅费用 M。
比如财务要求 K = 7 时，若小明提交了一张 1 月 8 日的票据，小明就不能提交 1 月 2 日至 1 月 14 日之间的其他票据，1 月 1 日及之前和 1 月 15 日及之后的票据则可以提交。
公司的同事们一起给小明凑了 N 张票据，小明现在想要请你帮他整理一下，从中选取出符合财务要求的票据，并使总金额尽可能接近 M。
需要注意，由于这些票据都是同一年的，因此 12 月底的票据不会影响到 1 月初票据的提交。这一年不是闰年。
【输入格式】
第 1 行：3 个整数，N, M, K 第 2 . . . N + 1 行：每行 3 个整数 mi, di, vi，第 i + 1 行表示第 i 张票据时间的月份 mi 和日期 di，vi 表示该票据的面值
【输出格式】
第 1 行：1 个整数，表示小明能够凑出的最大报销金额
【样例输入】
4 16 3
1 1 1
1 3 2
1 4 4
1 6 8
【样例输出】
10
【样例说明】
选择 1 月 3 日和 1 月 6 日的票据
【评测用例规模与约定】
对于 100% 的评测用例，1 ≤ N ≤ 1000, 1 ≤ M ≤ 5000, 1 ≤ K ≤ 50, 1 ≤ mi ≤
12, 1 ≤ di ≤ 31, 1 ≤ vi ≤ 400
日期保证合法。

本来以为是背包问题，做了一会发现不知道第二维该如何选择然后想到了下面的方法

先预处理每张票据距离年初的天数，然后根据天数排序，再预处理每张票据之前与他相差小于等于k天的最早的票据
然后DP只选择前i张票据所能凑出的最大报销金额，状态转移方程：f[i] = max(f[i - 1],f[minusk[i]] + vc[i].w);

刚刚发现忘记判断总金额是否超过M了，g

代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int month[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int N = 1e3 + 10;
int n, m, k;
int d[N], w[N];
int f[N];
map<int, int> minusk;
struct card
{
    int d, w;
    card(int dd = 0, int ww = 0)
    {
        d = dd;
        w = ww;
    }
};
bool cmp(card a, card b)
{
    return a.d < b.d;
}
vector<card> vc;
int main()
{
    cin >> n >> m >> k;
    int mm, dd, vv;
    for (int i = 1; i <= n; i++)
    {
        cin >> mm >> dd >> vv;
        int days = 0;
        for (int i = 1; i < mm; i++)
            days += month[i];
        days += dd;
        d[i] = days;
        w[i] = vv;
    }
    card t;
    vc.push_back(t);
    for (int i = 1; i <= n; i++)
    {
        card t;
        t.d = d[i];
        t.w = w[i];
        vc.push_back(t);
    }
    sort(vc.begin(), vc.end(), cmp);

    for (int l = 0, r = 1; r <= n; r++)
    {
        if (vc[r].d - vc[l].d > k)
            l++;
        minusk[r] = l;
    }

    f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        f[i] = max(f[i - 1], f[minusk[i]] + vc[i].w);
    }
    cout << f[n];
    return 0;
}

试题 G: 故障

【问题描述】
在软件或系统开发中，我们会遇到各种各样的故障。为了从故障现象反推故障原因，工程师们会总结一种叫做相关性矩阵的二维表格，来表示故障原因与故障现象之间的关系。比如：

1 2 3 4 5
A X X X
B X X
C X X

其中每行表示一种故障原因，每一列表示一种故障现象。该矩阵表示故障原因 A 可能产生故障现象 2、3、4，故障原因 B 可能产生故障现象 1、3。
在实际开发过程中，如果出现了故障原因，工程师就可以根据故障现象，去计算每种故障原因产生的概率，并按照概率大小对故障原因进行排查，以达到快速定位故障原因的目的。
现在，我们假设系统开发中同一时间只会出现一种故障原因，并且故障原因引起各故障现象是独立事件。举个例子来说：
假设系统现在发生了故障原因 A，有 $\frac{1}{3}$ 的概率出现故障现象 2，有 $\frac{1}{4}$ 的概率出现故障现象 3，有 $\frac{1}{2}$ 的概率出现故障现象 4。由于 3 种现象是独立发生的，因此有 $\frac{1}{2×3×4}$ 的概率同时出现故障 2、3、4。
约定若相关性矩阵中没有 ‘x’ 记号，则表示该故障原因一定不会产生某故障现象，比如故障原因 A，一定不会产生故障现象 1。
根据历史经验数据，我们统计得到了每一种故障原因出现的概率以及每一种故障原因对应的故障现象产生概率。
现在已知系统出现的故障现象，求问各个故障原因发生的概率
【输入格式】
第 1 行：2 个正整数 N, M，N 表示故障原因的个数（编号 1 . . . N），M 表示故障现象的个数（编号 1 . . . M）
第 2 行：N 个整数，第 i 个数表示故障原因 i 产生的概率 P_i.
第 3 . . . N + 2 行：每行 M + 1 个整数，第 i + 1 行第 j 个整数 P_ij 表示故障原因 i 出现故障现象 j 的概率（百分比）.
第 N + 3 行：1 个正整数 K，表示目前出现的故障现象数量
第 N + 4 行：K 个正整数，依次为当前出现的故障现象编号，不会重复
【输出格式】
第 1 . . . N 行：按概率从高到低输出每种故障原因及其可能的概率，若出现概率相同则优先输出编号小的故障原因。第 1 个数为故障原因编号，第 2 个数为故障概率（百分比），保留 2 位小数。
【样例输入】
3 5
30 20 50
0 50 33 25 0
30 0 35 0 0
0 0 0 25 60
1
3
【样例输出】
2 56.89
1 43.11
3 0.00
【评测用例规模与约定】
对于所有测试用例，1 ≤ N ≤ 40, 1 ≤ M ≤ 20, 0 ≤ P_i ≤ 100，∑(P_i) = 100， 0 ≤ P_ij ≤ 100

	1	2	3	4	5
A		X	X	X
B	X		X
C				X	X

这道题这个样例看了好久才看明白导致最后三道题一点都没做，希望能做对吧

先讲一下样例是怎么输出的

由于发生了故障现象3，而原因3不可能导致故障现象3的发生，所以首先排除原因3

然后分析原因1导致现象3的概率，原因1导致发生故障现象3的概率为（现象1不发生的概率 * 现象2不发生的概率 * 现象3发生的概率 * 现象4不发生的概率 * 现象5不发生的概率），即1 * 1-50/100 * 33/100 * 1-25/100 * 1 = 0.12375

同理分析原因2导致现象3的概率， 1-30/100 * 1 * 35/100 * 1 * 1 = 0.245

上面分析的是发生了原因1导致产生故障现象3的概率，下面还要求原因发生的概率，因为原因3不可能发生了，所以只分析原因1,2
原因1的概率为30，原因2的概率为20，所以发生原因1的概率即为30/(30+20)=0.6，同理发生原因2的概率为20/(30+20)=0.4

综上所述
原因1导致故障3的概率为0.6 * 0.12375 = 0.07425
原因2导致故障3的概率为0.4 * 0.12375 = 0.098
原因3导致故障3的概率为0

因为这有这三种原因相加概率应该为1，所以处理一下
原因1的结果即为：0.07425/(0.07425+0.098) = 0.4310595
原因2的结果即为：0.098/(0.07425+0.098) = 0.56894
原因3的结果即为：0

分析出样例来，这道题就比较简单了，下面贴上我的代码，由于比赛的时候时间不多了，所以代码很多地方都没处理好，很混乱，到最后才测试出样例，大家随便看看就好了

代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <iomanip>

using namespace std;

const int N = 45;
const int M = 45;
double p[N][N];
int n, m, k;
double pgz[N];                //原因概率
unordered_map<int, int> gzxx; //发生现象
unordered_map<int, int> knyy; //原因
struct ans
{
    int gz;
    double p;
    ans(int a = 0, double b = 0)
    {
        gz = a;
        p = b;
    }
};
bool cmp(ans a, ans b)
{
    if (a.p == b.p)
        return a.gz < b.gz;
    return a.p > b.p;
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> pgz[i];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> p[i][j];
    cin >> k;
    for (int i = 1; i <= k; i++)
    {
        int xx;
        cin >> xx;
        gzxx[xx] = 1;
    }

    vector<int> kngz; //可能故障原因
    for (int i = 1; i <= n; i++)
    {
        int j;
        for (j = 1; j <= m; j++)
        {
            if (gzxx[j] && p[i][j] == 0)
                break;
        }
        if (j == m + 1)
        {
            kngz.push_back(i);
            knyy[i] = 1;
        }
    }

    double zy = 0; //原因总概率
    for (int i = 0; i < kngz.size(); i++)
        zy += pgz[kngz[i]];

    vector<double> pkngz; //可能故障的概率
    double sumgl = 0;
    for (int i = 0; i < kngz.size(); i++)
    {
        int yy = kngz[i];
        double ptemp = pgz[yy] / zy;
        for (int j = 1; j <= m; j++)
        {
            if (p[yy][j] == 0)
                continue;
            if (gzxx[j])
                ptemp *= (p[yy][j] / 100);
            else
                ptemp *= (1 - p[yy][j] / 100);
        }
        sumgl += ptemp;
        pkngz.push_back(ptemp);
    }
    vector<ans> vc;

    for (int i = 0; i < pkngz.size(); i++)
    {
        ans tans;
        tans.gz = kngz[i];
        tans.p = pkngz[i] / sumgl;
        vc.push_back(tans);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!knyy[i])
        {
            ans tans(i, 0);
            vc.push_back(tans);
        }
    }
    sort(vc.begin(), vc.end(), cmp);
    for (int i = 0; i < vc.size() - 1; i++)
        cout << vc[i].gz << " " << fixed << setprecision(2) << vc[i].p * 100 << endl;
    cout << vc[vc.size() - 1].gz << " " << fixed << setprecision(2) << vc[vc.size() - 1].p * 100 << endl;
    return 0;
}

试题 H: 机房

【问题描述】
这天，小明在机房学习。
他发现机房里一共有 n 台电脑，编号为 1 到 n，电脑和电脑之间有网线连
接，一共有 n − 1 根网线将 n 台电脑连接起来使得任意两台电脑都直接或者间接地相连。
小明发现每台电脑转发、发送或者接受信息需要的时间取决于这台电脑和多少台电脑直接相连, 而信息在网线中的传播时间可以忽略。比如如果某台电脑用网线直接连接了另外 d 台电脑，那么任何经过这台电脑的信息都会延迟 d 单位时间 (发送方和接收方也会产生这样的延迟，当然如果发送方和接收方都是同一台电脑就只会产生一次延迟)。
小明一共产生了 m 个疑问：如果电脑 ui 向电脑 vi 发送信息，那么信息从ui 传到 vi 的最短时间是多少？
【输入格式】
输入共 n + m 行，第一行为两个正整数 n, m。
后面 n − 1 行，每行两个正整数 x, y 表示编号为 x 和 y 的两台电脑用网线直接相连。
后面 m 行，每行两个正整数 ui, vi 表示小明的第 i 个疑问。
【输出格式】
输出共 m 行，第 i 行一个正整数表示小明第 i 个疑问的答案。
【样例输入】
4 3
1 2
1 3
2 4
2 3
3 4
3 3
【样例输出】
5
6
1
【样例说明】
这四台电脑各自的延迟分别为 2, 2, 1, 1。
对于第一个询问，从 2 到 3 需要经过 2, 1, 3，所以时间和为 2 + 2 + 1 = 5。
对于第二个询问，从 3 到 4 需要经过 3, 1, 2, 4，所以时间和为 1+2+2+1 = 6。
对于第三个询问，从 3 到 3 只会产生一次延迟，所以时间为 1。
【评测用例规模与约定】
对于 30% 的数据，保证 n, m ≤ 1000；
对于 100% 的数据，保证 n, m ≤ 100000 。

没看题，以后再补

试题 I: 齿轮

【问题描述】
这天，小明在组装齿轮。
他一共有 n 个齿轮，第 i 个齿轮的半径为 r_i，他需要把这 n 个齿轮按一定顺序从左到右组装起来，这样最左边的齿轮转起来之后，可以传递到最右边的齿轮，并且这些齿轮能够起到提升或者降低转速 (角速度) 的作用。

小明看着这些齿轮，突然有 Q 个疑问：能否按一定顺序组装这些齿轮使得最右边的齿轮的转速是最左边的齿轮的 q_i 倍？
【输入格式】
输入共 Q + 2 行，第一行为两个正整数 n, Q，表示齿轮数量和询问数量。
第二行为 n 个正整数 r₁,r₂, …,r_n，表示每个齿轮的半径。
后面 Q 行，每行一个正整数 q_i 表示询问。
【输出格式】
Q 行，对于每个询问，如果存在至少一种组装方案满足条件，输出 ‘YES‘，否则输出 ‘NO‘。
【样例输入】
5 3
4 2 3 3 1
2
4
6
【样例输出】
YES
YES
NO
【样例说明】
询问 1 方案之一：2 3 3 4 1
询问 2 方案之一：4 2 3 3 1
询问 3 没有方案
【评测用例规模与约定】
对于 15% 的数据，保证 n, Q ≤ 100 ；
对于 30% 的数据，保证 n, Q ≤ 2000 ；
对于 100% 的数据，保证 n, Q ≤ 2 × 10⁵; a_i, q_i ≤ 2 × 10⁵ 。

没看题，以后再补

试题 J: 搬砖

【问题描述】
这天，小明在搬砖。
他一共有 n 块砖，他发现第 i 砖的重量为 w_i，价值为 v_i。他突然想从这些砖中选一些出来从下到上堆成一座塔，并且对于塔中的每一块砖来说，它上面所有砖的重量和不能超过它自身的价值。
他想知道这样堆成的塔的总价值（即塔中所有砖块的价值和）最大是多少。
【输入格式】
输入共 n + 1 行，第一行为一个正整数 n，表示砖块的数量。
后面 n 行，每行两个正整数 w_i, v_i 分别表示每块砖的重量和价值。
【输出格式】
一行，一个整数表示答案。
【样例输入】
5
4 4
1 1
5 2
5 5
4 3
【样例输出】
10
【样例说明】
选择第 1、2、4 块砖，从上到下按照 2、1、4 的顺序堆成一座塔，总价值为 4 + 1 + 5 = 10
【评测用例规模与约定】
对于 20% 的数据，保证 n ≤ 10；
对于 100% 的数据，保证 n ≤ 1000; w_i ≤ 20; v_i ≤ 20000 。