竞赛讨论区 > 【题解】西南科技大学2021届新生赛

【题解】西南科技大学2021届新生赛

头像
ChuTian
编辑于 2021-03-20 19:45:56 APP内打开
赞 2 | 收藏 2 | 回复1 | 浏览957

比赛总结:

预期难度:F,C,G<D,J<E,H,K<A,I<B<L
实际情况:C,F,G<E,D<J,A,H,K<B,I<L

题解:

题面很短,还没有大模拟,标程合起来都没500行,还是很阳间的吧。
由于另一个出题人怕被喷,所以就我来挨喷了。

A. 暗号I

知识:hash,二分
思路:
可以想到,先需要把本质相同的字符串找出来。那么只需要把字符串中每个字符按照第一次出现的顺序替换为即可。再通过map/unordered_map把本质相同的字符串进行映射,将他们的下标存入对应数组中。暴力查找的复杂度为,所以对于查询的区间通过二分查找下标,复杂度为。相减即可得到结果。

B. 暗号II

知识:dp
思路:
1、 表示长度为的字符串hash之后值为的有多少个。
初始设
对于枚举长度为的字符串每个后面加上一个字符后,得到的hash值为,将的值加入
最后输出即可。
复杂度为。所以原本考虑过限制条件为,可以通过动态开数组或者用滚动数组来解决。
2、数位dp,看成26进制的去搜索。

C. 3.6数对

知识:桶排
思路:
暴力的话复杂度为,显然是通过不了的。可以发现的值域很小,并且我们只要统计满足的数量,数量乘起来就是这种情况的所有可能。
所以将所有的数放入桶数组中,就是答案。

D. 圆的交点

知识:思维
思路:
我们画图可以发现只有三种类型的圆的组合存在交点。
1、相邻,即或者。他们之间的交点个数为。如图:
图片说明
很容易发现,这样的组合有种。
2、斜对面,即。他们之间的交点个数也为,并且都在整数点上。如图:
图片说明
3、相切,即或者。他们之间的交点个数为,并且我们可以发现这些交点与第2种情况是重合的。如图:
图片说明
结合2,3,我们发现所有作为圆心的点都是交点。
其实也很好想到,和作为圆心的点距离为的整数点数量肯定大于,所以作为圆心的点必然会成为几个圆的交点。
所有最终答案为

E. 孪生质数

知识:筛法,逆元
思路:
筛法预处理出素数,然后处理出孪生素数。
由于的数中孪生质数的数量为多一些。所以对于每次询问,遍历查找和二分查找中孪生素数的个数都可以。则

F. 数字金字塔

知识:记忆化/数学
思路:
朴素的想法是暴力,但是无论是还是的暴力都无法通过。
1、发现这种查询可以预处理先把他们全部算出来,然后在每次询问的时候直接查询就可以了。
2、公式:

G. 小凡做蛋糕

知识:思维
思路:
不难发现,点值为
因为可以发现蛋糕的高度是一层层递增的,所以一个点的高度与他和四边最近的距离有关,计算的相当于是求这是第几层蛋糕,乘上蛋糕胚的高度就是答案了。

H. 小凡出数据

知识:并查集/暴力
思路:
只用考虑的情况,很容易发现满足有且只有一组,的也一样。的只有两种情况,一是直接有一条长度为的边,二是之间有一点满足。那么我们可以发现如果是第二种情况的话,那么的连边关系肯定已经在前面确定了。
有两种参考方法:
1、由几个点存在需要维护的关系很容易就想到需要使用并查集。那么,按照权值从小到大,用并查集维护关系,如果两点不在同一个集合内,那么他们之间就存在一条边。
2、枚举是否存在中间点使得,但是这样的复杂度为。我们可以加一个判断是否成立,成立再进行判断是否存在。因为可以发现满足这个条件的点不太多,其余大量的点可以直接跳过,所以复杂度应该为级别。

I. 喜欢整除的磊哥

知识:数学,构造
思路:
提供两种参考方法:
1、
要求,那么我们可以求出。那么可以得到
所以我们就相当于要把改成。不妨设,可以发现,相当于计算的后位与的差值。当然,这个差值也有可能是负数,因为,所以负数的差值满足,那么再加上一个就好了。可以发现,这样按位替换就可以满足题目要求。
2、

考虑把拆成两部分,是一个位数。例如,那么把拆成

可得
要使的倍数,那么只需要就行了。知道了,就很好求出,并且,直接把后面替换成就行了。

J. 苏幕遮·寻姻缘

知识:贪心
思路:
这是一道非常经典的贪心题。
将线段按照左端点排序,遍历时维护最大的右端点值。可以想到,如果两条线段存在重合,那么前一条线段的右端点肯定大于后一条线段的左端点。计算一下重叠的长度,记录两条线段的编号即可。

K. 听闻远方有你,动身跋涉千里

知识:二分
思路:
首先我们先看一个人经过的行动轨迹,发现是前缀和的。那我们就可以维护两人每次行动后前缀和的最大最小值。
对于每次查询,我们先假设,我们发现,如果两人相逢,那么加上小源行动轨迹的右端点不能小于加上小凡行动轨迹的左端点。我们又通过上面可以发现,两个人行动轨迹的左端点肯定是一个非升序列,右端点肯定是一个非降序列。也就是说两个人一旦相逢,那么之后的时刻肯定都会相逢。
当然对于,我们要判断加上小凡行动轨迹的右端点不小于加上小源行动轨迹的左端点是否成立;对于的特殊情况,输出就可以了。
暴力判断的复杂度为,显然是不行的。那么可以想到,通过二分答案(相逢的时刻)去判断是否满足相逢的条件,这样复杂度为

L. 苍天阻我寻你,此情坚贞如一

知识:线段树,二分
思路:
通过上一题那么思路就很明显了。
因为需要修改,所以可以线段树将单点修改转化为区间修改。最朴素的是二分+区间查询,但是复杂度为,但的数据量显然无法通过,可以将二分操作在线段树上执行,复杂度为

标程:

A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083133
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083355
C:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083373
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083437
E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083448
F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083463
G:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083478
H:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083490
I:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083498
J:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083505
K:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47083516
L:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47087110

1条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