QOJ # 2835. Number Theory

发布时间 2023-10-02 18:45:43作者: 275307894a

题面传送门

貌似是一个点名被卡的做法,怎么回事呢/cy

首先我看到这个东西感觉一脸进制转换,但是这玩意不是非常严格的进制转换,他的某一位的基数是上一位基数乘 \(10\) 还要 \(+1\),没关系,对于每个数从高到低转化,总能转化出一个合法的进制数。

然后考虑调整这个类似进制的数,首先一个比较容易地观察是每一位的绝对值不会超过 \(10\),否则可以进位,并给 \(1\)\(-1\)。进一步的,我们发现,对这个数的操作只有三种:

  • 将某一位减一,低一位加 \(10\)\(1\) 位加 \(1\)
  • 将某一位加一,低一位减 \(10\)\(1\) 位减 \(1\)
  • 直接将 \(1\) 位上的数进位到后 \(4\) 位。

因此可以设 \(f_{i,j,-1/0/1}\) 表示从高到低到了第 \(i\) 位,\(1\) 位现在的值是 \(j\),上一位是加一/不变/减一的最少用的 \(1\) 的个数和。前两个转移是平凡的,第三个转移因为只有后 \(4\) 位所以暴力也是 \(O(n^2)\) 的,因此总复杂度 \(O(n^2)\)

submission