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 R42 细节决定Rating

提示:题解正文前超长啰嗦部分

我活到现在,还没这么惨过,NOIp都没有。

比赛开始4min的时候,切掉A

 

 

 

嗯没有什么毛病

最后

 

 

用实力告诉你什么叫没带脑子比赛


开始切B

下面两段程序只有这里不一样

为啥第二个会WA?????


C 35min找错

尝试cout某些变量,发现去掉cout和不去掉,结果不一样

你猜哪错了?

35min找这一个字母 我怕不是学文化课学傻了写出i=i来??

然后 忘记判前导零 WA一发

最后,最后还fst了!!

10^9是10位数,我***……

我持盾,持盾。。


D 手速打完

seq[100010] -> WA 一发

改对,交上,Ac。

最后还是fst了!!!!

我***……

我持盾,持盾。。


然后我们愉悦的比赛就结束了。

我都不知道我的脑子飞哪去了……找到和我说一声‘

细节决定Rating啊!

凉凉。


我们还是来扯题解吧

A. Equator

这题巨没意思,加一遍扫一遍完事

注意sum/2还要上取整,也就是+sum%2

B. Students in Railway Carriage

我们貌似其实好像大概一定可以说明贪心是对的

这样,如果有一些空段,它们\geq 2且是一个偶数,

那你无论什么顺序安排反正都一样,填满的格子不能变多。(二元组证一下……)

对于奇数那些,……呃, \geq 3的拆成一段偶数空位和一个空位这样两个空段

这就变成了若干由一个空位,2N个空位组成的空段。

对于一个的那些你怎么放也是固定结果的。

(注意其实\geq 3的,拆出的一个空位,你放黑或白都可以,并不受后面偶数段的影响)

然后你每次挑大的放进那一个就行。挨着放就行,反正次序安排与解的优劣无关

对于一个B这样好像很啰嗦了……

C. Make a Square

解法1,枚举最终状态,每次判断可行并更新答案

解法2,从0到9枚举步数,DFS出终态并判断合法与否

特别注意判终态不含前导零(终态不含即可,非终态?含也行。为什么呢?)

D. Merge Equals

从左向右扫一遍然后开map记录位置,找到一个二元组,递归地消除即可。

特别注意long long

E. Byteland, Berland and Disputed Cities

交了几发,WA了。

所以思路是错的,并不会,留坑了。

F. Simple Cycles Edges

并没来得及看,留坑了。

G. Visible Black Areas

瞅了一眼图好像是个计算几何?并没细看题面,咕咕咕。

Codeforces Edu R40

手残比赛系列 +3 +3 +3 +3 +3……

话不多说进入正题

A. Diagonal Walking

瞎dp一波即可 贪心也对(当时没仔细想直接开始敲dp)

B. String Typing

枚举终点然后判断能不能复制即可。

记得倒序,要不会被aaaaaaaaa这种卡掉

C. Matrix Walk

尝试能不能通过上下的移动确定一行的宽度y

然后fixed宽度,把不合法的上下移动,左右移动判掉即可

特判不动的情况和没有上下移动的情况

x轴直接设置10^9

D. Fight Against Traffic

两遍SPFA然后枚举左右端点判定距离即可

注意有两种情况,还有就是ans要除2

E. Water Taps

把式子移一下就会发现是贪心

还没写出来,写出来再说

F. Runner’s Problem

时间不够了,没看题目

G. Castle Defense

先差分一遍把初始的\rm defense指数算出来

然后二分最小值,用贪心的方法判定

区间影响那就差分一下,假设判定的时候当前不足,还要让i+1加上补充的数目,i+2 \times \rm Range -1减去数目,然后从左到右扫就行

H. Path Counting

留坑

I. Yet Another String Matching Problem

留坑

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

还是自己太弱了。