CF补题计划菜鸡的紫名梦

计划菜鸡的紫名梦"/>

CF补题计划菜鸡的紫名梦

Educational Codeforces Round 75 (Rated for Div. 2)

2021/7/10/ 14:30-16:30

performance: 1600
这场太颓废了，ab切的慢，之后不想写c。
其实d已经想到二分了，但是写check时，还没有想出来。

• A：accheck ans
• B：ac 分析本质，之后check ans
• C：ac 分析本质，队列维护
• D：二分答案&&check里排序（观察和本质分析，发现问题的本质&&贪心
• E1：2300
• E2：贪心&&优先队列维护&&排序2400
• F：组合数学 || fft2500

Codeforces Round #596 (Div. 2, based on Technocup 2020 Elimination Round 2)

2021/7/9/23:30

perfomance:1740
这场数论题应该出的。。。。。。。。。出了performance应该到1900
A的特判wa了一发，还是不够稳健
这题数论题想歪了，其实由于数据的a的范围很小，（所以可以把它的对于k的逆先存起来，复杂度是质因分解的复杂度）
而且一个数的质因数很小（在极端条件下， 2 ∗ 3 ∗ 5 ∗ 7 ∗ 11 ∗ 13 ∗ 17 = 510510 2*3*5*7*11*13*17=510510 2∗3∗5∗7∗11∗13∗17=510510，总共7个。小于10个，类似于阶乘）
k最大到100，n最大 1 0 5 10^5 105. 时间复杂度 O （ n ∗ k ∗ l o g N ） O（n*k*logN） O（n∗k∗logN）

• A：ac签到（简单分类讨论，有个特判要注意！！）
• B1&&B2：acvis记录下跑双指针即可。
• C：ac枚举&&二进制&&数学推导 代码

1. 类似于求一个数的二进制表达，已经是最优。不够时，看是否可以补充。
2. 枚举答案 i i i
3. 对公式进行化简 n − i ∗ p n - i*p n−i∗p,问题转换成求它的二进制表达。此时这个式子如果小于0，那么肯定找不到解。
4. 之后假如当前 x = n − i ∗ p x = n - i*p x=n−i∗p的 x x x的二进制位数小于枚举的答案，那么我们可以找除了第一位以外的位，通过分解来增加现在的二进制位数（题目说明每个2的倍数可以使用多次）。

• d：质因分解&&水题。（没做出来赛时。。。。

t神的代码
我的tle代码。。。。

• E：dp 2200
• F：分治&&贪心 2500
  div1剩下的两题

---

Codeforces Round #597 (Div. 2)

2:00:01才过d，原因竟是把加号写成*号。。。。。
加上d的performance1800。没加上是1550
这场的c和d都没对样例，直接交导致wa了几发。以后还是交一下。（因为测试最多损失10score，wa1发就损失50score
B的石头剪刀布，看错题了。。。。
C一开始去想组合了。。。没想dp。。。。
D最后才想到连超级汇点。

• A：ac不容易的签到（其实判是否互质即可）

官网的证明（嗯qs，这个式子太常用了。。。

• B：ac石头剪刀布，写个循环判断并记录答案（先是看必胜态 <之后是平局>，可以不看。。。）
• C：ac取出连续一段算贡献，这里可以dp预处理（细心可以发现其实是fib）
• D：ac最小生成树，把电站看成一个超级汇点，之后连边跑最小生成树即可。
• E：概率dp&&最短路
• F：bitmasks&&combination&&dp

---

Codeforces Round #599 (Div. 2)

2021/7/5

performance:1720手速回到了1720
这里的

• A: ac 倒序遍历一遍取一个min即可。
• B1: ac 交换两个数
• B2:ac找到规律后构造即可，根据题目的提示去构造即可。
• C: ac对于题目的解释，（复习CRT之后再来）
• D：缩点&&（dfs||bfs） 并查集写法的证明

给一个权值若不为1则为0的树，求最小生成树。
看似是最小生成树。可以换种思路是，将0边的联通块缩点，最后的结果就是联通块的数量 -1。
————————————————
版权声明：本文为CSDN博主「胡十八」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：

• E：dp&&bitmask&&模拟

Educational Codeforces Round 76 (Rated for Div. 2)

2021/7/5

