锅炉信息网 > 锅炉知识 > 锅炉百科

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 创作并发布

上一篇:Poon Hill ABC徒步

下一篇:数控折弯机销售

精选推荐

  • 711关东煮供应商
    711关东煮供应商

    今天给大家介绍三位,奶粉,全家、罗森这些便利店里关东煮的供应商。店里卖三四块钱一串的关东煮,在网上买不到,一块钱就搞定。首先关东

  • 健康日历|高压锅容易爆炸的4个原因
    健康日历|高压锅容易爆炸的4个原因

    来源:医药养生保健报设计:李雅琴医学审核:姜峰出品人:胡丽丽

  • 高炉
    高炉

    今天这活却是个白事,等到了时辰,那家人便准备火化,本来准备送普炉,我却心中一动,便对那家人说道:“这老人走也不要省,还是送高炉吧。”

  • 高压锅和电压力锅的区别,推荐几款点压力锅
    高压锅和电压力锅的区别,推荐几款点压

    记得之前有一次去朋友家玩,他正在用高压锅煮小米粥,是的,高压锅压小米粥,大概煮了半小时,高压锅突然爆炸了,现场惨不忍睹啊,幸好厨房里没

0