P9134 [THUPC 2023 初赛] 拧螺丝 题解

· · 题解

观察样例解释，可以得到结论：在完成的前一步，老板来之前，必须有至少 2 个拧好至少 n-k 个螺丝的模块。无论老板收走其中的任何一个，都可以马上拧好另一个。

为了讨论方便，下面继续用 k=3 举例，并假设 n 是很大的数。

而再往前一步呢？再上一步收走后，需要两个分别至少拧好 n-3,n-6 个螺丝的模块，或者 n-4,n-5。

老板的最优策略显然是每次收走最大的那个，因此，再上一步收走前，需要三个分别至少拧好 n-3,n-3,n-6 或 n-4,n-4,n-5 个螺丝的模块。

后者需要更少的总螺丝达成，且最大值更小，因此需要准备被老板收走的其它模块需要的螺丝也更少，所以后者优于前者。

再往前一步，用类似的道理，可以证明需要四个分别至少拧好 n-5,n-5,n-5,n-6 个螺丝的模块；再往前一步是 n-6,n-6,n-6,n-6,n-6；等等。

这样的状态可以用三元组 (width,height,remain) 表示：总共需要准备 width 个模块，其中每个都需要拧好至少 height 个，而其中 remain 个需要再多一个。

这样取名是因为，状态可以用添加一个不完整的行的矩形来表示：height 行 width 列再加上仅有 remain 个的不完整的一行。

可以参考下面的可视化：

o
o
o
o  oo
o  oo  oo
o  oo  ooo  ooo
o  oo  ooo  oooo  ooooo  ooo

容易发现，每次倒推一步相当于：

很容易写出倒推一步的程序。如果倒推了 x 步后发现状态相当于不需要额外准备模块，此时 width=x+1，那么输出 width-1 即可。

最后再特判 k=1，此时 n=1 时答案为 1，否则为不可能。

那么这样就做完了……吗？

每次只能在最上面一列消除 k-1 个，所以 width 的增长是 \left(\dfrac{k}{k-1}\right)^n 级别；在 k 很小而 n 很大时，答案将会无比巨大。

因此，不仅需要使用高精度，而且也不再能一步一步模拟。

不过，当 remain>k 时，每一步仅仅相当于 remain-=k-1;width+=1;，可以直接一次性模拟多步；而 remain\le k 时，下一步就会让 height 减少 1，remain 相应变化。

如此特殊处理后就差不多做完了……吗？

来算一下时间复杂度：需要 O(n) 次 O(n) 位高精与低精的运算，也就是 O(n^2) 的复杂度；再看一眼数据范围，n=10^5。看起来似乎不太过得了。

不过，可以注意到，k=2 时，答案为简单的 2^{n-2}(n\ge 2)，可以简化计算；而 k=3 时，底数仅仅有 1.5，再压一压位似乎常数可以变得很小。所以就可以过了。

参考代码（懒得实现高精，所以直接使用了 python）：

n,k=map(int,input().split(' '))
if k==1: # 特判 k=1
    if n==1:
        print(1)
    else:
        print('Poor E.S.!')
else:
    if k==2: # 特判 k=2
        if n<=2:
            print(1)
        else:
            print(2**(n-2))
    else:
        width,height,remain=1,n,0
        while width<2*k and (height>0 or (height==0 and remain>0)): # width 很小时，无需一次模拟多步
            cnt=width*height+remain
            cnt=cnt-k
            height=cnt//width
            remain=cnt-height*width
            width+=1
            if remain!=0:
                remain+=1
        while height>0 or (height==0 and remain>0): # width 现在很大，必须一次模拟多步
            if remain>=2:
                mult=(remain-2)//(k-1)
                remain=remain-mult*(k-1)
                width+=mult
            height-=1
            width+=1
            remain=width-(k-remain)
        print(width-1)