P1335 [NOI2013] 小Q的修炼 题解

nevergiveuphhhh · 2021-09-05 18:26:52 · 题解

对于此题，我认为的难点是观察数据并猜测性质和读入操作。

我隔一会就思考这个字符串读起来怎么这么麻烦啊。

首先可以发现，这个所有的选择都之后往后走，就是个 topo 图。

task1,2,3

观察到数据有形如:

s x x+11

v 3 + c y

v 4 + c y

v 5 + c y

v 6 + c y

v 7 + c y

v 8 + c y

v 9 + c y

v 10 + c y

v 11 + c y

v 12 + c y

之类的东西，而且每个这样的循环后面有一个这样的东西。

i v 3 c 0 43 45

v 1 - v 3

i c 0 c 1 46 0

v 1 + v 3

v 3 - v 3

i v 4 c 0 48 50

v 1 - v 4

i c 0 c 1 51 0

v 1 + v 4

v 4 - v 4

发现这个就是把正的数据加到 1 上，负的不变并清空。

这样就没法贪心或者 dp 了。

然后我们又发现循环长度很小，直接爆搜就行了。

task4,5,6

最开始对变量 2 有一个正的初值。

然后:

s 5 8

v 2 - c 10

v 1 + c 22750

i c 0 c 1 8 0

i v 2 c 9 9 10

i c 0 c 1 14 0

循环节长这样。

每次如果选择，会有一些跳转之类的。

发现 2 的初值比较小而且后面只会减。

考虑 dp 。