CFR556

CFR556 div1

CF1149A Prefix Sum Primes

code

CF1149B Navigation System

其实我感觉这个B有为了出题而出题的嫌疑

不会的看代码即可

CF1149C Tree Generator

题意:给一个长度为n的括号序列(无标号欧拉序),保证对应合法的有根树,q次交换某两个字符(依然合法),每次输出当前树的直径

请先思考后再展开

和O(1)LCA利用的欧拉序性质一样,$直径=\max_{1 \le l \le r \le 2(n-1)} d_l+d_r-2d_{t \in [l,r]}$,其中d为深度,同时也是前缀和

因此就是区间加,维护这个max,和线段树动态维护直径的CEOI2019某题类似

CF1149D Abandoning Roads

请先思考后再展开

只能欺骗自己说不会的point就是题目最难的point,觉得自己是只被切成两半的蚯蚓……

我的思路:根据MST那套理论,其实就是存在若干个用A连起来的联通块,找到1到p的最短路径,满足不会两次到达一个联通块

注意到最坏情况是从$联通块x \to y \to x$,因此记录上一个所在联通块后,会出现非法路径的最坏情况就是$x \to y \to z \to x$,即三条B,因此这时一定满足$[只在x里面走的距离]*A>3*B即距离 \ge 4,siz_x \ge 5$,只要不走回这种大联通块就行,用dij转移,复杂度就是$O(2^{n/5}*(n/4)*m*log)$(上个联通块大小<4的话不用记录)


其实不记录上一个特殊联通块问题也不大,$距离\ge 3,siz \ge 4$,$O(2^{n/4}*m*log)$

另外还有个我完全忘记的科技:只有两个边权,可以仿照noip切蚯蚓之类的,开两个队列来模拟一个堆,$O(2^{n/4}m)$

好像可以适当放大n来让强行让上面做法更优越

CF1149E

咕咕咕

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