ABC246D 2-variable Function Solution
更好的阅读体验戳此进入
题面
存在函数 $ f(a, b) = a^3 + a^2b + ab^2 + b^3 $,要求 $ a, b \ge 0 $,给定 $ n $,求最小的 $ f(a, b) $ 满足 $ f(a, b) \ge n \(。\) n \le 10^{18} $。
Solution
显然 $ a, b $ 的范围不超过 $ 10^6 $,则可以枚举 $ a $,二分 $ b $,取最小值即可。
对于二分 $ b $ 的单调性证明,可以考虑固定 $ a $ 为参数,则有函数 $ f(b) = b^3 + ab^2 + a^2b + a^3 $,三次函数不好操作,所以考虑求导,显然 $ f'(b) = 3b^2 + 2ab + a^2 $,因为 $ a, b $ 非负,所以显然导函数 $ f'(b) \ge 0 $,所以范围内函数取值单调递增,于是可以二分。
或者不进行二分,根据单调性,显然 $ a $ 减小时 $ b $ 不会比上次更大,所以写个双指针枚举,$ a $ 升序,$ b $ 降序,小于 $ n $ 时直接 break
即可。
Code
#define _USE_MATH_DEFINES
#include <bits/extc++.h>
#define PI M_PI
#define E M_E
#define npt nullptr
#define SON i->to
#define OPNEW void* operator new(size_t)
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(random_device{}());
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
bool rnddd(int x){return rndd(1, 100) <= x;}
typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;
template<typename T = int>
inline T read(void);
ll Func(int a, int b){return (ll)a * a * a + (ll)a * a * b + (ll) a * b * b + (ll)b * b * b;}
int main(){
ll N = read<ll>();
ll mn(LLONG_MAX);
for(int x = 0; x <= (int)1e6; ++x){
int l = 0, r = (int)1e6;
ll cur(-1);
while(l <= r){
int mid = (l + r) >> 1;
ll tmp = Func(x, mid);
if(tmp >= N)cur = tmp, r = mid - 1;
else l = mid + 1;
}
mn = min(mn, cur);
}printf("%lld\n", mn);
fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
template<typename T>
inline T read(void){
T ret(0);
short flag(1);
char c = getchar();
while(c != '-' && !isdigit(c))c = getchar();
if(c == '-')flag = -1, c = getchar();
while(isdigit(c)){
ret *= 10;
ret += int(c - '0');
c = getchar();
}
ret *= flag;
return ret;
}
UPD
update-2022_10_21 初稿
原文地址:http://www.cnblogs.com/tsawke/p/16820302.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性