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可以得出以下两种暴力:
- 枚举进制 ,判断 的 进制表示法是否只由 和 构成,时间复杂度
- 枚举 的表示法,二分是否有满足此表示法的 。看似更优了,可时间复杂度仍为 。
此时已经可以通过 左右,我们接着考虑 时的做法。
接着,我们发现对于第一种暴力,当进制 时,有且仅有 和 两种答案。从第二个暴力的角度,我们发现当 时 最多只有以下 种表示法:
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 创作并发布
上一篇:Poon Hill ABC徒步
下一篇:数控折弯机销售