Bear and Tower of Cubes Codeforces

https://codeforces.com/contest/680/problem/D

一道2D，又是搞两个小时才搞出来。。。不过好在搞出来了

官方题解：可以证明对于m,设a是满足a^3<=m的最大a，那么选a或a-1一定最优；那么可以暴力dfs

....23333.。。。。。

完了，我也不知道为什么这个代码能A了

我的想法（仅做记录）：对于m=m1的方案，如果最大的选a，那么说明X在[a^3,min((a+1)^3-1,m1)]区间内；这个区间的两个端点都减去a^3后，就发现m=m1的方案，相当于在m=min((a+1)^3-1,m1)-a^3时的方案上再补上取一个a

然后我打了一个很naive的暴力，就是枚举最大的数（设为i）。。根本不能A

考虑优化这个dp：

当m1<(i+1)^3-1即i>(m+1)的三次方根-1时，答案是m=m1-i^3时的答案补上取一个i，显然i变得更小时，答案的第一项不会变得更差，但是当答案的第一项相等时，i越大答案的第二项越好，因此暴力从最小的可能i枚举到最大的可能i，更新答案，如果发现枚举到某处时这一次得到的答案比当前总答案第一项劣，就跳出（所以其实是玄学暴力23333）

当m1>=(i+1)^3-1即i<=(m+1)的三次方根-1时，答案是m=(i+1)^3-i^3-1的答案补上取一个i，显然i变得更大时，答案总体不会变得更劣，因此只求i=(m+1)的三次方根-1时的答案即可

看了题解后发现自己这样搞其实有些无用的枚举（就比如第一种情况也是只考虑一个值就行了，这就是65行以后漏掉了对lt的赋值还能A的原因）

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<map>

 #include<cmath>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<ll,ll> pll;

 const ll N=;

 ll poww(ll x)

 {

     return x*x*x;

 }

 ll work(ll x)

 {

     ll t=pow(x,0.333333333333333333);

     while(poww(t+)<=x)    t++;

     while(poww(t)>x)    t--;

     return t;

 }

 map<ll,pll> an;ll num;

 //pll solve(ll m)

 //{

 //    if(an.count(m))    return an[m];

 //    //num++;

 //    //if(num%100000==0)    printf("%lld\n",num);

 //    //printf("%lld\n",m);

 //    //scanf("%d",new int);

 //    pll ans,t;ll tt;

 //    for(ll i=1;i<=N;i++)

 //    {

 //        tt=poww(i);

 //        if(tt>m)    break;

 //        //if(poww(i+1)-1>m)    break;

 //        t=solve(min(m,poww(i+1)-1)-tt);

 //        t.fi++;t.se+=tt;

 //        ans=max(ans,t);

 //    }

 //    return an[m]=ans;

 //}

 pll solve(ll m)

 {

     if(an.count(m))    return an[m];

     pll ans(-,-),t,lt(-,-);ll t3=work(m+)-;

     if(t3>&&t3<=N)

     {

         t=solve(poww(t3+)-poww(t3)-);

         t.fi++;t.se+=poww(t3);

         ans=t;

     }

     if(t3!=m)

     {

         for(ll i=t3+;i<=N;i++)

         {

             if(m-poww(i)<)    break;

             t=solve(m-poww(i));

             if(lt.fi!=-&&lt.fi!=t.fi)    break;

             t.fi++;t.se+=poww(i);

             ans=max(ans,t);

         }

     }

     return an[m]=ans;

 }

 int main()

 {

     ll m;

     an[]=mp(,);

     scanf("%lld",&m);

     auto t=solve(m);

     printf("%lld %lld\n",t.fi,t.se);

     return ;

 }

巴特西

Bear and Tower of Cubes Codeforces - 680D

最新文章

热门文章