Codeforces Edu R39

居然Rated!

哇我明天早自习怕不是要被查水表了QAQ

不管了先补下题解

A. Partition

这题很zz你就把正数划到B负数划到C就行了

代码↓

B. Weird Subtraction Process

这题也很zz,fqk学长推了下式子然而我直接写了个二分

二分(a或b)*2*k可以证明复杂度非常优秀,大概在O(logn)还是怎么着的反正减一次还是减两次就完事了

具体证明等我再补 不一定能记得补

来补

复杂度是O(log2n)

C. String Transformation

贪心。忽略掉z即可

别忘记特判,具体看代码

D. Timetable

前三题都是热身题,这才是个正经题

dp。

先设dx[i][j]是第i天逃课j次后的最小度过时间

dp求这个东西,O(nk2) 先枚举每一天,这是显然的

然后枚举用了几次逃课,再meet in the middle,枚举从开头逃了几节然后就能算结尾逃了几节

预处理一下逃了x节之后在第几个小时就可以O(1)算答案了,三层枚举总的是O(nk2)

然后处理出dx就dp,设dp[i][j]是到第i天为止用了j次逃课得到的最短时间

然后枚举i,这也是显然的

枚举一下j,为了更新dp[i][j]你需要枚举当前第i天用了多少次逃课

这样我们就枚举l做为今天逃课数,然后更新dp[i][j]即可。

这题其实长得蛮像新魔法药水

后面三题没做出来 QAQ很惭愧

还是自己太弱了。

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据