记录一下国赛的题面,真的和省赛完全不是一个难度的。这次估计国三都混不到,还是太菜了QAQ,之后如果能补题解就补吧。
题面的pdf文件我也上传到CSDN下载区了,内容和本篇文章相同。
(题面真长,我复制到markdown修改格式都搞了半天)

11.15中午更新:混到个国三,~~然而并没什么用~~
@

试题 A: 合数个数(5 分)

【问题描述】
一个数如果除了 1 和自己还有其他约数,则称为一个合数。例如:1, 2, 3不是合数,4, 6 是合数。
请问从 1 到 2020 一共有多少个合数。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

试题 B: 含 2 天数(5 分)

【问题描述】
小蓝特别喜欢 2,今年是公元 2020 年,他特别高兴,因为每天日历上都可以看到 2。
如果日历中只显示年月日,请问从公元 1900 年 1 月 1 日到公元 9999 年 12月 31 日,一共有多少天日历上包含 2。即有多少天中年月日的数位中包含数字2。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

试题 C: 本质上升序列(10 分)

【问题描述】
小蓝特别喜欢单调递增的事物。

在一个字符串中,如果取出若干个字符,将这些字符按照在字符串中的顺序排列后是单调递增的,则成为这个字符串中的一个单调递增子序列。

例如,在字符串 lanqiao 中,如果取出字符 n 和 q,则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。

小蓝发现,有些子序列虽然位置不同,但是字符序列是一样的,例如取第二个字符和最后一个字符可以取到 ao,取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。

对于一个字符串,小蓝想知道,本质不同的递增子序列有多少个?

例如,对于字符串 lanqiao,本质不同的递增子序列有 21 个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。

请问对于以下字符串(共 200 个小写英文字母,分四行显示):
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
本质不同的递增子序列有多少个?

【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

C题代码

#include <bits/stdc++.h>
using namespace std;
const int N=210;
int dp[N],ans=0;
bool vis[N];
int main()
{
    string s="tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
    int n=s.length();
    for(int i=0;i<n;i++)
    {
        if(!vis[s[i]])dp[i]++; // 单个字母组成的串只加一次
        vis[s[i]]=1;
        for(int j=i-1;j>=0;j--)
        {
            if(s[j]==s[i])break; // 遇到了上一次出现的相同字母就停止,因为之前的已经计算过了
            if(s[j]<s[i])
            {
                dp[i]+=dp[j];
            }
        }
        ans+=dp[i];
    }
    printf("%d\n",ans);
    return 0;
}

答案:3616159

试题 D: 咫尺天涯(10 分)

【问题描述】
皮亚诺曲线是一条平面内的曲线。
下图给出了皮亚诺曲线的 1 阶情形,它是从左下角出发,经过一个 3 × 3 的方格中的每一个格子,最终到达右上角的一条曲线。

在这里插入图片描述
设每个格子的边长为 1,在上图中,有的相邻的方格(四相邻)在皮亚诺曲线中也是相邻的,在皮亚诺曲线上的距离是 1,有的相邻的方格在皮亚诺曲线中不相邻,距离大于 1。

例如,正中间方格的上下两格都与它在皮亚诺曲线上相邻,距离为 1,左右两格都与它在皮亚诺曲线上不相邻,距离为 3。

下图给出了皮亚诺曲线的 2 阶情形,它是经过一个 3^2^ × 3^2^ 的方格中的每一个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。

在这里插入图片描述
下图给出了皮亚诺曲线的 3 阶情形,它是经过一个 3^3^ × 3^3^ 的方格中的每一个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。

在这里插入图片描述
皮亚诺曲线总是从左下角开始出发,最终到达右上角。

小蓝对于相邻的方格在皮亚诺曲线上的相邻关系很好奇,他想知道相邻的方格在曲线上的距离之和是多少。

例如,对于 1 阶皮亚诺曲线,距离和是 24,有 8 对相邻的方格距离为 1, 2 对相邻的方格距离为 3,2 对相邻的方格距离为 5。

再如,对于 2 阶皮亚诺曲线,距离和是 816。请求出对于 12 阶皮亚诺曲线,距离和是多少。

提示:答案不超过 10^18^。

【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一 个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

试题 E: 玩具蛇(15 分)

【问题描述】
小蓝有一条玩具蛇,一共有 16 节,上面标着数字 1 至 16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成 90 度角。

小蓝还有一个 4 × 4 的方格盒子,用于存放玩具蛇,盒子的方格上依次标着字母 A 到 P 共 16 个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现,有很多种方案可以将玩具蛇放进去。

下图给出了两种方案:
在这里插入图片描述

请帮小蓝计算一下,总共有多少种不同的方案。如果两个方案中,存在玩具蛇的某一节放在了盒子的不同格子里,则认为是不同的方案。

