当前位置: 代码迷 >> 综合 >> AIM Tech Round 5 (rated, Div. 1 + Div. 2) E. Restore Array
  详细解决方案

AIM Tech Round 5 (rated, Div. 1 + Div. 2) E. Restore Array

热度:115   发布时间:2023-10-29 05:42:17.0

题意

给你一个环b
要你构造一个环a,满足aiai%ai+1=biai+1=bi

题解

第一次构造这种类型的。。想的不是特别好。。
其实,想这种构造余数的,一般要想的就是,我们尽量吧商变为0或1值最好的
这里属于后者
也就是,我们要构造一个余数合法,并且刚好,aiai就之比ai+1ai+1bibi,这样是最好的
后面一个条件很好满足
问题是前面一个
考虑一个余数什么时候合法
自然就是余数比商小的时候
于是得到做法,我们找一个最大的bb
然后从这一位为末尾开始往回填
每一位就是他的上一位加上 b i
特殊的,末尾,也就是最大的那一个为他本身
但是,这样你会发现有几种情况:
1.如果倒数第二位也是最大值怎么办?这样的话,除数和余数就是一样的了,不合法
那么我们找到一个位,他是最大值,并且他比他的上一位大就好了
但是这样又有一一种情况,就是全部数一样怎么办?
可以证明,全部数一样的情况
除了都是0,否则都是无解的
证明很简单,假如这个都是x
那么我们把a序列中,最小的一个拿出来
这个一定是x
但是如果存在有一位是x,那么就是存在一条式子,他的除数和余数都是x了,显然不合法
证毕
2.如果最后一位不合法怎么办?
考虑这种情况什么时候会发生,就是我们只有一个正数,然后别的都是0
这个时候,其实我们只需要把除了最后一位的数都加上bmaxbmax就好了
也就是,倒数第二位比最后一位大两个最后一位
然后就可以了

然后整个题就做完了
时间复杂度是O(n)O(n)

代码

由于写这篇题解和做的时候不是用同一台电脑。。
现在不知道为什么这台机上不去CF。。拿不到代码
就不贴了。。反正很好写
这次我是真的写了!

  相关解决方案