Tony102's Blog - CodeChef 比赛
type: channel
link: https://tony102.com/index.php/tag/CodeChef-%E6%AF%94%E8%B5%9B/
items: Contest: CodeChef STARTERS 17 (Div.3)

Contest: CodeChef STARTERS 17 (Div.3)
type: item
date: 2021-11-18T01:58:00+08:00
description: 因为我太菜了，没打过 CodeChef，所以只能打 Div.3一场比赛 naive 所有题。A: Chef on VacationChef on Vacation水题，不想解释B: New PieceNew Piece水题，不想解释C: GCD of Prefixes随便构造。比如说，假如现在要推 $a_2$，那么 $a_1 = k_1b_2, a_2 = k_2,b_2$，那么只需要使 $k_2 = k_1 - 1$ 再乘上 $b_2$ 就行了。这样可能只有青铜，实际上直接输出 $b_i$ 就行了，判断是否合法即可。D: Binary Inversionnaive 了，随意贪心。开始贪心的是字典序，然后发现按照 $0$ 的个数降序排就行了。那个时候才 $40$ min 的样子（毕竟我 WA 了一发然后写了一个暴力）。之后呢？在打摆，发现拍一直没拍出问题，但是交上去一直 WA。然后我开始怀疑 Windows 对拍有问题，还搞到我自己服务器上拍（巨快无比，一秒钟拍了300组）。一直颓颓颓颓到结束才发现没开 long longE: String Game也属于赛后随便看看就会了，但是因为在打摆一直没想这个题（逃。很容易发现，最后只跟操作轮数的奇偶性相关，当然，如果 $0$ 或 $1$ 有一个没有，那当然就是 Alice 赢了。否则，每个人都会删当前局面可以减少相邻的 $01$ 的那个数删，则至少需要 $ cnt_0 + cnt_1 - 2 \times \min(cnt_0, cnt_1)$ 轮，直接判断奇偶性即可。F: Partion It睡了，早上再落实。upd 20211118:把一个质数和自己在 $[1,n]$ 中的倍数放在一个集合，输出的时候注意一下两个集合大小和 $k$ 的关系，多退少补。特别注意 $1$，可以把它当做一个“边角料”来用。