竞赛讨论区 > 【题解】牛客OI周赛13-普及组
头像
已注销
编辑于 2019-12-11 17:15
+ 关注

【题解】牛客OI周赛13-普及组

T1 zn的手环

大讨论一下就好了
先转化成24h制, 然后算一下时间跨度也可以。
具体如下:
1.如果同为早上或者下午, 入睡时间早于起床时间那么答案可以直接算。 否则需要把起床时间+24h来算
2.如果不同的话, 此时我们对起床时间直接+12h即可。

标程点击这里查看~

T2 zn的游戏

直接找最接近的两个数之间的距离就行了, 在这里两个数指max{ai}和min{ai}, 然后对距离取min即可
为什么呢...因为如果[l, r]中有子区间[l', r']满足[l', r']包含了最小值和最大值,
那么肯定不选[l, r]。
同理我们发现每一对最大值和最小值都能组成一个区间, 然后我们只需要取最接近的一组就行了。
由于读入量过大所以需要快读, 不然会tle最后一个点。

T3 zn的绳子

很容易可以发现, 上一个位置有没有交叉对下一个位置并没有什么影响。
然后我们可以发现最多有n - 1个交叉, 最少有0个交叉
那么我们需要<=k个交叉的话, 只需要在n - 1个交叉中选k个来放, 也就是C(n - 1, k)
然后对于n 最多为1e7 那么我们需要线性求逆元的姿势。
可以先logN算出inv(n!) 然后通过inv(i!) = inv((i + 1)!) * (i + 1) 来倒推

标程点击这里查看~

T4 zn的幸运数字

首先, 对于质数P有这么一个性质
对于任意整数x满足都有
很容易可以证明

首先对于p, 由于a为整数, 所以有
然后对于质数p, d(p) = 2, 由于2 ~ p内的整数都满足
所以有
所以

所以我们只需要从n往下扫到第一个质数就可以停下来了。
由于质数密度很大, 在随机数据下(好像不随机数据也可以), 每logN就会出现一个质数
所以期望效率是
但是对于x = 1的时候, 考虑到, 此时并不满足对于任意A, B有
所以我们需要特判一下x = 1时候的情况。

标程点击这里查看~

吐槽

QAQ怎么好像没啥人打(((
好像没啥人答疑(对比上一场是不是我语文变好了, 果然文化课快乐(迫真))
好像T2因为数据过大的原因把scanf卡了, 要快读才能过最后一个点

全部评论

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

等你来战

查看全部

热门推荐