首先需要注意 IO 加速，这方面技巧可以查看公众号“三三信奥”的《[DAY01] 输入输出加速》内容。
子任务 1
把题目给的函数复制下来，对于每个询问直接调用函数输出即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 1000000;
int Q, R;
int f(int x, int n)
{
if (n == 0)
return x;
if (x % 2 == 0)
return f(x / 2, n - 1);
return f(min(3 * x + 1, R), n - 1);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> Q >> R;
while (Q--)
{
int x, n;
cin >> x >> n;
cout << f(x, n) << "\n";
}
return 0;
}
子任务 2
算是一个偏误导的子任务，也确实是一个想不到正解的拿分子任务。
我们容易发现 的变化周期很明显：
这样就有了小范围暴力枚举，大范围通过周期快速计算的方法。
子任务 3
一个偏麻烦的做法
其实从角谷猜想这个基本结论容易发现，这里每个数必然会变到 或变到 ，因此只在处理 和 的变化路径后，预处理 范围内的变化链即可。
实际上因为我造数据偷懒，所以 的变化非常短，没有特意构造。
但实际上处理 范围内的变化链本身就有点麻烦。后面处理周期的细节也有点多。
优雅的倍增
显然变 步可以先变一半再变另一半，这题可以倍增处理。
#include <bits/stdc++.h>
using namespace std;
const int MAXR = 1000000;
int Q, R;
// f[i][j] 存 i 开始 2^j 变到了几。
int f[MAXR + 5][35];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> Q >> R;
for (int i = 1; i <= R; i++)
{
if (i % 2 == 0)
f[i][0] = i / 2;
else
f[i][0] = min(i * 3 + 1, R);
}
for (int j = 1; j <= 30; j++)
for (int i = 1; i <= R; i++)
f[i][j] = f[f[i][j - 1]][j - 1];
while (Q--)
{
int x, n;
cin >> x >> n;
for (int j = 30; j >= 0 && n > 0; j--)
{
if ((1LL << j) <= n)
{
x = f[x][j];
n -= (1LL << j);
}
}
cout << x << "\n";
}
return 0;
}