这个提答还算小清新，不用跑很久，主要是观察数据性质。
Description
小 Q 最近发现了一款新游戏，游戏的目标是从一个新手修炼成为武功高强的大侠。
对着这个游戏，小 Q 玩了很多次仍然玩不出他想要的结局，于是他费尽千辛万苦找到了游戏的剧本。令人惊讶的是，游戏的剧本并不像我们平时见到的剧本，反而很像代码。这个剧本是这样描述的：
量：有 $2$ 种量，常数和变量。
常数：一个整数。
变量：初始值为 $0$ 的可变整数，不同变量用不同正整数区分。
事件：整个剧本由若干个事件构成。所有的事件按照给定的顺序从 $1$ 开始依次编号。事件共有 $3$ 种：普通事件、选择跳转和条件跳转。
执行位置：一个整数，表示接下来将会执行的事件编号，如果不存在这个编号的事件则停止，即游戏到了一个结局。最初的时候执行位置为 $1$。
普通事件：一个变量增加或减少一个量的值。之后执行位置增加 $1$。
选择跳转：两个整数。执行到这里时玩家需要在这两个整数中选择一个，之后执行位置将被修改为这个整数。
条件跳转：两个量和两个整数。执行到这里时，若第一个量小于第二个量，则执行位置将被修改为第一个整数，否则将被修改为第二个整数。
小 Q 认为，整个游戏是希望一个叫做“成就值”的变量（编号为 $1$）最大。
现在给出 $10$ 个剧本，需要求出每个剧本获得最大成就值的每一步选择。
Solution
这个题乍看上去除了 $2^x$ 的搜索没啥办法能做，去看看数据，选择跳转的次数是非常多的。
不知道模拟退火效果怎么样，我估计可以得到一定分数，但无法 AC。
就看看数据吧。
前两个点可以直接搜索过去。
第三个点挺整齐的，发现每 $170$ 行之间是独立的，在进入下一个之前会把所有变量的绝对值加到变量 $1$ 上并清空所有变量。
那么我们对每个块内搜索就好了，最后答案就是每个块内的最大值加起来。
第三个点的代码：
namespace solve
{
const int maxn = 40000;
int var[maxn], n, m;
struct number
{
char type;
int x;
inline int val() { return type == 'c' ? x : var[x]; }
inline void in() { type = readchar(), x = read(); }
};
struct opt
{
char type;
int s1, s2;
int mul;
number a, b;
inline void in(int id)
{
type = readchar();
if (type == 's')
s1 = read(), s2 = read();
else if (type == 'i')
a.in(), b.in(), s1 = read(), s2 = read();
else
{
s1 = id + 1;
a.type = 'v', a.x = read(), mul = readchar() == '+' ? 1 : -1;
b.in();
}
}
} a[maxn];
int choice[maxn];
int ans_choice[maxn], ans, tot;
void dfs(int now, int dep, int i)
{
if (now > (i + 1) * 170)
{
if (var[1] > ans)
{
ans = var[1];
for (int i = 1; i < dep; i++)
ans_choice[i] = choice[i];
tot = dep - 1;
}
return;
}
if (a[now].type == 's')
{
choice[dep] = 1, dfs(a[now].s1, dep + 1, i);
choice[dep] = 2, dfs(a[now].s2, dep + 1, i);
}
else if (a[now].type == 'i')
{
if (a[now].a.val() < a[now].b.val())
dfs(a[now].s1, dep, i);
else
dfs(a[now].s2, dep, i);
}
else
{
int tmp = a[now].mul * a[now].b.val();
var[a[now].a.x] += tmp;
dfs(now + 1, dep, i);
var[a[now].a.x] -= tmp;
}
}
void main()
{
n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i].in(i);
int all = 0;
for (int i = 0; i < 200; i++)
{
dfs(i * 170 + 1, 1, i);
for (int i = 1; i <= tot; i++)
cout << ans_choice[i] << endl;
all += ans;
memset(var, 0, sizeof(var)), ans = 0;
}
cerr << all << endl;
}
}
第 456 个点可以发现都是很多下面这种形式组合起来：
i v 2 c 10 3 4
i c 0 c 1 8 0
s 5 8
v 2 - c 10
v 1 + c 22750
i c 0 c 1 8 0
意思就是，变量 2 有个初值，然后如果变量 2 的值大于 $x$，可以让变量 2 的值减去 $x$，同时变量 1 的值加上一个数，也可以不选。
发现每次跳的地方都比这个地方大，也就是说这是个 DAG，我们倒着跑一个背包即可。
第 78910 个点发现也是由 456 点那样的大块组成的，然后大块内部是类似第三个点的结构，那就大块内搜索，然后背包就好了。
注意不能用行数分块，数据好像并不是完全均匀的，以及价值之类的要算清楚。
直接给出 7 8 9 10 的代码：
namespace solve
{
const int maxn = 40000;
int var[maxn], n, m;
struct number
{
char type;
int x;
inline int val() { return type == 'c' ? x : var[x]; }
inline void in() { type = readchar(), x = read(); }
};
struct opt
{
char type;
int s1, s2;
int mul;
number a, b;
inline void in(int id)
{
type = readchar();
if (type == 's')
s1 = read(), s2 = read();
else if (type == 'i')
a.in(), b.in(), s1 = read(), s2 = read();
else
{
s1 = id + 1;
a.type = 'v', a.x = read(), mul = readchar() == '+' ? 1 : -1;
b.in();
}
}
} a[maxn];
int id[maxn], cnt;
int val[maxn], w[maxn], nxt[maxn];
int is[3000][10010];
int f[3000][10010];
vector<int> all[maxn];
namespace dfs
{
int ans, ans_choice[maxn], tot;
int choice[maxn];
void dfs(int now, int dep, int ed)
{
if (now > ed)
{
if (var[1] > ans)
{
ans = var[1];
for (int i = 1; i < dep; i++)
ans_choice[i] = choice[i];
tot = dep - 1;
}
return;
}
if (a[now].type == 's')
{
choice[dep] = 1, dfs(a[now].s1, dep + 1, ed);
choice[dep] = 2, dfs(a[now].s2, dep + 1, ed);
}
else if (a[now].type == 'i')
{
if (a[now].a.val() < a[now].b.val())
dfs(a[now].s1, dep, ed);
else
dfs(a[now].s2, dep, ed);
}
else
{
int tmp = a[now].mul * a[now].b.val();
var[a[now].a.x] += tmp;
dfs(now + 1, dep, ed);
var[a[now].a.x] -= tmp;
}
}
void work(int bg, int ed, int i)
{
memset(var, 0, sizeof(var)), ans = 0;
memset(ans_choice, 0, sizeof(ans_choice)), tot = 0;
memset(choice, 0, sizeof(choice));
dfs(bg, 1, ed);
// cerr << bg << " " << ed << " " << i << " " << ans << endl;
for (int j = 1; j <= tot; j++)
all[i].push_back(ans_choice[j]);
}
}
vector<int> choice;
void choose(int id)
{
for (int p : all[id])
choice.push_back(p);
}
void back(int i, int j)
{
// cerr << i << " " << j << endl;
if (i > cnt)
return;
if (is[i][j])
{
choice.push_back(1), choose(i + 1);
back(i + 1, j - w[i + 1]);
}
else
{
if (j >= w[i + 1])
choice.push_back(2);
back(nxt[i], j);
}
}
int isbg[maxn];
void main()
{
n = read(), m = read();
for (int i = 1; i <= n; i++)
a[i].in(i);
int W = a[1].b.val();
for (int i = 1; i <= n - 2; i++)
{
if (a[i].type == 's' && a[i + 1].type == 'v' && a[i + 2].type == 's')
{
isbg[i] = 1;
id[i] = ++cnt;
}
}
id[n + 1] = cnt + 1;
w[cnt + 1] = 1e9;
cerr << cnt << endl;
for (int i = n; i >= 1; i--)
{
if (!id[i])
id[i] = id[i + 1];
}
for (int i = 1; i <= n; i++)
{
if (isbg[i])
{
dfs::work(i + 2, a[i].s2 - 2, id[i] + 1);
val[id[i] + 1] = dfs::ans;
w[id[i] + 1] = a[i - 2].b.val();
nxt[id[i]] = id[a[i].s2];
}
}
for (int i = 1; i <= cnt; i++)
if (!nxt[i])
nxt[i] = cnt + 1;
// for (int i = 1; i <= cnt; i++)
// cerr << nxt[i] << endl;
for (int i = cnt; i >= 1; i--)
{
memcpy(f[i], f[nxt[i]], sizeof(f[i]));
for (int j = W; j >= w[i + 1]; j--)
{
if (f[i + 1][j - w[i + 1]] + val[i + 1] > f[i][j])
{
f[i][j] = f[i + 1][j - w[i + 1]] + val[i + 1];
is[i][j] = 1;
}
}
}
// for (int i = 1; i <= cnt + 1; i++)
// cerr << w[i] << " " << val[i] << endl;
int j = max_element(f[1], f[1] + W + 1) - f[1], res = f[1][j];
cerr << j << " " << res << endl;
back(1, j);
for (int p : choice)
cout << p << endl;
}
}