CFR630

CFR630 div2

全场rk17它不香吗,尽管是中国buff

其实说实话前面10分钟都是在慢慢的配置环境,然后在没有看榜之前,一直都是觉得自己就是挺慢的


当时过了前面6题后,感觉G这种区间题,枚举中间两个点的话,左右端点的延伸长度是平等所以没法优化的,然后刚好qq上挺多东西看的就聊了起来

然后在依然没有对题目认真思考的时候(基本在试图理解别人是怎么做的),看到群上一句其实上面思路再稍微想想就能得到的话,就会做了

验证了打小号时人会非常放松的真理,有好有坏吧

CF1332A Exercising Walk

code

CF1332B Composite Coloring

请先思考后再展开

因为给出的时候数都是合数,所以他们的最小质因子一定在根号以内,而根号以内的素数恰好11个

code

CF1332C K-Complete Word

code

CF1332D Walk on Matrix

请先思考后再展开

当时想要找到他的算法的实际意义是什么,然后没找出来

随便画了个2×3刚好就对了,大致思路就是引导他去选择$2^{17}$,而答案里面一定没有$2^{17}$

code

CF1332E Height All the Same

简单转化后的题意:你要给n*m个格子染0和1,但0和1的个数都是奇数就非法

请先思考后再展开

多项式的奇数项?中国人?八成单位根反演,待我细细推推式子

总方案数为$A=R-L+1,A^{nm}$,在nm是偶数时会有都是奇数的情况,即$\sum_{i=0}^{\infty} [i\%2=1]C_{nm}^i (\frac{A}{2})^i (\frac{A+1}{2})^{nm-i}$

code

CF1332F Independent Set

请先思考后再展开

一开始还感觉这题挺难的,然后就是发现就是按部就班

就你看起来考虑边导出子图,再考虑若干棵树各自的独立集,肯定不如考虑独立集再考虑对应合法的边导出子图数量好做

除了独立集中每个点旁边至少一条边的限制外,每条边是否有出现的可能是独立的,所以我们枚举独立集中非法部分做容斥,那么有选择权利的边就是不能够两端都在独立集中,且两个端点都不在非法部分中。

将每个点是否在独立集和独立集的非法自己中用两个二进制位表示,做个简单的线性树形dp即可,code

CF1332G No Monotone Triples

题意:给出一个序列,q次询问区间,找到区间中任意一个最长的一个子序列,满足该子序列没有一个更小的子序列是单调的,$n,q \le 2e5$

请先思考后再展开

画画图发现长度不超过4,然后长度为3的可以枚举中间点,向左右各找第一个更小或更大的(即有效子序列只有n个),然后输出的话我比较喜欢记录$ans_i=左端点 \ge i的区间中最小的右端点$,这样只要询问$ans_l \ge r$即可判断,输出方案求区间最小、大值即可。

比较棘手的是4,正如上面所说,枚举中间两个时,两边延伸不好处理,那其实只剩一种办法了:枚举两边的端点

具体的,考虑每个点为左端点去找最小的右端点,那合法的条件明显是$min(a_{l \sim r})<a_l,a_r<max(a_{l \sim r})$

做法很多,我的想法是,注意到对于l而言合法的r是一段后缀(记为rpos),对r而言合法的l是一段前缀(记为lpos),那两人能组合就是$l \le lpos_r且rpos_l \le r$。这很容易实现,我是考虑记一个set表示当前能用的右端点,然后从后往前枚举左端点并加入合法右端点,对当前左端点而言第一个合法的右端点可以set上二分找到

实现时,我是直接把一个二分复制了6次求出lpos、rpos、左右第一个最小;$O(nlogn)$,常数应该很容易优化得更小,code

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/7ced7f1f.html
转载请注明出处,谢谢!