COMPFEST 14 - Preliminary
第二次和袁妹妹打的一场acm。感觉由于是10:35点开始，有点疲劳了，我自己状态不是很好，爬了。。。。。
真实的演员。
赛时只做对了7道，实际上可以做出10，11道以上（只是初赛嘛），有很多我现在看来很套路的题而当时根本没去看。
只说我做的吧。。
真不是复制的上次的开头/kk。
顺序是字典序。
D safe
意思是让你构造一个长度\(n\),满足能通过下述操作使得 \(a_i<a_{i+1}\) ，且 \(\sum a_i\) 最小，如果相同比较字典序。
操作是，设当前操作了这个位置 \(c\) 次，那么由 \(x\) 变成 \(2(x-2^c)\)。你需要保证任何时刻 \(x\) 为正。
首先写出操作 \(c\) 此后变成了啥,\(2^c(x-c)\)。
首先就能知道，事实上操作越多次，这个数会越大。
然后直接考虑最后的数列情况，如果我们选择了 \(x\) 我们初始的 \(a_x\) 就一定要最小的，也就是 \(2^c\mid\mid x\)，\(c\) 次操作和为 \(x\) 的。所以我们现在认为一个原始的 \(a\) 能到 \(c\times 2^{a-c},2\nmid c\)。这样每个数都只能被表示成一个原始的了。
然后你考虑我们选择的原始的数，一定是 \([1,k]\) 这样的区间，原因显然。
那第一问很简单，直接做是 \(O(\sqrt {v})\) 的。
第二问，事实上我们可以先按照 \(c\times 2^{a-c}\) 的位数分类。这样只会有 \(O(\sqrt v)\) 个类，然后找到现在这个类。
之后就是在一个类里面找第 \(k\) 个。经典二分看 \(\leq mid\)个数。
其次你会发现其实把 \(c\) 位数相同看到一起，还是只会被分成 \(\log\) 段，一段一段考虑就行。
大概就是比较 \(a\times 2^b,2\nmid a,b\geq n-20\) 这样的（因为 \(a\) 不会很大。）
所以直接做，复杂度2log。
E euclid
看完题解我发现自己是个shaber。
让你求 \(\sum_{x,y,z} f(x,y,z)\times g(x,y,z)\)。
\(f(x,y,z)\) 意思是让 \(x,y,z\) 联通所需要的边数。
\(g(x,y,z)=\omega(\gcd(a_x,a_y,a_z))\),\(\omega\) 是质因子个数。
我这个shaber竟然枚举了\(\gcd\) 然后莫反，真傻呀。
事实上我们考虑质因子对 \(a_x\) 这些的贡献。。。。。然后就只考虑质数的倍数就行，这样肯定是 \(\log_2\) 级别的。。
然后后面的是板子虚树了，建出倍数的虚树，dp就完了！
F safe
题意你有 \(n\) 行，每行一个连续段。你一次操作可以移动一个连续段，代价会或上移动的距离。
询问给定他要的最终代价，最多几个数能在一列上，操作互不影响。
首先移动 lowbit<lowbit(w) 的肯定不行。然后我们可以先瞎移动几次或出来 \(w\) 就完事了，剩下的只跟 \(lowbit\) 是啥有关了。
然后。。。直接看 \(\bmod 2^c\) 是啥，2log做完了，不知道能不能更优。
H safe
题意让你把一堆数黑白染色，只有颜色不同有限制，\((a_i+a_j)^2+a_ia_j\bmod 3\not =z\),\(z\) 是自己选的常量。
直接枚举黑白有\(\bmod 3\) 的情况，然后枚举 \(z\)，然后hall定理判断一下。。。。
具体说就是用\(\bmod 3\) 的能不能分别满足黑白，还有黑and白。
构造不难。完事了。
I keter。
woshishabi
题意，问满足如下条件的图的个数：
- 点数 \(n\),边数 \(2\times n-2\),边权 \([1,2\times n-2]\) 且互不相同。
- 存在一种对一颗已知的树的边赋权的方法，使得图上同时经过 \(x,y\) 的最小简单环和树上两点间距离相同。
- 允许重边，但不允许自环。
注意：最小环，和距离的定义，都是路径上的最大边权。。。。。。
就是瓶颈路嘛！
首先想想如果建出来最小生成树，会咋样？发现我们任意两个点的最小简单环的权值，必然 不等于最小生成树任意一条边的权值。
考虑一定是树边加上若干非树边，瓶颈一定是非树边。（不然割断）。
同时考虑这颗给定的树上，我们已经获得了 \(n-1\) 个互不相同的最小环的长度了，，并且只有 \(2n-2\) 条边，那也说明了，把最小生成树去掉，剩下的也是一棵树，这棵树的克鲁斯卡尔重构树，和给定树的一样。
我们再考虑考虑 合并两个点集发生了啥，我们现在合并 \(a,b\) 如果最小生成树的结构是 \(a\to c,c\to b\) 这样的，我们是不好统计的。
既然不好统计我们就得思考思考这东西合法吗？由于当前 \(a,b\) 和 \(c\) 不在一个点集中说明 \(w(a,c),w(b,c)\) 都要大于当前连的边，那如果最小生成树长这个样，我们得出 \(w(a,c),w(b,c)\) 都不大于当前练的边，矛盾了。很开心我不会算的不合法。
然后就很朴素了，合并两个点集就是找两条边。而限制只不过非mst的边最大，mst的边任意。
大概是由于非mst的边，已经有序，本着什么东西限制程度高我就先考虑什么，我们固定了 \(n-1\) 个非mst的边权， 每一次只插入 mst 的边，这样权值大概就是 \((2n-3)!!\)。连边方案是朴素的，这样 \(O(n)\) 做完了。
这个题我最开始没有看出来那部分是不合法的，然后完全没头绪。后来双阶乘那块一直以为是egf就很伤心的Wa on 8 了。
K 并查集 euclid
大概操作是，单点修改，单点询问，全局如下修改：把 \([l,r]\) 之间的数改成 \(l-1\),或 \(r+1\)。
保证 \(2\nmid r-l\)。
这个全局操作是个内鬼，记录势能是全局不同的数，就知道了这个全局操作很吃势能。
现在我们就用并查集维护每个点所在点。然后用线段树，set维护值域。
然后全局操作就是把一些 并查集合并，单点修改就是把一个点改集合。
这个单点改看起来不好搞，但你考虑实际上新建一个点就可以了，原先的就不要了。
然后\(n\log n\) 做完了！。当时忘记了一共可能有 \(n+2q\) 个点，并查集开小了，gg.
j safe（dbq我不会数字典序）
好像是模拟赛原题？不记得了。
大概就是你要遍历一颗带权树，然后你可以选择一次瞬移，问最少走多少次。
很经典呀，大概不能瞬移遍历一棵树就最多少遍历一条链。
如果能瞬移一次，那就是少遍历两条边不交的链，当然根据样例，边不交的链还是不够的。
具体来说如果这两条链点不交，我们还可以少遍历一条边，如果点相交，就只是少遍历两条链。
第一种很简单枚举从那条边切开的，然后找直径就好。
第二种枚举交点，找前4个dis，然后加起来就好。
重量级的来力！
L
可能是我太菜，别的题我都是有思路的，但这个 \(L\)
一点都没想到呀，给他留到了最后，也说明是最难的
我当时问了yhw一句，这个操作啥意思，yhw答曰：“好像就是前缀和”，然后又云：“好像不太行”，遂去想只能再负数进行操作，无功而返。
就是前缀和！！！！！为啥yhw是神仙.svg。
前缀和一做，欸，改仨数是是吧，哈哈没想到吧！看我半径为0.5旋转两个数的绿宝石水花！！(swap)
然后，然后最后条件是，单增，，，然后，，，典中典逆序对。。。。。
总结，yhw是神仙、能想出差分，想不到前缀和的我太拉、不能再当演员了。