温馨提示: 1)有些链接需要在本校OJ上的博客里才能打开。2)没更新完。
晚上打了场AtCoder,rank1515rank 1515rank1515,切了5题,信心++。
zswangziye的atcoder账号
打T5的时候心态不稳,没验证好复杂度就交了,错了7次,下次注意。
早上8点多就回校了,假期减了一天。
上午模拟赛,考得不好,pts和rk就不说了,信心–。
比赛补题地址
T1签到题,枚举两个相同字母的位置,计算把这两个字母之间其他的字母扔出去的交换代价,在交换代价合规情况下找最大可能的连续相同字母大小。
T2是DP,分成五种情况讨论,f[i][0]f[i][0]f[i][0]表示当前位置为’0’,f[i][1]f[i][1]f[i][1]表示当前位置为’*‘,f[i][2]f[i][2]f[i][2]表示当前位置为’2’,f[i][3]f[i][3]f[i][3]表示当前位置为’1’左边有地雷,f[i][4]f[i][4]f[i][4]表示当前位置为’1’右边有地雷。然后讨论各种情况的状态转移。
T3是一种神奇的题目,先在原序列中把每个连续上升子串内部标记成同一编号,然后讨论几种可能的修改情况:1)在该子串前方或后方修改一个,使其长度+1。2)如果两个连续子串之间可以通过修改前一个子串合并,那就合并。3)修改后一个子串。
T4需要推一推,具体如下:
首先求平均数在[l,r][l,r][l,r]等价于求平均数在[1,l)[1,l)[1,l)和[1,r][1,r][1,r]的数量,后者减去前者即为答案。
以区间[i,j][i,j][i,j]的平均数为例,如果平均数需要满足这个性质,那么每个数减去rrr后求和的值必须≤0\leq 0≤0。
即为a[i]−r+a[i+1]−r+……+a[i+j−1]−r≤0a[i]-r+a[i+1]-r+……+a[i+j-1]-r \leq 0a[i]−r+a[i+1]−r+……+a[i+j−1]−r≤0.
设b[i]=a[i]−rb[i]=a[i]-rb[i]=a[i]−r,则b[i]+b[i+1]+……+b[i+j−1]≤0b[i]+b[i+1]+……+b[i+j-1] \leq 0b[i]+b[i+1]+……+b[i+j−1]≤0.
容易联想到前缀和,设s[i]=Σj≤ib[j]s[i]=\Sigma_{j \leq i} b[j]s[i]=Σj≤ib[j],可得s[i+k−1]−s[i−1]≤0s[i+k-1]-s[i-1] \leq 0s[i+k−1]−s[i−1]≤0,即s[i+k−1]≤s[i−1]s[i+k-1] \leq s[i-1]s[i+k−1]≤s[i−1].
发现i−1≤i+k−1i-1 \leq i+k-1i−1≤i+k−1,所以求逆序对。
开始停课,第一次全天停。
上午提高难度模拟赛,160pts160 pts160pts rank1rank 1rank1,感觉良好,信心++。
改题可以看DengDuck’s blog
比赛补题地址
T1,直接放官方题解:
T2,也直接放官方题解:
还有一个写的不错的题解:这里
T3,DengDuck的题解
T4超纲。
期待周五ing。