自动搬运

查看原文

来自洛谷，原作者为

	Johndoe **

搬运于2025-08-24 22:06:58，当前版本为作者最后更新于2018-12-14 02:43:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一开始的想法是记忆化搜索，但是数据范围内存会爆炸。 试验之后会发现当n较大时总是有一长串相同（好像0-10000里面只有400+个不同值），于是就会想用别的方式储存数据。 所以struct个a[MAXN]出来储存数据。

struct func{
	ull start,end,value;
}a[MAXN+1];

然后我们研究一下其实是可以发现，end[i],start[i],value[i]，在i比较大的情况下是有递推关系的（i指第i个区间）

	start[num]=end[num-1]+1;
	value[num]=max(start[num],value[search(start[num]/2)]+value[search(start[num]/3)]+value[search(start[num]/8)]+value[search(start[num]/9)]);
	end[num]=min(ai*(end[search(start[num]/ai)]+1))-1;(ai=2,3,8,9)

其中search（n）是寻找n在那个区间的一个函数 但是当i比较小的情况不一定成立，因为这个递推式是在max(g(n/2)+g(n/3)+g(n/8)+g(n/9),n)=g(n/2)+g(n/3)+g(n/8)+g(n/9)的情况下成立的 可以证明当n比较大时情况的确如此 附代码

#include<iostream>
#include<cmath>
#define ull unsigned long long
#define MAXN 100010
using namespace std;
struct func{
	ull start,end,value;
}a[MAXN+1];
ull num=0;
ull search (ull n){
	ull l=0,r=num,mid=(l+r)/2;
	while (r>l){
		mid=(l+r)/2;
		if (n>a[mid].end)l=mid;
		else if (n<a[mid].start)r=mid;
		else if (n>=a[mid].start&&n<=a[mid].end)return mid;
		else if (n>=a[l].start&&n<=a[l].end)return l;
		else if (n>=a[r].start&&n<=a[r].end)return r;
		else return mid; 
	}
	return mid;
}
ull g(ull n){
	if (n==0)return 0;
	else return max(n,g(n/2)+g(n/3)+g(n/8)+g(n/9));
}
int main(){
	ull n=1e17;
	a[0].start=a[0].end=a[0].value=0;
//	for (ull i=0;i<=n;i++)cout<<i<<" "<<g(i)<<endl;
	for (ull i=1;i<=200;i++){
		if (g(i)!=g(i-1)){
			a[++num].start=i;
			a[num-1].end=i-1;
			a[num].value=g(i);
		}
	}
	while (a[num].end<2*n){
		++num;
		a[num].start=a[num-1].end+1;
		a[num].value=max(a[num].start,a[search(a[num].start/2)].value+a[search(a[num].start/3)].value+a[search(a[num].start/8)].value+a[search(a[num].start/9)].value);
		a[num].end=min(2*(a[search(a[num].start/2)].end+1),min(3*(a[search(a[num].start/3)].end+1),min(8*(a[search(a[num].start/8)].end+1),9*(a[search(a[num].start/9)].end+1))))-1;
	}
//	ull t=n;
//	for (n=0;n<=t;n++)if (a[search(n)].value!=g(n))
long long x,y;
while(cin>>x>>y){
if (x<2||y<2)cout<<x+y<<endl;
else if (x<0)cout<<x+a[search(y)].value<<endl ;
else if (y<0)cout<<y+a[search(x)].value<<endl;
else cout<<a[search(x)].value+a[search(y)].value<<endl;
}
//	cout<<a[search(n)].value<<endl;
}

61ms 应该算是比较快的了