新算法·倍增
2026-10-13 19:31:46
发布于：浙江
7阅读
0回复
0点赞
原题：#D0624. [DAY01]角谷变换
偶不不不不不，注意到我们的n会达到10^9，这无疑是让人愤怒的
直接模拟无疑是会超时的
但是注意到任何正整数都能被分成2的幂相加，如：78=2^6 + 2^3 + 2^2 + 2^1 91=2^6 + 2^4 + 2^3 + 2^1 + 2^0
我们定义，s[i][j]=从i开始，使用2^j次f函数
而任意的n都可以被从大到小枚举j来分解，但怎么得到s数组呢？
注意到：s[i][j]=s[ s[i][j-1] ][j-1]
而s[i][0]=f(i)
我们可以用的时间复杂度来预处理s数组，具体代码如下：
vector<vector<int>> s(R+1,vector<int>(35)); // 因为R很小，35完全够
for(int i=1;i<=R;i++)s[i][0]=f(i,1);
for(int j=1;j<=30;j++){
for(int i=1;i<=R;i++)s[i][j]=s[s[i][j-1]][j-1];
}
得到了s数组，那就很简单了，直接一个while(q--)，里面套个for循环分解n，最后输出即可。
完整代码：
#include <bits/stdc++.h>
using namespace std;
int q,R;
int f(int x,int n){
if(n==0)return x;
if((x&1)==0)return f(x>>1,n-1);
return f(min(3*x+1,R),n-1);
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>q>>R;
vector<vector<int>> s(R+1,vector<int>(35));
for(int i=1;i<=R;i++)s[i][0]=f(i,1);
for(int j=1;j<=30;j++){
for(int i=1;i<=R;i++)s[i][j]=s[s[i][j-1]][j-1];
}
while(q--){
int x,n;
cin>>x>>n;
for(int i=30;i>=0&&n>0;i--){
if((1<<i)<=n){
x=s[x][i];
n-=(1<<i);
}
}
cout<<x<<"\n";
}
}
恭喜你，学会了新算法：倍增。
倍增：
难度：中偏下，需要一点优化思维。
方法：预处理s数组，然后直接分解n，用来处理n很大的情况。
用处：处理n很大的情况，直接模拟会超时。
课后作业：
给定定义在 上的函数 ，有 次询问，每次给出 ，求 ，其中 ；
数据范围：，，；
倍增转移公式：，，查询时若 的第 位为 则 。
这里空空如也
有帮助，赞一个