CF补题计划菜鸡的紫名梦

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

2021/7/9/23:30

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

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

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

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

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

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

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

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版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44146257/article/details/103091645

• E：dp&&bitmask&&模拟

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版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43562213/article/details/103168350

• F:bitmask
• H:fft

BC的代码

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

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

problem A

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

problem B

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

problem C

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

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）

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

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

problem A Meximization

• tag：greedy
• 由于当前$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
• 这里在$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

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

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

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

problem A $PrisonBreak$

• tag：观察

problem B $RestoreModulo$

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

problem C $BasicDiplomacy$

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

problem D $Playlist$

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

problem E $SkylinePhoto$

• tag： data structures dp

problem F $UsefulEdges$

• tag： brute force graphs shortest paths