再也不打欢乐赛了(上白银了)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T1
简单的判断:
T2
判断+简单循环
判断一个数是回文数:把这个数倒过来,判断是否与原数相同。
剩下的就是简单判断循环了,相信大家都能写出来。
T3
预处理一个布尔数组,值为这一天是否全部都有空。
然后直接求最大值就行了。
T4
我不知道我是怎么在赛时写了个[已编辑]东西吃了 444 发罚时,最后气急败坏打了个暴力(结果还吃了一发)
思路就是用一个布尔数组储存每个时间段是否有常客,暴力,最后统计的时候用一个计数器算没有常客的连续时长,除上 aaa 就行。
T5
差分(当然用线段树/树状数组也行,这里就不展示了,毕竟不是动态查询,直接差分完了)
这题是个原题,我之前做过,CF的一道,好像是什么饮料的推荐温度。
[补]就是,原题链接,洛谷链接
差分:差分是前缀和的逆运算,也就是说差分数组前缀和以后就是原数组。于是我们注意到,区间 [l,r][l,r][l,r] 只要让差分数组的第 lll 位加 111,第 r+1r+1r+1 位减 111,前缀和后 [l,r][l,r][l,r] 就整体加一了,而这就能运用到本题上了。
前缀和:定义前缀和数组 sumsumsum,sumi=sumi−1+ai=∑j=1iajsum_i=sum_{i-1}+a_i=\sum_{j=1}^ia_jsumi =sumi−1 +ai =∑j=1i aj ,注意到求区间 [l,r][l,r][l,r] 和只需求 sumr−suml−1sum_r-sum_{l-1}sumr −suml−1 即可(sumr−suml−1=∑i=1rai−∑i=1l−1ai=∑i=lraisum_r-sum_{l-1}=\sum_{i=1}^ra_i-\sum_{i=1}^{l-1}a_i=\sum_{i=l}^ra_isumr −suml−1 =∑i=1r
ai −∑i=1l−1 ai =∑i=lr ai )。
然后用前缀和算 [l,r][l,r][l,r] 所有推荐次数大于等于 kkk 的就行了。
T6
写了个线段树,这题就是求 ai≥aj+k(i<j)a_i\ge a_j+k(i<j)ai ≥aj +k(i<j) 的数量,实际上就是线段树(似乎树状数组也行,但是不知道为啥写了线段树,可能是想练练抄书)求逆序对板子改点。