CSUST 2021周赛2题解

发布于 2021-02-22  130 次阅读



欸 朋友们好啊,我是浑元形意Coding门掌门人Uli。刚才有个朋友问我,U老师发生什么事啦?我说怎么回事,给我发了几张截图。我一看,哦,原来是昨天,有两篇题解,CSDN,一个长度2000多字,一个长度1000多字。然后上来就是,一个简单暴力,一个二分查找,一个最小生成树。我全部看懂了啊,看懂以后自然是,传统算法以点到为止,因为这时间,按照传统算法的点到为止,我就AC了。我收手的时间不敲了,他突然袭击,啊,我大意了啊,没有闪。欸,他的题解,没有写代码。但没关系啊,他也说,他结束也说了。两分多钟以后,当时流眼泪了捂着眼,我说停停,然后两分钟以后,两分多钟以后,就AC了。我说小伙子你不讲武德你不懂,他说U老师对不起对不起,我不懂规矩。啊,他说他是乱写的,他可不是乱写的啊,思路,板子,证明,训练有素。后来他说他练过三四年编程啊,看来是有备而来。这两个年轻人
不讲武德



偷袭
我19岁的
老同志
这好吗,这不好
我劝这位年轻人
好自为之
好好反思
不要再犯这样的聪明
小聪明
ACM要以和为贵
要讲武德
不要搞
窝里斗
谢谢朋友们
所以我的题解也不写代码了。

这周题目虽然,不难吧,但是差点爆零,非常的惊险,刺激啊。所以呢,还是写写题解,抖擞抖擞精神,希望大家,啊,能看懂啊。

A

题面

睿智小明买鞭炮
Description

在大家的帮忙下,小明成功完成了数学作业。现在小明决定出门找沸阳阳一起去放鞭炮庆祝。

现在有一家商店正在贩卖鞭炮,庆新年活动促销规则如下(举个栗子):

一次性购买鞭炮少于10盒 收取2元/盒

一次性购买鞭炮多于10盒 收取1元/盒。

如果小明买9盒鞭炮,那么会花费18元,如果小明买11盒鞭炮,花费11元,此时如果小明需要购买9盒的条件下,购买11盒将是最小花费

因此你能帮帮数学不好的沸阳阳算出,当沸阳阳购买一定数量Ai 的鞭炮所需的最小花费吗 (购买的数量只需要大于等于Ai即可)

Input
第一行输入:现在商店有n种促销规则,沸阳阳q次咨询。

第二行输入:共2*n个整数 S1,P1,S2,P2.....Sn,Pn 表示当购买鞭炮数不少于Si时每盒贩卖Pi元

第三行输入:q个整数 Q1,Q2....Qq 表示询问购买Qi盒鞭炮

Output
输出共q行:每行表示购买Qi盒鞭炮所需的最少花费

Sample Input 1
2 3
0 20 100 10
0 99 100
Sample Output 1
0
1000
1000

Hint
0<n,q<=1e5

0=S1<S2<...<Sn≤1e9

1e9≥P1≥P2≥P3≥...≥Pn≥0

题解

类型:二分,预处理
首先就不说小明做完作业和沸阳阳买鞭炮有什么关系了。然后也不说我做的时候没看到数据单调了。
数据单调,意味着只有买的数量多才有可能更便宜。思路就是对于每一个Qi,在S中找到第一个数量大于Qi的位置,记为pos。由于单调,所以这个位置可以二分找。那么,Qi*P(pos-1) 就是按照最少购买数的那个方案买的开销。要想花更少的钱,只有看看再多买能不能便宜点,所以从pos往后找。对于每一个方案i来说,买恰好Si个是花费最少的,所以可以把所有Si*Pi先算出来,然后问题转化为求[pos,n]区间中花费的最小值,与最少购买数的那个方案取min即可。

B

题面

龙卷风摧毁飞机场
Description

“为春运送温暖” 某航空公司现有N架飞机,每一架飞机都有其飞行路线。飞行路线包含不少于两个城市并且没有城市会在一条飞机路线上出现两次。现在假如乘客购买了某一架飞机的机票,该乘客可以在该航线的任意城市登机并在登机城市后的任意城市下机,其花费为航线票价。一个乘客至多使用两条航线。

现在沸阳阳想从城市S到达城市T 聪明的你能帮帮他算出最小花费吗?

Input
第一行输入3个数字:S T N (N≤500)

接下来2*N行描述可用的航线:

第一行输入该航线的费用 以及沿线城市数量(不超过500个)

第二行输入按顺序的沿线城市编号,城市编号不会超过1e4

Output
输出共一行 : 如果能从S城市到达T城市 输出最小花费

否则输出 -1

Sample Input 1
1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 2
Sample Output 1
7

题解

