注:每道题的参考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和字符串
知识点:字符串 贪心
显然操作要么全1
变0
,要么全0
变1
。
分别处理两种操作即可。对于1
变0
的情况,可以分别统计每个1
的前缀1
和后缀1
的位置(第一个1
的前缀为 ,最后一个
1
的后缀为 ),那么
次操作,即变换连续
个
1
,最终的字符串长度就是第 个
1
的前缀1
到第个后缀
1
之间的距离。
对于0
变1
的情况同理。
参考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) 回帖