【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。

试题 F: 皮亚诺曲线距离(15 分)

时间限制: 1.0s 内存限制: 256.0MB

【问题描述】
皮亚诺曲线是一条平面内的曲线。
下图给出了皮亚诺曲线的 1 阶情形,它是从左下角出发,经过一个 3 × 3 的方格中的每一个格子,最终到达右上角的一条曲线。

在这里插入图片描述

下图给出了皮亚诺曲线的 2 阶情形,它是经过一个 3^2^ × 3^2^ 的方格中的每一个格子的一条曲线。它是将 1 阶曲线的每个方格由 1 阶曲线替换而成。

在这里插入图片描述
下图给出了皮亚诺曲线的 3 阶情形,它是经过一个 3^3^ × 3^3^ 的方格中的每一个格子的一条曲线。它是将 2 阶曲线的每个方格由 1 阶曲线替换而成。

在这里插入图片描述

皮亚诺曲线总是从左下角开始出发,最终到达右上角。

我们将这些格子放到坐标系中,对于 k 阶皮亚诺曲线,左下角的坐标是(0, 0),右上角坐标是 (3^k^ − 1, 3^k^ − 1),右下角坐标是 (3^k^ − 1, 0),左上角坐标是(0, 3^k^ − 1)。

给定 k 阶皮亚诺曲线上的两个点的坐标,请问这两个点之间,如果沿着皮亚诺曲线走,距离是多少?

【输入格式】
输入的第一行包含一个正整数 k,皮亚诺曲线的阶数。第二行包含两个整数 x1, y1,表示第一个点的坐标。
第三行包含两个整数 x2, y2,表示第二个点的坐标。

【输出格式】
输出一个整数,表示给定的两个点之间的距离。

【样例输入】
1
0 0
2 2

【样例输出】
8

【样例输入】
2
0 2
0 3

【样例输出】
13

【评测用例规模与约定】
对于 30% 的评测用例,0 ≤ k ≤ 10。
对于 50% 的评测用例,0 ≤ k ≤ 20。
对于所有评测用例,0 ≤ k ≤ 100, 0 ≤ x1, y1, x2, y2 < 3^k^, x1, y1, x2, y2 ≤ 10^18^。
数据保证答案不超过 10^18^。

试题 G: 出租车(20 分)

时间限制: 1.0s 内存限制: 256.0MB

【问题描述】
小蓝在 L 市开出租车。

L 市的规划很规整,所有的路都是正东西向或者正南北向的,道路都可以看成直线段。东西向的道路互相平行,南北向的道路互相平行,任何一条东西 向道路垂直于任何一条南北向道路。

从北到南一共有 n 条东西向道路,依次标号为 H1, H2, · · · , Hn。从西到东一共有 m 条南北向的道路,依次标号为 S1, S2, · · · , Sm。

每条道路都有足够长,每一条东西向道路和每一条南北向道路都相交,Hi 与 Sj 的交叉路口记为 (i, j)。

从 H1 和 S1 的交叉路口 (1, 1) 开始,向南遇到的路口与 (1, 1) 的距离分别是 h1, h2, · · · , $h_{n−1}$,向东遇到路口与 (1, 1) 的距离分别是 w1, w2, · · · , $w_{m−1}$。

道路的每个路口都有一个红绿灯。
时刻 0 的时候,南北向绿灯亮,东西向红灯亮,南北向的绿灯会持续一段时间(每个路口不同),然后南北向变成红灯,东西向变成绿灯,持续一段时间后,再变成南北向绿灯,东西向红灯。

已知路口 (i, j) 的南北向绿灯每次持续的时间为 $g_{ij}$,东西向的绿灯每次持续的时间为 $r_{ij}$,红绿灯的变换时间忽略。

当一辆车走到路口时,如果是绿灯,可以直行、左转或右转。如果是红灯,可以右转,不能直行或左转。如果到路口的时候刚好由红灯变为绿灯,则视为看到绿灯,如果刚好由绿灯变为红灯,则视为看到红灯。

每段道路都是双向道路,道路中间有隔离栏杆,在道路中间不能掉头,只 能在红绿灯路口掉头。掉头时不管是红灯还是绿灯都可以直接掉头。掉头的时间可以忽略。

小蓝时刻 0 从家出发。今天,他接到了 q 个预约的订单,他打算按照订单的顺序依次完成这些订单,就回家休息。中途小蓝不准备再拉其他乘客。

小蓝的家在两个路口的中点,小蓝喜欢用 x1, y1, x2, y2 来表示自己家的位置,即路口 (x1, y1) 到路口 (x2, y2) 之间的道路中点的右侧,保证两个路口相邻(中间没有其他路口)。请注意当两个路口交换位置时,表达的是路的不同两边,路中间有栏杆,因此这两个位置实际要走比较远才能到达。

