竞赛讨论区 > 本场比赛题解
头像
蒼穹
发布于 2018-09-12 22:42
+ 关注

本场比赛题解

A
式子拆开来看很容易发现是a[n]-a[1]=k,然后移项a[n]=a[1]+k,暴力枚举a[1]=1~9,计算a[n],若a[n]也在1~9则ans+=10^(n-2)
时间复杂度O(logn)
B
对每一位分开讨论,发现在l~r这个区间这一位上1的出现次数达到1/2则这一位为0,否则为1,对每一位做一个前缀和即可
PS:线段树会被卡空间,只有60分
C
首先优先取上下两列都是U的,对于剩下的3种:上下两列都是D的不管,而剩下来的,可以考虑对称博弈,所以很容易发现:U在上方>U在下方,则先手获胜;U在上方=U在下方,平局;这里有个易错点:U在上方+1=U在下方,这时候,先对称博弈,然后剩下的一个先手可以抢去,这样就也是平局;U在上方+1<U在下方,则后手必胜。若双U的个数为奇数怎么办?把其中一个视为U在上方D在下方即可。
D
题意:求斐波那契数列的前n+1项和,定义s[n]为斐波那契前n项和,然后可以得出s[n]=f[1]+f[2]+…+f[n],然后s[n]+1=1+f[1]+f[2]+…+f[n]=2+f[2]+f[3]+…+f[n]=f[3]+f[2]+f[3]+…+f[n]=f[4]+f[3]+f[4]+…+f[n]=……=f[n+2],所以s[n]=f[n+2]-1,所以当输入n时,输出f[n+3]-1即可。矩阵乘法优化即可通过本题(不会矩阵乘法可以O(n)递推得60~80(看你写的常数吧))
E
直接int128在NOIP是不允许的!!
于是,我们可以使用计算器(NOIP是有计算器的),手算出2^63-1、2^64-1、2^65-1以内模7余1的正整数,对于n以内模7余1的正整数,很容易求得是(n-1)/7+1。然后可以利用容斥原理,先求2^m-1以内模7余1的个数,再减去2^n-1以内模7余1的个数。
F
对于含有>2个该子串的字符串,可以直接判成NO(容易发现一次swap最多拆掉2个子串);对于有且仅有2个该子串的字符串,交换第一个子串的第一个位置、第二个子串的第二个位置即可;对于有且仅有1个该子串的字符串,交换该子串的第一、第二个位置即可;对于没有的,首先交换1、2,若交换后仍有该子串,则交换1、3,证明:若交换1、2产生子串,尽可能是usqingnianloveskirito...-->suqingnianloveskirito...和s?uqingnianloveskirito…-->?suqingnianloveskirito…(注:?不为s),所以交换1、3后,分别变为:qusingnianloveskirito…、us?qingnianloveskirito…,于是满足条件
对本场比赛的评价:
题出的好!覆盖知识点广,题目又着切合实际的背景,解法比较自然。
给出题人点赞!

给出题人点赞 !

全部评论

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

等你来战

查看全部

热门推荐