m102 SE赛

这次考试考完试正在刷提交记录的时候，到我这突然oj卡了一下，然后卡了大约10s，再刷出来就发现：

然后。。。。。新成就赛时SE2333

反正也是测文件，就没有找老师重测！%%%fh FE 90 %%%

这次考试T1其实看了两个小时，但是死活不知道题是在说什么，不知道是我的语文不好还是出题人的语文不好，然后我T1就爆零了废话，题意都理解错了还能有分？

别的两道题倒是暴力都打了，但是觉得T1没A，心里很慌，看了T1半个小时之后就开始干T2T3，然后半个小时打了100分又开始看T1，然后就死了，我万万没有想到就是死在了读题上，考试的时候就是不知道他的两个弧和两个顶点到底是都满足还是部分满足，然后就死了，

题解：

T1当时觉得就是单调栈，由于题意理解错，在赛后%%%_LH大神帮我理解题意，然后我终于有了一个单调栈的构思，但是瓶颈就在与不会处理相等的情况，就是处理一下栈内的值和他的个数，在弹栈的时候如果和栈顶不相等，那么栈顶就贡献答案，如果相等就和所有相等的值贡献答案，还要和栈内第一个大于这个值的贡献答案，（注意是一个单调递减单调栈），然后我们就处理出来了不是以第一个数为右端点的所有答案，那么我们还差以第一个数作为右端点的贡献，我们可以正着倒着分别扫一遍，然后只要是从右侧看是最高的但是从左边看不是最高的就可以贡献答案。主要的瓶颈就是维护相同的值的处理方法和读题！CODE 就不放了！

由于lsc过于弱智，导致T2只会打40分算法，考试的时候主要不知道他多次经历同一个点怎么办，其实我们只要设dp[i]为从1第一次走到i的时间

那么我们可以推出$dp[i+1]=dp[i]+1$这是让他先到i，然后再走一步就跳回去然后再加上$dp[i]-dp[p[i]]$这就让他又走到了i

然后再+1就是$dp[i+1]$

总的柿子就是 $dp[i+1]=dp[i]+1+dp[i]-dp[p[i]]+1=dp[i]*2-dp[p[i]]+2$

然后你就愉快的100分！ CODE就不放了！

巴特西

m102 SE赛

最新文章

热门文章