类型:暴力,模拟
注意到一个乘客最多用两条航线,这就是说要么一条航线走到底,要么换乘一次,就这两种情况。但是实现的时候我们并不用真的对两种情况进行讨论。
简单思考一下,对于每一条航线,能够到达的点要么位于起点右边,要么位于终点左边。这是可以直接确定的。所以我们定义数组S[MAXN]表示起点到每一个点的距离,先初始化为inf,然后遍历一遍航线把能确定的开销全都更新为最小开销,一条航线走到底的情况就是S[T]。最后再遍历一遍每一个点,对于每一个点而言,换乘的情况就是 起点到i点距离 + i点到终点距离 。最后,如果距离仍然大于等于inf,说明不可到达。

C

题面

5G传输
Description

现在有N个城市,需要更换新一代网络。已知在城市Ai安装5G信号塔需要花费Pi 而且该城市网络传输效率可以带动任意个城市。现在一个城市P可以从另一个已经更换了5G的城市Q获得5G 。现在给出N*N的矩阵C,C[i,j] 表示城市 i j 之间建立5G网络需要花费C[i,j] (注意前提)

作为此项项目的总工程师的你,能算出使得所有城市均普及5G网络的最小花费吗

Input
第一行 输入一个 N (N≤300)

接下来N行 每行一个数 Pi 表示在当前城市建立5G信号塔的花费i

接下来输入一个N*N的矩阵C

Output
输出仅一行 完成该工程的最小花费

Sample Input 1
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
Sample Output 1
9

Hint
0≤Pi,C[i,j]≤ 1e5

题解

类型:MST
使用的算法显而易见,MST。然而还是想了好久最后才憋出来真是太菜了。(哭)
与裸题的区别,在于每个点有自己的权重。在朴素的MST中,自己到自己是不可能有开销的。一开始想的是将起点的dis赋值为自己的权重,再进行n次prim,然而这显然是错的。然后考虑把权重加进mp里,无果。
一拍脑袋,插一个点进去,它到自己的权重为0,它与所有点都有边相连,这些边的权重就是这些点自己的权重不就完事了吗?然后一发过了。(有被蠢到)

D

题面

神奇的数字串
Description

现在给出一串由n个整数组成的数字串,例如S0,S1,S2....Sn-1 ;

现在我们对数字串循环移位K位后,数字串为Sk,Sk+1,…,Sn−1,S0,S1,…,Sk−1;

现在定义当一个数字串满足对于任意的前i(1≤i≤n)项和都满足不小于0,即为good串。

聪明的小沸想知道对于一个给定的数字串S,在循环移位K位后,一共有多少个good串。

Input
第一行一个整数n,表示基数字串的长度。

第二行n个整数,依次为S0,S1,…,Sn−1的值。

Output
输出一行 :good串的总数

Sample Input 1 
3
2 2 3
Sample Output 1
3

Hint

满足1≤N≤1e6, |Si| ≤1e3, 0≤K≤n-1

对于循环移位K位以后,若存在完全相同的数字串,则视为不同的贡献,并非重复贡献

题解

类型:区间求最小值,前缀和
首先,老规矩复制一遍原串,预处理前缀和。在新串中,对于每一个长度为n的子串,如果满足在这个子串的区间中前缀和最小的数减去区间左边界-1的前缀和大于等于0,则它对答案贡献1。问题转化为求每一个子串区间中前缀和的最小值。这个可以用单调队列,线段树,树状数组实现。
bb一句,单调队列的实现比线段树简单多了,我这样的懒人很舒服。关于单调队列的讲解本文就不涉及了。
线段树的一种实现

E

题面

矩阵
Description

已知n \times n的矩阵c的元素的构成为c_{ij}=a_i\times b_j,现有q次询问,每次询问给你两个坐标(x_1,y_1),(x_2,y_2)

请输出\sum\limits_{i=x_1}^{x_2}gcd(c_{i,y_1},c_{i,y_1+1},\dots,c_{i,y_2})的值,其中函数gcd(x,y)为x与y的最大公约数。

Input
第一行包含一个正整数n(1\leq n\leq 100000),表示二维矩阵的大小。

第二行包含n个整数a_i(0\leq a_i\leq 1000000)

第三行包含n个正数b_i(0\leq b_i\leq 1000000)

第四行包含一个正整数q(1\leq q\leq 100000)

接下来q行,每行包含四个正整数x_1,y_1,x_2,y_2(1\leq x_1\leq x2\leq n,1\leq y_1\leq y_2\leq n)

Output
输出共有q行,每行输出对应询问的答案。

Sample Input 1
3
1 2 3
3 2 1
2
1 2 2 2
1 2 2 3
Sample Output 1
6
3

题解

类型:数论,预处理
先吐槽下学校oj的latex语法解析为什么这么蛋疼,复制过来都乱的。
这个问题就是求a的区间和与b的区间gcd的乘积。区间和咋做都行,区间gcd推荐线段树。

Q.E.D.


夢に僕らで帆を張って 来るべき日のために夜を越え。