abc293 题解

A/B按题意模拟即可。nAnBC注意到共要走  步，每步有两个方向可选，共  种情况。n由于  ，故  ，故爆搜即可。nCD显然的，颜色在本题中是无效

A/B

按题意模拟即可。
nA
nB

C

注意到共要走 步，每步有两个方向可选，共 种情况。
n由于 ，故 ，故爆搜即可。
nC

D

显然的，颜色在本题中是无效的变量，实际题意如下：

给定一张无向图，保证任意一点度不超过 ，无重边、自环，
n求环的数量和非环的连通块数。

其实已经可以 了，但我不想写，所以再观察下。

由于任意一点度不超过 ，因此连通块只有点、链、环三种可能。
n其中，满足每个点度数都为 的联通块才是环。
n因此考虑并查集，对于每个点维护度数，最后再求出每个连通块的点的最小度数即可。
nD

E

首先考虑暴力。设 ，
n则有 ，边界值
n此时发现 的值仅和 有关，因此考虑到矩阵快速幂。
n我们可以对 构造如下矩阵：

则每次递推相当于乘上如下矩阵:

每次乘完 即可。

题目至此已经解决了
n吗？

交上去，会发现 。。。
n问题在哪？

在 边界值 。
n因为原题数据范围为
n因此还要特判 的情况。。。
nE 和 四发罚时

F

好像是有结论的？
n不重要。
n暴力可以解决一切~

注意到对于不同进制 ， 的 进制表示法显然不同，
n可以得出以下两种暴力：

1. 枚举进制 ，判断 的 进制表示法是否只由 和 构成，时间复杂度
2. 枚举 的表示法，二分是否有满足此表示法的 。看似更优了，可时间复杂度仍为 。

此时已经可以通过 左右，我们接着考虑 时的做法。

接着，我们发现对于第一种暴力，当进制 时，有且仅有 和 两种答案。从第二个暴力的角度，我们发现当 时 最多只有以下 种表示法：
n10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111，因此考虑将两种暴力结合，先使用第二种暴力判段以上 种表示方法，再使用第一种方法枚举 的情况，复杂度为 ，已经可以通过此题。
n若是将特判扩大更多以寻找平衡点可以有更优的复杂度，此处不在讨论。
nF
nPS：一定要处理好二分边界!

G

一眼莫队。
n具体的，一个点加入区间的贡献为增加的同颜色三元组数，由于这个点加在边界处，贡献即为加入前已有点的两元组数，为
n
n删除时同理。
nG
nPS：一定是 组询问，不是 组！一定是 组询问，不是 组！一定是 组询问，不是 组！……

Ex

感觉是换根 ？还没做出来，待会来补。

本文使用 Zhihu On VSCode 创作并发布