10.22-10.23

A.异或和

CF1261F
做过类似的题的话，\(O(n^2\log^2v\log(n^2\log^2v))\) 应该算是暴力分了。
显然这过不了，不然就不是 *3100 了。
主要的瓶颈在于异或完后产生了大量的线段，而且里面大多数是没用的。
于是赛时写出了一个绝唐的优化

点击查看代码

for (int i = 0;i < seg[0].size();i++){LL l0  = seg[0][i].fr,r0 = seg[0][i].se;int k1 = __lg(r0-l0+1);for (int j = 0;j < seg[1].size();j++){LL l1  = seg[1][j].fr,r1 = seg[1][j].se;int k2 = __lg(r1-l1+1);if (k1 > k2){LL tmp = (l1>>k1)<<k1;if (tmp) ve.pb({l0^tmp,r0^tmp});else if(!vis1[i]) ve.pb({l0,r0}),vis1[i] = 1;}else{LL tmp = (l0>>k2)<<k2;if (tmp) ve.pb({l1^tmp,r1^tmp});else if(!vis2[j]) ve.pb({l1,r1}),vis2[j] = 1;}}}

显然大家注意到了如果两条线段长度不相等的话，我们可以把短的那条线段的补成长的。
这个玩意放到线段树上看就是短的线段的与长的线段位于同一深度的祖先和长的线段进行异或。
定义一个节点被标记即其是 \(n_{a}\log V\) 个区间中的一个，将所有节点分为三类：

1. 其自身被标记
2. 其自身未被标记且其子树内存在节点被标记
3. 其子树内（包括自身）无节点被标记

类似地，对于 \(n_{b}\log V\) 个区间也可以得到节点类型，那么也就可以看作 \(n_{a}\log V\) 个区间中1类节点和 \(n_{b}\log V\) 个区间中的 \(2\) 类节点两两合并以及前者的 \(2\) 类节点和后者的 \(1\) 类节点两两合并。
对于这样的复杂度，分别考虑每一层第 \(1\) 类和第 \(2\) 类节点个数：显然都是每层最多两个
综上，每一层两类的节点数都是 \(O(n)\) 的，那么每一层合并复杂度为 \(O(n^{2})\)，总区间个数降为 \(O(n^{2}\log V)\) ，再对其排序复杂度即 \(O(n^{2}\log^{2}V)\) ，可以通过。

B.仙人掌

这个东西真的有 *3400 吗？倒着加边感觉不难想啊。

如果是树的话，把边按权值从大往小加入，设 \(f_i\) 为 \(i\) 能到达的点数，对于当前这条边的两个端点 \(u,v\)，有 \(f_u=f_v=f_u+f_v\)。
但是作为仙人掌而言，在环上的点是可能会算重的。
唯一会算重的情况当且仅当加入这个环的最后一条边时，环上存在点 \(w\) 使得 \(u \to w\) 的路径边权递增且 \(v \to w\) 的路径边权递增。
设环上边权最大的那条边为 \((u',v')\)。此时我们会算重 \(u',v'\) 能到达的环外的点和点 \(u',v'\)。
记 \(g_i\) 为枚举完边权为 \(i\) 的边 \((u',v')\) 后 \(u', v'\) 能到达的点数。注意我们只需要用到环上最大边的 \(g_i\)，所以当 \(i\) 是环上最大边时，我们计算 \(g_i=f_u\)。当枚举到环上最小边 \((u,v)\) 时，设这个环的最大边权为 \(i\)。如果这个环的边权先增后减，我们有 \(f_u=f_v=f_u+f_v-g_i\)。
然后我 \(tarjan\) 找环写寄了哈哈哈，反正到现在还不知道找点双和边双的正确写法，鉴定为纯菜。

C.图论题

P7729
显示它的存在。
不过这场月赛竟然是我打的第一场

A.飞行计划

看了好几眼才想出来，二分之后，发现是个 \(\text{2-SAT}\) 问题，\(O(n^2)\) 连边后跑个 \(\text{tarjan}\) 就好，当然你可以先排个序然后线段树优化建图。

B.数字选取

P3172 [CQOI2015] 选数
但是 \(1<N\le10^{12},R-L\le10^6,1\le K\le10^{12},1\le L<R\le10^{12}\) 。

先运用不用动脑子的简单莫反，然后线性筛个 \(\mu\) 能拿 \(60\) 分，然后杜教筛一下就能拿 \(80\) 分。
想通过的话，得运用 \(R-L\le10^6\) 的性质，如果选的数不能重复的话，根据更相减损术，他们的 \(\gcd\le R-L\)。
先做个值域的小优化 \(L=(L-1)/K+1,R=R/K\)，这样问题转化成了 \(\gcd=1\) 的方案数。
我们设 \(f_i\) 表示从 \([L,R]\) 中选出不完全相同的 \(N\) 个数且 \(\gcd=i\) 的方案数，可得以下式子：
\(f_i=(\lfloor\frac{R}{i}\rfloor-\lfloor\frac{L-1}{i}\rfloor)^N-(\lfloor\frac{R}{i}\rfloor-\lfloor\frac{L-1}{i}\rfloor)-\sum\limits_{(i|j)\land(j\le R-L)\land(j>i)}f_j\) ，倒着 \(dp\) 就能求出来了。

C.糖果国

Snacks
赛时唐了去写 \(\text{ddp}\) 了，然后这玩意不就是子树加子树求 \(\max\) 吗？

A.冰风迷途的勇士

赛时猜了手结论，显然猜寄了，取得了 \(80\) 分的好成绩。

乘号最多 \(\log n\) 个，于是设 \(f_{i,j}\) 表示用 \(j\) 个乘号来凑出 \(i\) 所需的最少加号数。
转移的话有两种，要么填加号，要么填乘号，乘号比较好处理，直接枚举因数就好了。
加号有个性质，只需要向前枚举四个就行了，可惜赛时只枚举了一个。

B.魔女的心之火

先挂着，大概是不改了。

C. 沉沦之心

先挂着，可能会改。