performance1550
没切出d有点伤，e的dp比较好写，但是发现问题的本质后，代码很短。

• A: ac 签到+数学小技巧
• B：ac草稿纸上演算，按照条件输出
• C：ac发现本质，之后min输出
• D: 排序 加逆序处理时间max。之后check
• E: LIS&&染色 LIS做法 dp做法

反过来想,
考虑每个人最多保留多少个,
如果将三个人留下来的数依次排开,那么一定是递增的.
那么对三个人拼起来的序列求一个LIS就是最大保留个数了!
需要注意的点:
先对三个人自己的数排序,然后再拼起来.
思路2：
dp首先可以理解到，最后分配的情况肯定是第1个人解决前k个任务，第2个人解决k+1到k2的任务，第3个人解决k2+1到n的任务。(0<=k<=k2<=n),既对问题i,j来说，若i<j,则i对应解决的人编号<=j对应解决的人编号，所以不妨对n个任务所交给的人进行dp维护。dp[i][k]代表把第i个问题给予编号k的人所对应的最小转移次数
————————————————
版权声明：本文为CSDN博主「Bigspot」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：

• F:bitmask
• H:fft

---

Codeforces Round #628 (Div. 2)

反思

1500，本场500，750，1250，1750
B vector开小了1wa有点可惜。
ｃ一开始时想边的度ｄｅｇ，浪费了３０ｍｉｎ。
Ｄ的数学推导，还有待提高。

题意：

A EhAb AnD gCd
简单数学构造问题

B CopyCopyCopyCopyCopy
sort

C Ehab and Path-etic MEXs
根据顶点的度deg来构造

D Ehab the Xorcist
数学异或的推导&&分类讨论

E Ehab’s REAL Number Theory Problem 2600
F Ehab’s Last Theorem 2500
ABCD题解

---

Global 7

题解待补充

---

ED84

题解待补充

---

Codeforces Round #637 (Div. 2) - Thanks, Ivan Belonogov!

反思：

performance：1650 本场500，1000，1500，1750
最近一直在颓废，写完c就，溜了，这场以后，立下一个flag：
写完c后，一直把D刚出来，不做懒狗。（切出D加的分更多）

A Nastya and Rice	500

求一下两个区间是否会有交集就好

B Nastya and Door	1000

维护一个滑动窗口，先把前k个预处理，之后滑动就好。

C Nastya and Strange Generator	1500

本题算是阅读理解。由于每次是count最多的计算，所以维护下每个位置的count。
根据答案去推导，假如可以成功，那么就可以得到答案。

D Nastya and Scoreboard	1750

本题是一个经典的背包模型，可以把10种状态预处理出来，抽象成权值。
之后答案是要输出字典序最大的答案，那么我们从后往前dp即可。

E Nastya and Unexpected Guest	graphs implementation shortest paths 2400

F Nastya and Time Machine	constructive algorithms dfs and similar graphs 2600

jiangly的学习代码

---

Codeforces Round #641 (Div. 2)

BC的代码

反思（2021-2-1）

