感谢各位捧场！

瓜瓜打游戏（EASY）

考虑计数 DP，设 $g(i,j)g(i,\; j)$ 是拿到了通过 $ii$ 关后拿到了 $jj$ 个徽章的路径数，其可以由

• 通过 $i-1i-1$ 关拿到了 $j-1j-1$ 个徽章，在第 $ii$ 关拿了徽章有 $a_{i}a\_i$ 种可能。
• 通过 $i-1i-1$ 关拿到了 $jj$ 个徽章，在第 $ii$ 关没拿徽章只有 $11$ 种可能。

转移到。即得转移式

边界情况是 $g(0,j)=[j=0]g(0,j)\; =\; [j=0]$。递推即可。

这里是代码

瓜瓜打游戏（HARD）

我的方法十分的繁琐（离谱），期待有 dalao 给出更优的方法。

若我们记 $f_i(x)f\_i(x)$ 是 $g(i,j)g(i,j)$ 的 OGF （普通生成函数），可以发现

故 EASY 的答案可以表示为

而 HARD 中指定 $f(x)f(x)$ 的只有最高项系数和最低项系数不为 $00$。即有如下形式

因为 $pp$ 是质数，因此 $b_i=-a_i^{-1}b\_i\; =\; -a\_i^\{-1\}$ 总是可逆的，从而上式可以被重新写为

