Codeforces #677 Div.3 七题题解

A | B | C

过于傻逼。放个代码,估计连代码都没人看(摊手)

D | Districts Connection

是个构造题。

不同团块内部不能连,判断是否能构造生成树 (MST) 并输出方案。

考虑最经典的树——菊花图。我们强行选择第一个团块第一个点。让它和其他不同团块的所有点都连一条边。

这样只有一号团块没在生成树里。我们拿出二号团块的第一个点把一号团块除第一个点都连一遍。OK

所以团块数 \leqslant 2 即可。不然无解。

E | Two Round Dances

经典圆排列裸题。这里要分成等份的两部分。

让原题的输入是 N ,我们记 n \xlongequal{\mathrm{def}} \frac{N}{2}

我们就直接拿出圆排列公式:

Q_{n}^{r}=\frac{A_{n}^{r}}{r}=\frac{n!}{r\cdot \left( n-r \right) !}

证明就无所谓了,百度百科就有(直球),或者 Polya 直接推。

代公式 ,OK。

F | Zero Remainder Sum

总的来说这玩意类似一个背包。

一开始被那个 \lfloor \frac{m}{2} \rfloor 搞到怀疑人生。一直在找这条件有什么结论。

不过显然没有(摊手)其实你任给一个 lim 这题都能做。

设计状态 dp[i=当前行数][j=已选个数][k=当前行选 j 个且 mod K 余数为 k]

然后可以背包 – like 地转移。

然后最后把每行看成一个整体继续背包。完了。复杂度达到了惊人的 \mathcal{O}(n^4)

G | Reducing Delivery Cost

先对全图跑最短路, \mathcal{O}(n^2 \log n)

然后枚举边,把边权设为 0 之后统计答案。

总复杂度 \mathcal{O}(n^2 \log n)

我跑的就尼玛很慢,估计是 STL 的问题(大嘘)。

 

Codeforces #676 Div.2 五题题解

A XORwice

答案是 a \oplus b 。证明:显然。

B Putting Bricks in the Wall

由于只能左右上下动,结果就是限定移动的砖块只有 (1,2) \quad (2,1) \quad (n,n-1) \quad (n-1, n)

然后就 if 一下分情况讨论就可以了。代码如下:

C Palindromifier

是这样构造的:

然后就没了。代码:

D Hexagons

首先可以贪心地证明一定是只选择两个方向走最优。

选的话一共 12 种组合,挨个判断一下,然后更新答案。

粉兔の怒:

 

 

 

 

 

 

 

 

代码:

E

还没补,咕着先。

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 R473

我这个代码能力下降到\rm{-INF}

并查集板子打了15分钟 还有谁??

气死了

算了赶紧写完赶紧睡觉

A. Mahmoud and Ehab and the even-odd game(真长)

就这题!!!卡了我五分钟!!我觉得它长的像SG,是它的错还是我的?!

一定注意a \leq n!!

然后你就会发现这游戏最多就一轮

B. Mahmoud and Ehab and the message(这个更长?)

然后并查集板子+map……能这个点打Cf的都能看出来也不说了……

C. Mahmoud and Ehab and the wrong algorithm(哇,还是这么长)

送分(ming)构造题

两问分别长这样

注意第一问只有n \geq 5才有解……原因是层数和两个点的解的限制(也就是说第二层最少3个点然后第三层必须有两个点及以上((一个点的话那个算法也是正确的)))

D. Mahmoud and Ehab and another array construction task(最长!)

这题,扫一下然后质因数分解

如果分解有重那么立即断开,前面的原样输出,后面的贪心地选一个质数输出

注意特判

E. Mahmoud and Ehab and the xor-MST(哈!变短了吧!)

我们考虑……有什么好考虑的。。。

那就……从高位来考虑?

当前考虑的,要求mst的点集的所有点权,在目前位上, 必然是n_1 \text{ — } n_x这一部分是0,然后n_{x+1} \text{ — } n_{last}1,那么点 x+1 \text{ — } last之间独立连边,1 \text{ — } x之间独立连边,这么做,可以保证对答案贡献都是0,是最优的。

·

但是如果当前确实有一个满足上述条件的x存在的话,

(其实也就是现在考虑的点集的最大点权的点,点权模掉2^{w-1}大于等于2^w,其中w是当前考虑的位数)

(也就是这一位上有1的出现,所以点被划成了这一位是0 \; , \; 1两个子点集)

那么还要把左右两个点集联通。先加上这样的代价 :2^w

·

我们其实并不关心这两个点集是怎么内部联通的,因为这个可以递归求解。把两个点集的点权模掉2^w之后就成为子问题了,对吧?

但是0集那个子问题是可以预处理的,要不然会T。

f[i]表示从02^i-1的贡献和。怎么转移?这个其实就是……你把它按照上面我说的拆一下点集就好了。然后方程在这儿:f[i]=2*f[i-1]+(1LL<<w-1)这个不难理解吧……

我希望我这题说明白了.

(我怕我long long的位运算出锅于是打了快速幂……)

F. Mahmoud and Ehab and yet another xor task

留坑

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 R470 (Based on VKcup R1)

和dkw组队 敲开心!

明天早自习请假了但是还要七点半起床 好痛苦QAQ

大概上午要睡过去

A. Protect Sheep

送分(ming)构造题(?)

把羊四周全围上狗就行

别像我一样没判羊挨着羊的情况然后连WA两发QAQ

B. Primal Sport

留坑

C. Producing Snow

对于每个雪堆二分哪一天最早化到负数

对温度做个前缀和,每次二分,假设cac天化到负数,当前是第i天

差分答案,化的=温度的区间,也就是i~cac-1差分一下,最后可以得知每天化了多少雪

加上化的小于温度的那一天,这个单独统计

最后加起来就ok

D. Perfect Security

一颗Trie树题,挺好玩的

带删除Trie树,每个结点记录有多少个数在这上面

递归删除并且贪心就行了

如果还不明白:

尽量让密钥和文本不匹配的那几位在低位上,这样才能字典序小,

也就是把数看成一个二进制字符串,带权匹配。

对于询问Trie树,如果能走同0或同1的当然好,那就贪心的走就是了,递归回来删除

E. Picking Strings

留坑

Codeforces R469

临时改时间了结果我失了智打了后半场……rk2700全程被碾压

A. Left-handers, Right-handers and Ambidexters

一道略微简单的题

答案讨论下左右撇子哪个多就行,不够就Ambidexters凑,Ambidexters还有剩余就一边分一个

B. Intercepted Message

贪心.两边取,相等就消掉,不相等继续取