来补之前没考的牛客了！！
"蔚来杯"2022牛客暑期多校训练营（加赛）（EZEC Round）
258 J Jellyfish and its dream
感觉自己不太擅长这种。
差分，操作变成 \((x,1)\rightarrow(x+1,0)\)，即 \((0,1)\rightarrow(1,0),(1,1)\rightarrow(0,2),(2,1)\rightarrow(0,0)\)。
注意到 \(0\) 基本没有意义，因为 \(1\) 可以使用 \((0,1)\rightarrow(1,0)\) 改变位置。（没有逆操作不重要，因为是个环）
仔细想想，发现只要 \(1\) 比 \(2\) 多就一定合法。
259 G Good red-string
有趣，但总感觉有印象，可能考过之后又忘了。
可以说明，有解的充要条件是，每个前缀 \(c_r\geqslant c_e\geqslant c_d\)。（\(c\) 是出现次数）
其可以转换成每个前缀 \(c_e\geqslant c_d\)，每个后缀 \(c_e\geqslant c_r\)。
从前往后扫，如果 \(c_d>c_e\) 就找到最近的问号变成 e，从后往前也做一遍类似的，其余没有填充的问号从前往后分别填 r,e,d 即可。
这一定是最有可能合法的，检查一下就好了。
260 L Lndjy and the mex
感觉有点难啊！
枚举 \(k\) 01 规划计算 mex 不小于 \(k\) 的贡献，再枚举区间内数的构成：（\(a_i\) 是全局每个数出现次数，最后那个括号里是算插入的方案数）
\[\sum_k\sum_{[i\leqslant k]\leqslant b_i\leqslant a_i}{\sum b_i\choose b_0,\cdots,b_n}{n-\sum b_i\choose a_0-b_0,\cdots,a_n-b_n}(n-\sum b_i+1) \]其很类似一个卷积形式，答案可以刻画成：
\[\sum_i i!(n-i)!(n-i+1)[x^i]\sum_{k\geqslant 0}g_0(x)g_1(x)\cdotsf_{n-1}(x)f_n(x) \]这个可以分治 NTT，直接维护一下区间积与区间答案就好了，复杂度 \(O(n\log^2 n)\)。
261 B Bustling City
树上的点的答案很好算，随便长剖一下就好了。
环上的点如果枚举每个点算答案就有点难做，你可以枚举贡献来自哪个结点的人，注意到一个人走的时候与他同行的人数不减，可以算出其第一次达到要求的时刻，然后标记环上对应点，最后在环上推一边贡献就好了。
262 D Directions
很难的一步转化！
我们将所有点根据与 \(1\) 的方向关系分类，将所有在 \(1\) 西部的点根据圆心对称到另一个半圆上，那么 \(a\) 在 \(b\) 西边等价于操作后 \(a\) 在 \(b\) 左边，这样就可以记录目前选了几个在 \(1\) 西部的点，几个在 \(1\) 东部的点 dp 了。
要枚举共有多少点在 \(1\) 西部，复杂度应该是 \(O(n^3)\) 的。
263 A Alternating 2.0
差分，那么一次可以把 \(\leqslant 2\) 个 \(0\) 全部变成 \(1\)，于是操作次数为 \(\lceil\frac{\sum[s_i=s_{i+1}]}{2}\rceil\)。
上取整拆成全局和、权值为奇数的子序列数量，现在分别考虑两个问题：
第一个问题枚举点对算贡献，我们有：
\[\sum_{l\leqslant i<j\leqslant r,s_i=s_j}2^{r-l+i-j} \]这个东西随便拆开一下，化简式子就好了。（拆成 \(i<j\leqslant r\) 减去 \(i<j<l\) 和 \(i<l,l\leqslant j\leqslant r\)）
第二个问题可以观察到奇偶性等于 \((len+[s_1=s_n])\bmod 2\)，我们固定首尾对应位置，若首尾不相邻，那么使得权值为奇数的子序列一定恰好一半，这就很好算了。
复杂度 \(O(n+q)\)。
264 F Flame blast magician master qcjj
其实不难，但是题意太自然了，不太能联想到这个 trick。
二维提示我们使用“减半警报器 trick”（其实我也不知道叫什么名字），我们只需分开维护 \(x,y\) 轴是否 hit 到半血线，这是容易用线段树维护的。
标签：10,44,geqslant,枚举,复杂度,2023,sum,leqslant,rightarrow From： https://www.cnblogs.com/xiaoziyao/p/17197480.html