这场被我水过去了（其实挺难的，最近遇到数学直接被吓傻了），当作练习做了。
A Orac and Factors 、 500
math&&观察
B Orac and Models \ 1000
数学筛法的应用
C Orac and LCM\ 1500
唯一分解 或者 观察+gcd
D Orac and Medians\ 2250
constructive algorithms greedy
E Orac and Game of Life\ 2250
data structures graphs implementation math shortest path
F Slime and Sequences (Easy Version\ 3000
dp fft math

---

Codeforces Round #645 (Div. 2)

反思

分数大概1610左右，还是慢了。
1.对于C想歪了，应该大胆猜结论的。c的题解，可以看这位大佬的，学到了，找规律，比我的暴力强多了

可以由一般的观察去，推导特殊的观察。很像数学归纳法。

2. 对于D就只是前缀和，加贪心。（主要是不敢贪心啊啊）

Codeforces Round #645 (Div. 2)
A Park Lighting	500
根据题目大胆的才结论	向上取整
B Maria Breaks the Self-isolation	750
根据题意sort后O(n)check	sort
C Celex Update	1500
先观察，画图后，可以发现答案在一个范围内，最后思考怎么O(1)表达范围即可。数学等差数列公式	math
D The Best Vacation	1500
先前缀和预处理，之后贪心的找	pre \ 贪心 \ 双指针
E Are You Fired?	2000
constructive algorithms data structures greedy implementation 2400
F Tasty Cookie	2500
binary search constructive algorithms greedy implementation 2700

---

Educational Codeforces Round 88 (Rated for Div. 2)

反思（2021-1-31）

1. performance：1750左右。（这次的c有点毒瘤，假如中途放弃了分会更低）
2. 努力切d，最后还是调到结束。大体的方向没错，转移方程也写对了。主要是一些小细节（简单dp ）。（ps：切出后，加分上限会到1900）
3. 赛后看了下E，好像不是很难（组合问题）。qwq（ps：切出DE后，加分上限会到2080）

Educational Codeforces Round 88 (Rated for Div. 2)
A Berland Poker	500
分类讨论一下	向上取整
B New Theatre Square	750
分析下那种方案更划算（学习下他人的代码）	暴力
C Mixing Water	1500
数学（纯数学做的话，注意一下就好了）或者二分	二分 \ math
D Yet Another Yet Another Task	1700
easy dp	dp
E Modular Stability	2000
简单组合问题，过的人挺多的	combination
F RC Kaboom Show	2900
binary search brute force data structures geometry math

大佬的C的学习笔记
d题题解

---

Codeforces Round #646 (Div. 2)

看大佬题解，时，突然看到个小姐姐，%%%%%%%，好像是oier%%%%%%

反思

performance : 1650

这场也被我wa过去了，手速abc最多感觉到1700，要上分还是要4题（4题可以到1900）
A Odd Selection 500
math / numeration (数据小，可以直接枚举， 出现合法情况就输出即可)
B Subsequence Hate 1000
pre / suf（我是用了前缀和直接暴力，之后O(n)的遍历去找最小的答案即可）
C Game On Leaves 1500
简单博弈， 可以画几个必胜态，之后就可以发现规律。
D Guess The Maximums 2000
binary search implementation interactive math *2100
E Tree Shuffling 2000
简单树上greedy ， dp
F Rotating Substrings 3000
dp strings *2600

e题题解

---

Codeforces Round #649 (Div. 2)

反思（退步了，2021-2-3）

perfomance：1400

没看分数，一开始A读错题，白给1h。振作点，rushrush。
A XXXXX750
math，bruteforces（想清楚就好了，不能图快）
B Most socially-distanced subsequence1000
observation,greedy(观察可以发现当中间的数与两边的绝对值，小于等于两边的绝对值，那么中间的数肯定可以删去，可以用两个指针记录一下，就可以了)
C Ehab and Prefix MEXs1500
construction， simulate，observation（暴力即可，主要是被A搞了c态）
D Ehab’s Last Corollary2000
constructive algorithms dfs and similar graphs greedy implementation trees *2100
E X-OR2500
bitmasks constructive algorithms divide and conquer interactive probabilities

696 待补充

---

Educational Codeforces Round 103 (Rated for Div. 2)

反思：

分数大概1620;(3题最多就走这么远了，4题才是王道)

1. 这场A的2A，有点可惜。不过之后不注重罚时，反而顺利切出DB。
2. 最后的C没有调出来，有点可惜。赛后看了大哥的代码，还是发现鄙人的代码比较冗杂。

Educational Codeforces Round 103	(Rated for Div. 2)
A K-divisible Sum	500
注意好分类讨论，不然很容易wa	math \ dove nest
B Inflation	1000
首先把浮点数运算，转换为int。中间有一个地方注意除法方式	向上取整\扩大范围
C Longest Simple Cycle	1500
从后往前枚举答案，对于一个圈要考虑是否围起来	greedy \ bruteforce \ numeration
D Journey	1500
观察可以发现一个点可以到向前走多个且走回来，当且仅当出现LRLR（RLRLR），那么预处理一下每个位置 i i i 最多向前走多少个，向后走多少个就可以了。	pre \ suf
E Pattern Matching
bitmasks data structures dfs and similar graphs implementation strings
F Lanterns
data structures dp
G Minimum Difference
data structures two pointers

---

Codeforces Round #702 (Div. 3)

这场感觉实际难度，只有div4.
performance：1620

problem A

• 讲了一个密集的概念dense。（学到了）
• tag： greedy
• 解法：每次只要贪心地插入二倍即可。
  

problem B

• tag： bruteforces
• 解法：写个while最多不超过两次，就可以把所有余数都三等分。

problem C

• tag：enumeration
• 解法：给出n ，要使得 a 3 + b 3 = n a^3+b^3=n a3+b3=n那么只要枚举a，之后查看是否有 n − a 3 n-a^3 n−a3存在，且是cube即可。（可以用一个set预处理出所有的 a 3 a^3 a3, 方便后面的查找）

problem D

• dreammoon 大佬说是笛卡尔树，学到了（赛时直接暴力了）这里附上一个O（n）的建立方法 传送门
• tag: bruteforce、 divide and conquer
• 解法：直接暴力查找即可，每次查找一个区间。

problem E

• tag：greedy，prefix and suffix or binary search
• 解法：先排序，一个人能获胜，那么它后面的人肯定可以获胜。（有这个结论那么就要找到tokens刚好可以获胜的那个人）

problem F

• 我写歪了，不过ac了。主要还是要学习dreammoon的思路，dreammooon的思路好简单啊啊啊。

problem G

• 贪心和数学分析，主要是循环节的分析不是很到位，导致被卡住了。（差点ak）

---

Codeforces Round #704 (Div. 2)

反思

• 这场的D一个case写在了后面导致被hack X，挺可惜的。。。
• c一开始看以为是出栈序列，其实是想复杂了
• 以后写多case，应该每个case检查一下的。不重不漏最关键

放一个拖出去打死的代码，xs
performance：1620
（D没写歪的：performance：1900）

problem A

• tag:向上取整

problem B

• tag：贪心

problem C

• tag： 前缀和

problem D

• tag：construction

problem E

• tag: check和暴力和construction
• 题解地址

---

Codeforces Round #708 (Div. 2)

performance:1400
仔细想了下，既然是紫名的梦想，那么就每场都写题解吧。（顺便督促自己补题）

本场的e1之前有过类似的，可惜没有a。
本场挺有教育意义的，通过c1，让我知道分析问题，可以从简单的着手，之后再考虑难的即可。

problem A Meximization

• tag：greedy
• 由于当前 M E X MEX MEX只会跟前面的元素有关，那么贪心的前面每个元素摆一个，后面随意即可。

problem B M-arrays

• tag：greedy, math
• 本题要想到转换为mod，以mod来分组即可。（因为mod很小）

problem C1 k-LCM (easy version)

• tag：greedy，construction
• 简单构造，分类讨论一下即可。

problem C2 k-LCM (hard version)

• tag：greedy， construction
• 这里在 c 1 c1 c1的条件下，构造即可。

problem D Genius

• tag：dp

problem E1 Square-free division (easy version)

• tag：math，unique decomposition theorem
• 本题算是原题了，就20场之前，出过一道一摸一样的。
• 平方数，可以用mod2来划分。
• 对于一个集合的hash，可以类比字符hash，为了避免hash值冲突，可以建立两个hash（当然直接暴力即可）

problem E2 Square-free division (hard version)

• tag：dp

Educational Codeforces Round 106 (Rated for Div. 2)

perfomance: 1500.
这场表现的不好，d没切出来。菜了。。。。。。

---

Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round)

performance：1600 菜了，
反思：（wawa战士了）

• b应该想清楚再码的，中间漏了一种情况导致wa了几发。qwqqwq。
• c暴力莽就完事了。

problem A P r i s o n B r e a k Prison Break PrisonBreak

• tag：观察

problem B R e s t o r e M o d u l o Restore Modulo RestoreModulo

• tag：数学公式推导，分类讨论（这里做的时候细心一点，不然很容易wa）

problem C B a s i c D i p l o m a c y Basic Diplomacy BasicDiplomacy

• tag：simulation,greedy
• 先把一天中的只有一次的预处理出来即可，后面暴力模拟即可。

problem D P l a y l i s t Playlist Playlist

• tag：link
• 一道链表的操作题，因为操作数可能很多，直接遍历循环会超时。
• 这里先抽出所有可能会被影响的点，加入队列中操作即可。

problem E S k y l i n e P h o t o Skyline Photo SkylinePhoto

• tag： data structures dp

problem F U s e f u l E d g e s Useful Edges UsefulEdges

• tag： brute force graphs shortest paths