Codeforces Edu R43

今天又又又又延时了!!这不道德!!

好菜啊只水了ABC三道不带脑子题……E最后结束的时候还没改对……

废话不多说了……

A. Minimum Binary Number

一个有趣的故事:我一开始把minimum看成maximum然后写了一个maximum版本的做法……

然而并没有啥用……

关于minimum,显然是

1.数位最少

2.只有最高位是1

那么我们的策略是把低位的1都向最高位移动并合并。

B. Lara Croft and the New Game

模拟+数数

并没有太大技巧,注意分两种情况,第二种的时候用除法直接锁定在哪一行(row)。

C. Nested Segments

转化一下问题,使得处理更简单一些

我们按照l_i为第一升序关键字,r_i为第二降序关键字排序,这时候就只需要判r_i \leq r_{i-1}就行了。

我们考虑答案是取了r_i序列的一个不降的部分,可知序列前面都是降的。这时候只需要判ii-1的关系即可。

D. Degree Set

不会呢,留坑吧

E. Well played!

贪心。有一个结论是2^a一定会乘到一个数上面去,不会分散开。

F. Minimal k-covering

看起来很难,yzy大佬刚了差不多1h都没刚动,我还是暂时咕咕咕吧。

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很惭愧

还是自己太弱了。