CF水题题解

Pre

本弱实在是太弱了,身边的大佬们切题如喝水,而我昨天A+B做了快一个小时。。。

写一下简要的题意和收获,暂时只打算改ABCD,也许能力强一点(根本不会发生的事)之后会改EF。

#Round 740

A

纯模拟

B

算出一个人需要反转几次才能赢,然后枚举他赢得次数。
因为每次赢都可以和一次输反转加两次break

C

二分答案,先二分计算出来进入每个山洞需要的最小体力。
然后在二分答案,优先选择最小体力最小的山洞进入。

D

貌似这题还行,大佬都说是水题。
D1 可以差分处理第一种+整除分块处理第二种(\(n \sqrt n\))
D2 比较巧妙不用这个点去刷新别人,而是对于每个点看他从谁转移过来,配合一个前缀和,枚举调和级数。(\(n ln n\))

\(\lfloor \frac{a}{b} \rfloor=c\)的数对,对于每一个\(c\),可以直接枚举\(b\)。
这样,最后一个 \(\lfloor \frac{a}{b} \rfloor !=c\)的\(a\)必定是 \((c+1)*b\)。
所以,直接把 \([c*b,(c+1)*b-1]\)的前缀和加到答案就行了。

整除分块变调和枚举。

#Round 741

A

假设模数是\(x\) ,答案就是 \(min(r-x,x-1)\)。
发现是两个一次函数取min,是个单峰且单调段都线性变化。
所以直接看峰点是否在范围内,否则直接把左/右端点当成x

B

看起来很唬人,然而不难。
如果个位中出现了1/4/6/8/9,那么直接输出就是合法方案。
否则,如果有一个位上面的数出现了两次或以上,我们可以11乘这个数。
如果都没判走,那么这个k<=4,直接状压就行了。

推性质带走合法状态从而枚举。

C

考场太困没想出来(菜)
够造一种合法方案,首先如果序列里面有0,那可以操作。

他在前半段,我们可以连上后半段输出两个相等的数(加前导0)
他在后半段,可以构造出两个数为二倍关系。

所以序列里全剩1了,这样也有很多种构造

直接输出两个全等的串(1~(n-1),2~n)。
或者构造(x*(x+2))也可以。

第二种就是先把和他一样长的一段0复制在后面,在加上他自己

111-> 111000 -> 111111

二进制下乘法的意义

D

太菜还不会做,太废还不想看题解。

上一篇:Linux安装CF-812AC usb网卡驱动


下一篇:为什么要进行股票研究