本次校赛出题人有7个,每人2道(一道中文,一道英文),总共14道
题意:
第1行输入一个字符串,代表每一位加法运算所遵循的进制表规则,第2,3行输入两个运算数,按照进制表规则输出运算结果
思路:
先把2个字符串都在开头补0,使其等长,然后把这2个数加起来,之后进制转换,最后注意输出格式就可以了
思路:
每个人都可以拿(给自己加分)或者禁(不让对分加禁了的数字的分),所以是拿还是禁就是看能拿的选择和能禁的选择中谁的贡献大(就是面值大),确定了操作方式就可以模拟了
题意:
一共有N组条件,每一组有2个字符串(B和H),若H可以由B截取其中K个连续字符并放到最前面得到,那么这组就可以匹配成功,问这N组中有几组可以匹配成功
思路:
考点:字符串哈希
- 直接使用储存Hash值,计算时不处理算术溢出问题(产生溢出时相当于自动对
取模,这样可以避免低效的mod运算),且一般取哈希进制数P为131或13331
- 区间
的字符串哈希值公式为:
- 在
串中找连续的
个字符,和
串前
个字符匹配上,之后检验其余部分是否能匹配上即可,最终复杂度为
,其中
为字符串总长度
代码:
思路:
也是签到题,认真想一下,从1到n检查有没有空缺就可以了
思路:
每个测试样例不超过 组测试数据,实现实数长度
不超过
的大实数加法,注意是否输出小数点,省略无意义的0
时间复杂度
思路:
考点:背包DP,树形 DP
我们可以抽象为有根树中一个点最多只有一个父亲结点,这是一个森林,方便起见,我们可以新增一篇开心度为 的文章(设这篇文章的开心度为
),作为所有无先导诗文篇章的先导诗文,这样我们就将森林变成了一棵以
号诗文为根的树,而且恰好满足题意输入
设表示以
号点为根的子树中,已经遍历了
号点的前
棵子树,选了
篇文章的当前累计最大开心值之和,转移的过程中,我们枚举
点的每个子结点
,同时枚举以
为根的子树选的文章数(设为
),将子树的结果合并到
上,另外,设以
为根的子树大小为
,点
的儿子个数为
,有状态转移方程:
的第二维可以用滚动数组的方式省略掉,这时设
为在
及
以下的子树上选
篇文章(范围在
至
)所能得到的当前累计最大开心值之和,注意这时需要倒序枚举
的值,对于
,从
至
枚举就好了,而且我们可以证明,该做法的时间复杂度为
代码:
思路:
签到题,直接输出对应校赛的举办时间即可
代码:
思路:
本题所需解决的问题有3个:
- 计算蛋糕的大小:观察题目,我们可以知道蛋糕的宽都是相同的,因此判断每块蛋糕的面积的大小只需要判断蛋糕上下底边的和的大小即可
- 统计每块蛋糕上水果的个数:枚举每个水果的坐标,使用二分查找(通过向量的叉积判断水果在断口的左边还是右边)水果左边最右边的断口(或右边最左边的断口),统计每个断口被查找的次数即可求出每块蛋糕上水果的次数(蛋糕边缘的切割点的坐标可以利用前缀和求出)
- 找出所求蛋糕:可以通过记录当前最优解查找,也可使用结构体排序后直接选出
代码:
题意:
找到中的
、
,使得
最大。
思路:
二分+位运算
给 l 的二进制补 1 ,只要没超过 r 就一直补,最后得到的数和 r 或运算就是结果
思路:
本题所需解决的问题有2个:
- 快速的求出范围内的所有质数:很明显使用定义来判断质数的总时间复杂度为
,而本题的数据范围在1e7,肯定会超时,接下来采用埃氏筛,其效率是
,虽然已经很快了,但是在残暴数据1e7面前仍会超时,最后便是本题的正解:欧拉筛(线性筛)正如名字那样,他的时间复杂度为
,在利用线性筛打好表后,我们只需要枚举每个数,判断他们是否是素数,如果是则把他们存在一个数组中
- 对数组进行排序:大概有
个素数,最后我们直接进行排序就好(排序使用时间复杂度不超过
即可)
代码:
题意:
输入y,找出输入后函数在0-100上的最小值
思路:
算法:二分法求解
给原方程求导之后运用二分法求解。
思路:
给定一颗 的无根树 (
,保证无环),注意到
,题目要求
次树上修改,
次树上询问。因此使用邻接表建图之后,对每次修改和查询暴力
求解即可,注意开
,时间复杂度
思路:
题目要求两个人到达同一地点所需时间最少,所以可以对每个人分别bfs一下,找到之和最小的那个点即可
思路:
签到题,为啥都不做捏QAQ,直接枚举所有的子串,然后判断是否回文就好了,因为输入字符串中间可能会有空格,所以输入方式推荐用getline
代码:
如若转载,请注明出处:https://www.zhidianwenhua.com/238.html