小蓝的订单也是从某两个路口间的中点出发,到某两个路口间的中点结束。

小蓝必须按照给定的顺序处理订单,而且一个时刻只能处理一个订单,不能图省时间而同时接两位乘客,也不能插队完成后面的订单。

小蓝只对 L 市比较熟,因此他只会在给定的 n 条东西向道路和 m 条南北向道路上行驶,而且不会驶出 H1, Hn, S1, Sm 这几条道路所确定的矩形区域(可以到边界)。

小蓝行车速度一直为 1,乘客上下车的时间忽略不计。请问,小蓝最早什么时候能完成所有订单回到家。

【输入格式】
输入第一行包含两个整数 n, m,表示东西向道路的数量和南北向道路的数量。
第二行包含 n − 1 个整数 h1, h2, · · · , $h_{n−1}$。
第三行包含 m − 1 个整数 w1, w2, · · · , $w_{m−1}$。
接下来 n 行,每行 m 个整数,描述每个路口南北向绿灯的时间,其中的第 i 行第 j 列表示 $g_{ij}$。
接下来 n 行,每行 m 个整数,描述每个路口东西向绿灯的时间,其中的第 i 行第 j 列表示 $r_{ij}$。
接下来一行包含四个整数 x1, y1, x2, y2,表示小蓝家的位置在路口 (x1, y1)到路口 (x2, y2) 之间的道路中点的右侧。
接下来一行包含一个整数 q,表示订单数量。
接下来 q 行,每行描述一个订单,其中第 i 行包含八个整数 $x_{i1}$, $y_{i1}$, $x_{i2}$, $y_{i2}$, $x_{i3}$, $y_{i3}$, $x_{i4}$, $y_{i4}$,表示第 i 个订单的起点为路口 ($x_{i1}$, $y_{i1}$) 到路口 ($x_{i2}$, $y_{i2}$) 之间的道路中点的右侧,第 i 个订单的终点为路口 ($x_{i3}$, $y_{i3}$) 到路口 ($x_{i4}$, $y_{i4}$) 之间的道路中点的右侧。

【输出格式】
输出一个实数,表示小蓝完成所有订单最后回到家的最早时刻。四舍五入保留一位小数。

【样例输入】
2 3
200
100 400

10 20 10
20 40 30
20 20 20
20 20 20
2 1 1 1
1
2 2 1 2 1 2 1 3

【样例输出】
1620.0

【样例说明】
小蓝有一个订单,他的行车路线如下图所示。其中 H 表示他家的位置,S 表示订单的起点,T 表示订单的终点。小明在最后回家时要在直行的红绿灯路口等绿灯,等待时间为 20。

【评测用例规模与约定】
对于 20% 的评测用例,1 ≤ n, m ≤ 5,1 ≤ q ≤ 10。对于 50% 的评测用例,1 ≤ n, m ≤ 30,1 ≤ q ≤ 30。
对于所有评测用例,1 ≤ n, m ≤ 100,1 ≤ q ≤ 30,1 ≤ h1 < h2 < · · · < $h_{n−1}$ ≤ 100000,1 ≤ w1 < w2 < · · · < $w_{m−1}$ ≤ 100000,1 ≤ $g_{ij}$ ≤ 1000,1 ≤ $r_{ij}$ ≤ 1000, 给定的路口一定合法。

试题 H: 答疑(20 分)

时间限制: 1.0s 内存限制: 256.0MB

【问题描述】
有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。老师可以安排答疑的顺序,同学们要依次进入老师办公室答疑。

一位同学答疑的过程如下:
1. 首先进入办公室,编号为 i 的同学需要 si 毫秒的时间。
2. 然后同学问问题老师解答,编号为 i 的同学需要 ai 毫秒的时间。
3. 答疑完成后,同学很高兴,会在课程群里面发一条消息,需要的时间可 以忽略。
4. 最后同学收拾东西离开办公室,需要 ei 毫秒的时间。一般需要 10 秒、20 秒或 30 秒,即 ei 取值为 10000,20000 或 30000。

一位同学离开办公室后,紧接着下一位同学就可以进入办公室了。
答疑从 0 时刻开始。老师想合理的安排答疑的顺序,使得同学们在课程群里面发消息的时刻之和最小。

【输入格式】
输入第一行包含一个整数 n,表示同学的数量。
接下来 n 行,描述每位同学的时间。其中第 i 行包含三个整数 si, ai, ei,意义如上所述。

【输出格式】
输出一个整数,表示同学们在课程群里面发消息的时刻之和最小是多少。

【样例输入】
3
10000 10000 10000
20000 50000 20000
30000 20000 30000

【样例输出】
280000

【样例说明】
按照 1, 3, 2 的顺序答疑,发消息的时间分别是 20000, 80000, 180000。

