2021牛客多校第五场 ¶

排名	当场过题数	至今过题数	总题数
16/233	8	11	11

A¶

upsolved by 2sozx JJLeo

题意¶

一颗仙人掌，问每次询问三个点 $c, d, l$ 寻找一个点在 $(c, d)$ 和 $(c, l)$ 的最短路上并且距离 $c$ 最远。$n \le 10^5$

题解¶

虽然但是，这不是仙人掌很模板的东西(x，MJX纯nt，仙人掌直接读成了图，不可做！

简略题解：可以建立广义圆方树(别问，问就是懒)，然后每个点记录他是环上的第几个点即可知道答案，距离可以使用节点编号与 $n$ 大小判断是否 $ + 1$。

答案只能是 $fa(lca(c, d, l)), lca(c, d), lca(c, l), lca(d, l)$ 其中之一，三点的 $lca$ 可以粗略理解一下，就是中间那个点，具体判断只需要判断是否这个点是最短路上的点即可。

C¶

solved by JJLeo 2sozx

题意¶

乒乓球规则，两人打 $n$ 小轮，问第一个人在 $i$ 分为获胜分的情况下能赢多少轮。$n \le 10^6$

题解¶

对于 $i$ 显然需要至少 $i$ 轮，将 $W、L$ 分别存入 vector，对于一个位置可以 $O(1)$ 寻找到其中一个人得到 $i$ 分的位置，如果此时分差超过了 $2$ 分，那么直接结束。

否则高分的人一定比低分人分数高 $1$ ，因此可以通过下一个位置的胜负判断是否结束还是分数变为相同。如果分数相同，那么在之后的过程中双方分差不得超过 $2$，否则直接结束，可以通过预处理得到每个位置开始分差不超过 $2$ 的最长结尾在哪。

预处理可以 $ST$ 表，也可以直接 $O(n)$ 扫一遍。对于不同的 $i$ 询问总复杂度是调和级数的。

E¶

upsolved by 2sozx JJLeo

题意¶

稍微简化个题意，去掉了个没啥用的条件。

一棵树，有点权，边上为 $\text{or,and,xor}$ 其中一种，每次询问一个节点，子树所有点到这个节点路径按边上运算符计算后的所有值，这些值 $\text{or,and,xor}$ 起来的答案。

题解¶

可以考虑对于每个点记录这三个的答案，考虑父亲由孩子转移即可，所有转移式子都形如如下形式： $$ (a_1 \operatorname{opt_1} x) \operatorname{opt_2}(a_2 \operatorname{opt_1} x) \operatorname{opt_2} \cdots \operatorname{opt_2}(a_n \operatorname{opt_1} x) $$ 将 $\operatorname{opt_1},\operatorname{opt_2}$ 分别用 $\text{or,and,xor}$ 代替，一共有九种可能，可以分类讨论出来其逻辑表达式，具体的表达式列表格意义不大，下面直接粘贴代码了

void dfs(int i){
    siz[i] = 1;
    f[i][0] = f[i][2] = 0, f[i][1] = -1;
    for(int j = 0;j < v[i].size();j++){
        int to = v[i][j].first, opt = v[i][j].second;
        dfs(to), siz[i] += siz[to];
        if(opt == 0){ // |
            f[i][0] |= f[to][0] | a[i];
            f[i][1] &= f[to][1] | a[i];
            f[i][2] ^= (~a[i] & f[to][2]) | (siz[to] & 1 ? a[i] : 0);
        }else if(opt == 1){ // &
            f[i][0] |= f[to][0] & a[i];
            f[i][1] &= f[to][1] & a[i];
            f[i][2] ^= f[to][2] & a[i];
        }else{ // ^
            f[i][0] |= (~a[i] & f[to][0]) | (a[i] & ~f[to][1]);
            f[i][1] &= (~a[i] & f[to][1]) | (a[i] & ~f[to][0]);
            f[i][2] ^= f[to][2] ^ (siz[to] & 1 ? a[i] : 0);
        }
    }
    g[i][0] = f[i][0], f[i][0] |= a[i];
    g[i][1] = f[i][1], f[i][1] &= a[i];
    g[i][2] = f[i][2], f[i][2] ^= a[i];
}

F¶

solved by Bazoka13 2sozx

题意¶

给一个凸包，点集大小为 $n$ ，按逆时针记为 $A_i$，对于内部的一个点 $P$ 的值定义为 $\min\limits_{i = 1}^n \angle{A_iPA_{i+1}}$ ，求对于内部所有点的值的最大值。$n\le100$

题解¶

答案显然可以二分，考虑如何 check。

对于一个边 $A_iA_{i+1}$，如果$\angle{A_iPA_{i+1}}$ 相同，显然是在同一个圆弧上，并且若$P$ 在圆弧与边内部的区域，角度一定大于此值，因此对于每条边构建出一个圆，判断圆是否有交即可。

G¶

solved by JJLeo

题意¶

最小化 $x+y$ 使得 $\operatorname{lcm}(a+x,b+y)=c$，$c$ 以不超过 $18$ 个质因子的形式给出。

题解¶

设 $n=18$，遍历 $c$ 的所有因子，至多有 $2^n$ 个。对于因子 $p$，如果其 $\ge a$ 就可以成为一个合法的 $x=p-a$，$y$ 同理。

同时还需要保证 $a+x$ 和 $b+y$ 对于每个质因子至少有一个次数和 $c$ 相同，统计时状压成集合，相当于要求两个集合的并是全集。

分别设 $f_S$ 和 $g_S$ 为对应子集的最小 $x$ 和 $y$，对 $g_S$ 做高维前缀和变为 $h_S = \min \limits _{S \in T} g_T$，答案即为 $\min \limits _S (f_S+h_{U-S})$。

总时间复杂度为 $O(n2^n)$。

I¶

upsolved by JJLeo

题意¶

长度为 $n$ 的序列，$q$ 次询问，每次问 $[l,r]$ 区间序列排序后最长连续段的长度，同时不断向两侧扩展 $k$ 次，输出每次扩展后的答案。($1 \le n \le q \le 10^5$，$\sum k \le 10^7$)

题解¶

一个想法是莫队 + 可撤销并查集，发现莫队不好撤销，且并查集带个 $\log$ 不知道能不能过 $O(n \sqrt n \log n + \sum k \log n)$。

考虑回滚莫队，排序和莫队一样，对于在一块的按右端点排序，右侧不断增加，左侧不断回滚，复杂度不变，可以卡过去。

正解为将可撤销并查集改成链表，因此只需要每次被合并的一定是一个连通块的两端，因此维护每个连通块的两端并把信息更新到上面就可以了，总时间复杂度为 $O(n \sqrt n + \sum k)$。

记录¶

0h：H是个签到，但是还是个构造，MJX乱构造一通加上瞎猜结论导致debuff拉满，直接白给一发，ZYF想B，CSK看了F发现好可做直接开始推式子证明。MJX和ZYF讨论讨论B整了个做法直接交了，发现初始没排序，直接白给。然后ZYF睡醒了，看K就一sb题直接冲了。D也是个暴力DP直接冲

1h：ZYF D 开了个没用的数组直接MLE，CSK和MJX说了说做法MJX觉得太对了CSK继续写。MJX看J是个大模板，抄板子直接过了。MJX和ZYF讨论G发现直接枚举集合然后就很可做了，CSK发现F题题读错了，寄！

2h：ZYF写G没开高维前缀和，白给一发，看C也是很好写想了想直接开写，MJX 和 CSK 说F然后虽然题读错了，但是方法还是差不多的，搞个圆交板子就完事。MJX写了个C的递推求最长合法的，然后交了就挂了，ZYF直接改成 $O(n \log n)$ 的求法，过了。

3h：CSK F一直没调出来，有奇奇怪怪的bug，看了半天，最后发现二分判断时候写了if没写else，寄！MJX看A是很经典的题，但是变成了图，完全不会做(赛后发现是个仙人掌，草！)，考虑一起看E和I

4h： MJX 想了个E的思路，ZYF给了个奇怪的解法，MJX感觉不可写，然后就感觉E不会维护了，然后一起想I，想了个分块+并查集的做法，不知道咋维护size的撤销（感觉都失忆了，不是纯回滚莫队），开始罚坐，寄！

总结¶

读题读题读题！！！！

想的时候想深点

Dirt¶

B(+1)：开始没排序

C(+1)：MJX奇怪的式子

D(+1)：MLE了，老nt了

G(+1)：没求高位前缀和

H(+1)：MJX是sb

2021牛客多校第五场¶

A¶

题意¶

题解¶

C¶

题意¶

题解¶

E¶

题意¶

题解¶

F¶

题意¶

题解¶

G¶

题意¶

题解¶

I¶

题意¶

题解¶

记录¶

总结¶

Dirt¶

2021牛客多校第五场 ¶