题解 P5083 【函数】

Johndoe · 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 应该算是比较快的了