这个形式指引我们从根的角度思考问题。若 $a_{i}a\_i$ 中有重复，那么 $h(x)h(x)$ 会存在重根 $x=b^{\mathrm{\prime }}x=b\text{'}$，求导后仍是零点 $h^{\mathrm{\prime }}(b^{\mathrm{\prime }})\equiv 0h\text{'}(b\text{'})\; \backslash equiv\; 0$；但是和上式左边 $h^{\mathrm{\prime }}(x)\equiv n{x}^{n-1}h\text{'}(x)\; \backslash equiv\; n\; x^\{n-1\}$ 矛盾。故 $a_{i}a\_i$ 中没有相同的数。

接下来便是在 ${\mathbb{F}}_p\backslash mathbb\{F\}\_p$ 中讨论 $cc$ 的可分解问题，即 $cc$ 应是 $nn$ 次剩余。因为 $pp$ 是质数，故 $pp$ 一定存在原根 $gg$，故我们总可以取离散对数 $c=g^{{}_{g}c}c=g^\{\backslash log\_g\; c\}$。

若 $b_i^n\equiv b_i^n\equiv cb\_i^n\; \backslash equiv\; b\_i^n\; \backslash equiv\; c$，那么

不难通过同余方程的知识，计算得 $cc$ 这样的 $nn$ 次剩余有 $\frac{p-1}{\gcd (p-1,n)}\backslash frac\{p-1\}\{\backslash gcd(p-1,n)\}$，其中每个 $cc$ 对应于 $\gcd (p-1,n)\backslash gcd(p-1,n)$ 个 $b_{i}b\_i$。若我们需要 $nn$ 个解，那么有 $n=\gcd (p-1,n)n\; =\; \backslash gcd(p-1,n)$，即 $n\mid p-1n\; \backslash mid\; p\; -\; 1$。

综上所述，当 $n\mid p-1n\; \backslash mid\; p\; -1$ 时，考虑 $b_{i}b\_i$ 的排列，有 $n!\times \frac{p-1}{n}=(n-1)!(p-1)n!\; \backslash times\; \backslash frac\{p-1\}\{n\}\; =\; (n-1)!(p-1)$ 个解；当 $n\nmid p-1n\; \backslash nmid\; p-1$ 时，有 $00$ 个解。

这里是代码

瓜瓜喜欢做 $A+BA\; +\; B$

不难发现，无论选择哪个点涂色，都会覆盖 $n+m-1n\; +\; m\; -\; 1$个格子，而且必然会覆盖上一轮染色的部分点。

由于每一次染色所用的颜色都各不相同，那么最后一次染色的颜色面积最大。

故输出最后一次所用的颜色编号和 $n+m-1n\; +\; m\; -\; 1$ 即可。

这里是代码

瓜瓜轰炸机

设一个格子的坐标是 $(x,y)(x,y)$，当 $x+yx+y$ 是奇数时，我们称这个格子是奇性的；反之，若 $x+yx+y$ 是偶数时，称为偶性的。

注意到当选择一个格子轰炸时，此处的敌人一定会逃向奇偶性不同的格子。所以当我们轰炸了所有奇性的格子时，就可以保证剩下所有敌人位于偶性的格子内；反之同理，轰炸偶性格子后敌人会跑到奇性格子里。

因此按照此规律轮番轰炸所有偶性格子与奇性格子即可。需特殊注意只有一个格子的情况。

这里是代码

瓜瓜不想上电工课

要让电路中的总电阻尽可能小，那就应当优先翻转 $a_i-b_{i}a\_i\; -\; b\_i$ 大的灯泡。令 $c_i=a_i-b_{i}c\_i\; =\; a\_i\; -b\_i$ 并将其降序排序，取前 $kk$ 个大于 0 的数即可。

这里是代码

周周的猫窝

假若仅考虑猫窝 $A_{i}A\_i$ 和猫窝 $A_{j}A\_j$，可以发现分割其领地的是中垂线，$A_{i}A\_i$ 拥有的领地是中垂线的一侧，即一个半平面。

考虑所有的猫窝，那么 $A_{i}A\_i$ 的领地应是所有半平面的交集，即所有中垂线围成的区域。

本题数据 $nn$ 最大才只有 $1010$ 个点，只卡了暴力，任何一种通过几何计算的做法都可以过。

• 做法一：半平面交。
• 做法二：$n-1n-1$ 条中垂线最多有 $n^{2}n^2$ 个交点，若此交点是领地的顶点，则到 $A_{i}A\_i$ 的距离一定最短。大概是 $O(n^3)O(n^3)$。
• 各种瞎搞……

这里是代码（瞎搞的半平面交）

瓜瓜的 01 串

注意到这两种操作先后顺序并不影响答案，即操作具有交换性。

再注意到操作一重复 $22$ 次等于没变，同一位置的操作二重复 $22$ 次也是没变，因此多余的操作一总是可以转换成操作二而不使答案变劣。

故只需考虑 $00$ 次、$11$ 次操作一足矣。再注意当 $k⩾{\mathrm{c}\mathrm{n}\mathrm{t}}_{1}k\; \backslash geqslant\; \{\backslash rm\; cnt\}\_1$时，因为必需做完 $kk$ 次操作，最后剩下 $11$ 的个数是 $(k-{\mathrm{c}\mathrm{n}\mathrm{t}}_1)\mathrm{m}\mathrm{o}\mathrm{d}2(k-\{\backslash rm\; cnt\}\_1)\; \backslash bmod\; 2$ 。

这里是代码

瓜瓜上电工

注意到题目要求测量的接线柱对 $(a_i,b_i)(a\_i,b\_i)$，一定会在答案流程中以某种顺序出现。

而在接线柱对的某个排列中，插入额外的中间情况并不会让答案更优。因此枚举接线柱对的全排列即可。

这里是代码

周周的舟舟

本题的关键点是 $dd$ 只有 $100100$，并且 $xx$ 坐标互不相同，这意味着每个点最多能和 $200200$ 个点传导。若一些点的距离小于 $dd$，我们可以把这些点看作一个连通块，最终输出的即是连通块的个数。

这启发我们用并查集解决。当我们离线并排序（离散化）后，对于新加入的点 $(x_i,y_i)(x\_i,y\_i)$，连通块的个数先加 $11$，可以直接找到 $x_i-dx\_i-d$ 到 $x_i+dx\_i\; +\; d$ 范围内的敌人；当连通块发生合并时，连通块的个数减 $11$。

也可以不离散化，借助 set 和 map 的二分，也可以通过。

这里是代码

策策学长找 py

由于不能走回头路，那么下一个位置一定满足 $x_i⩽x_{i+1}x\_i\; \backslash leqslant\; x\_\{i+1\}$ 且 $y_i⩽y_{i+1}y\_i\; \backslash leqslant\; y\_\{i+1\}$。

因此可以考虑对 $x+yx+y$ 排序，验证结果满足上述关系即可。

进一步的，可以以 $xx$ 为第一关键字，$yy$ 为第二关键字排序，判断一下 $yy$ 是否是非递减的即可。

这里是代码

瓜瓜选妃

做法一

注意到，若我们修改时考虑二维差分，那么修改是 $O(1)O(1)$ 的，求前缀和是 $O(nm)O(nm)$ 的。

可以对时间二分，总复杂度 $O(nm\log t)O(nm\; \backslash log\; t)$。

这里是代码（二分1）

这里是代码（二分2）

做法二

考虑用并查集维护。对于每行，用并查集维护右侧第一个未被选择的 MM 在哪里（包括自己）；列也同理。当我们需要修改时，就在并查集上边改边跳。

当全部并查集都指向方阵外时，说明全部格子都被选过了。故每个格子最多只会被访问 $11$ 次。

代码：咕咕咕。

周周的泡泡

因为戳破的泡泡必须是连续的，可以考虑二分求解。当我们确定左端点时，随着右端点右移，最终的高度 $hh$ 是单调递减的，预处理前缀和后可以二分答案。复杂度 $O(n\log n)O(n\; \backslash log\; n)$。

进一步，注意到当左端点右移时，二分的右端点是不会左移的，因此可以用双指针算法，复杂度 $O(n)O(n)$。

这里是代码（二分1）

这里是代码（二分2）

HT 巨巨的磁盘

线段树。对于每个节点 $pp$ 维护：左边界最长空闲 $L_{p}L\_p$、右边界最长空闲 $R_{p}R\_p$、整体最长空闲 $V_{p}V\_p$。维护时有一些细节需要注意。

查询空闲 $xx$ 时，可以直接在根节点答案是否存在。下面假设答案在节点 $pp$ 中：

• 如果当前节点 $L_p⩾xL\_p\; \backslash geqslant\; x$，那么节点 $pp$ 的左边界即是答案。
• 如果左子节点 $V_{2p}⩾xV\_\{2p\}\; \backslash geqslant\; x$，那么答案存在于左子树中。
• 如果 $R_{2p}+L_{2p+1}⩾xR\_\{2p\}\; +\; L\_\{2p+1\}\; \backslash geqslant\; x$，那么答案由两个区间拼成。
• 最后，答案只可能存在于右子树中。

这里是代码（线段树1）

这里是代码（线段树2）