【评测用例规模与约定】
对于 30% 的评测用例,1 ≤ n ≤ 20。
对于 60% 的评测用例,1 ≤ n ≤ 200。
对于所有评测用例,1 ≤ n ≤ 1000,1 ≤ si ≤ 60000,1 ≤ ai ≤ 1000000,ei ∈ {10000, 20000, 30000},即 ei 一定是 10000、20000、30000 之一。

试题 I: 奇偶覆盖(25 分)

时间限制: 1.0s 内存限制: 256.0MB

【问题描述】
在平面内有一些矩形,它们的两条边都平行于坐标轴。
我们称一个点被某个矩形覆盖,是指这个点在矩形的内部或者边界上。
请问,被奇数个矩形覆盖和被偶数 (≥ 2) 个矩形覆盖的点的面积分别是多少?

【输入格式】
输入的第一行包含一个整数 n,表示矩形的个数。
接下来 n 行描述这些矩形,其中第 i 行包含四个整数 li, bi, ri, ti,表示矩形的两个对角坐标分别为 (li, bi), (ri, ti)。

【输出格式】
输出两行。
第一行包含一个整数,表示被奇数个矩形覆盖的点的面积。
第二行包含一个整数,表示被偶数 (≥ 2) 个矩形覆盖的点的面积。

【样例输入】
3
1 1 3 3
2 2 4 4
3 3 5 5

【样例输出】
8
2

【评测用例规模与约定】
对于 20% 的评测用例,1 ≤ n ≤ 10, 0 ≤ li < ri ≤ 100, 0 ≤ bi < ti ≤ 100。
对于 40% 的评测用例,1 ≤ n ≤ 1000, 0 ≤ li < ri ≤ 100, 0 ≤ bi < ti ≤ 100。
对于 60% 的评测用例,1 ≤ n ≤ 10000, 0 ≤ li < ri ≤ 1000, 0 ≤ bi < ti ≤ 1000。
对于 80% 的评测用例,1 ≤ n ≤ 100000, 0 ≤ li < ri ≤ 100000, 0 ≤ bi < ti ≤100000。
对于所有评测用例,1 ≤ n ≤ 100000, 0 ≤ li < ri ≤ 10^9^, 0 ≤ bi < ti ≤ 10^9^。

试题 J: 蓝跳跳(25 分)

时间限制: 2.0s 内存限制: 256.0MB

【问题描述】
小蓝制作了一个机器人,取名为蓝跳跳,因为这个机器人走路的时候基本靠跳跃。

蓝跳跳可以跳着走,也可以掉头。蓝跳跳每步跳的距离都必须是整数,每步可以跳不超过 k 的长度。由于蓝跳跳的平衡性设计得不太好,如果连续两次都是跳跃,而且两次跳跃的距离都至少是 p,则蓝跳跳会摔倒,这是小蓝不愿意看到的。

小蓝接到一个特别的任务,要在一个长为 L 舞台上展示蓝跳跳。小蓝要控制蓝跳跳从舞台的左边走到右边,然后掉头,然后从右边走到左边,然后掉头,然后再从左边走到右边,然后掉头,再从右边走到左边,然后掉头,如此往复。

为了让观者不至于太无趣,小蓝决定让蓝跳跳每次用不同的方式来走。小 蓝将蓝跳跳每一步跳的距离记录下来,按顺序排成一列,显然这一列数每个都不超过 k 且和是 L。这样走一趟就会出来一列数。如果两列数的长度不同,或者两列数中存在一个位置数值不同,就认为是不同的方案。

请问蓝跳跳在不摔倒的前提下,有多少种不同的方案从舞台一边走到另一边。

【输入格式】
输入一行包含三个整数 k, p, L。

【输出格式】
输出一个整数,表示答案。答案可能很大,请输出答案除以 20201114 的余数。

【样例输入】
3 2 5

【样例输出】
9

【样例说明】
蓝跳跳有以下 9 种跳法:
1. 1+1+1+1+1
2. 1+1+1+2
3. 1+1+2+1
4. 1+2+1+1
5. 2+1+1+1
6. 2+1+2
7. 1+1+3
8. 1+3+1
9. 3+1+1

【样例输入】
5 3 10

【样例输出】
397

【评测用例规模与约定】
对于 30% 的评测用例,1 ≤ p ≤ k ≤ 50,1 ≤ L ≤ 1000。
对于 60% 的评测用例,1 ≤ p ≤ k ≤ 50,1 ≤ L ≤ 10^9^。
对于 80% 的评测用例,1 ≤ p ≤ k ≤ 200,1 ≤ L ≤ 10^18^。
对于所有评测用例,1 ≤ p ≤ k ≤ 1000,1 ≤ L ≤ 10^18^。