竞赛讨论区 > 【题解】2020牛客寒假算法基础集训营第一场
头像
神崎兰子
编辑于 2020-02-06 20:21
+ 关注

【题解】2020牛客寒假算法基础集训营第一场

注:每道题的参考cf难度分指codeforces.com对题目的难度评分(出题人自己估计)

写在题解前面的话

首先这次的题目难度并不大,大概是codeforces的div3水平(因为出题人rating只有1900太菜了QAQ)。比赛进行相对比较顺利,值得庆幸的是数据并没有出什么问题。
另外A题的样例描述有个小错误(坐标(3,2)写成了(3,3)),G题的题面容易引起歧义(“k个相同字母”)。
J题的测试样例仍然不够强,放过了部分错误代码。
这些都是我要检讨的,这里向大家说一声抱歉QAQ

J的样例已经加强,之前ac的童鞋们可以重新提交试试(不会影响排名)

J原来的标程也有错,不能通过加强后的样例,已更新标程。

level 1 hanayo和米饭

知识点: 数组 循环

签到题。有多种方法可以做,最省事的方法是把每个数标记一下,然后遍历输出没标记的那个数就可以了。
参考cf难度分:700

level 1 kotori和bangdream

知识点:概率论

签到题。每个音符的得分期望是 个音符的总得分期望为每个音符的期望乘以
参考cf难度分:900

level 2 rin和快速迭代

知识点:数论 模拟

只要会 复杂度处理每一次迭代就行。是一道披着假数论的implementation
参考cf难度分:1000

level 3 eli和字符串

知识点:字符串 前缀和 双指针

可以单独处理每种字母找 个的长度(双指针),然后求最小值。
或者也可以开26个前缀和,然后双指针找区间维护最小值。
参考cf难度分:1300

level 4 honoka和格点三角形

知识点:计数

可以把面积为 的“好三角形”分为两类分开统计:两条边和两个坐标轴平行;只有一条边和某个坐标轴平行。
对于第一种情况,一定是 或者 的形式,一个 的矩形中含有4个不同的三角形。总数是
对于第二种情况,可以分别统计底边为 、高为 和底边为 、高为 的情况。要注意底边靠近边界时的特殊讨论。
①对于底边为2,高为1的情况:
若底边和x轴平行,那么底边横向移动(指x轴水平移动,下同)有 种可能,“对点”(指底边相对的点)的某一面选择有 种可能(某一面选择,指的是底边固定的情况,对点在一条直线上移动所做出的选择),而底边纵向移动有 种情况,其中有 种情况对点可以选择两个面,2种情况对点只能选择一个面(当底边移动到格点阵边界的时候)。因此纵向移动折合为 ,即
以上可计算为
若底边和y轴平行,同理可推出
②对于底边为1,高为2的情况,推理方法和上面类似,请选手们自行推理。
参考cf难度分:1500

level 4 nozomi和字符串

知识点:字符串 贪心

显然操作要么全10,要么全01
分别处理两种操作即可。对于10的情况,可以分别统计每个1的前缀1和后缀1的位置(第一个1的前缀为 ,最后一个1的后缀为 ),那么 次操作,即变换连续 1,最终的字符串长度就是第 1的前缀1到第个后缀1之间的距离。
对于01的情况同理。
参考cf难度分:1600

level 5 maki和tree

知识点:图论
经过一个黑点的路径有两种:两个端点都是白点;其中一个端点是黑点。
因此我们可以先预处理,将每个白点连通块上的白点个数统计出来。这样我们就可以得知每个黑点所连接的白点的权值(即连通块白点数)。
设某黑点连接了 个白点,第 个白点的权值为
这样第一种路径的数量为,第二种路径的数量为。第一种可以用前缀和处理达成 计算
参考cf难度分:1900

level 5 umi和弓道

知识点:计算几何 双指针

首先确定umi所在位置的象限。很明显同一象限的点是不可能用挡板挡掉的,对于剩下的点找出线段和 轴或 轴的交点,统计坐标位置(如果存在交点的话)。
之后双指针维护 轴上或者 轴挡住 个点的挡板长度最小值。注意 轴和 轴要分开计算。
参考cf难度分:2000

level 5 nico和niconiconi

知识点:动态规划

代表前 个字符的计数最大值。
那么可得转移方程:



最后输出 即可。
参考cf难度分:1800

level 6 μ's的影响力

知识点:数论 矩阵快速幂

显然 可以用 , 这三个因子表达出来。
每一项a的幂次分别是 从第三项开始每一项为前两项之和加1。
而x和y的幂次构成斐波那契数列:x的幂次第一项是1,第二项是0;y的幂次第一项是0,第二项是1。之后每一项均为前两项之和。
根据费马小定理,由于1e9+7是素数,有 。因此幂的指数对1e9+6取模即可。要注意a是1000000007的倍数的特殊情况。
可以用矩阵快速幂O(logn)求出x、y、a幂次的第n项。
矩阵快速幂求斐波那契数列的第n项方法如下:
假设代表斐波那契数列的第 项,显然有:
图片说明
因此
图片说明
图片说明 的值可以用快速幂算出来,这样就可以O(logn)实现计算斐波那契数列的第n项了。
有关快速幂的知识:
要求 mod p,我们可以得出
①若b为偶数,
②若b为奇数,
可以看到幂是指数级别下降的,因此最终复杂度是而不是朴素算法的
参考cf难度分:2200

标程:

A: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786029
B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786046
C:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786057
D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786062
E:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786070
F:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786077
G:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786086
H:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786091
I:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42786097
J:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42789798

全部评论

(53) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