首页 > 代码库 > URAL 1948 H - The Robot on the Line 二分 + 数学
URAL 1948 H - The Robot on the Line 二分 + 数学
给定一条二次函数 f (x) = a * x * x + b * x + c
求一个最小的k，使得f(x) + f(x + 1) + f(x + 2) ..... + f(x + k - 1) 不等于 0 恒成立。
首先把参数统一写成 x + t这样的形式，然后带入去
化简有：a*x*x + (2*a*t+b)*x + a*t*t+b*t+c //现在的t是从0--k-1
列出k个式子，求和（简单的数列求和）。然后就得到一条关于x的二次函数，用判别式判断即可。
为什么能二分?
因为单调。化简后可以看到B*B - 4*A*C。k越大，<0就越成立。因为4*A*C有k的项且指数都比较高。所以这个判断是单调的。
则二分即可。
数字很大 啊。用double居然没爆。应该用到了1e100。double犀利啊
#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>LL a, b, c;bool check (LL t) { double k = (double)t; double B = (b + 2 * a * (k - 1) + b) * k / 2.0; double C = a * (k - 1) * (k) * (2 * (k - 1) + 1) / 6 + (k - 1) * k / 2 * b + k * c; double A = k * a;// cout << B << " " << C << " " << A << endl; return B * B < 4 * A * C;}void work () { cin >> a >> b >> c;// cout << a << " " << b << " " << c << endl; LL begin = 1; LL end = 1e18;// cout << check (9) << endl; while (begin <= end) { LL mid = (begin + end) >> 1;// cout << mid << endl; if (check (mid)) { //mid是满足条件的，就是方程无解的// cout << " ***" << endl; end = mid - 1; } else { begin = mid + 1; } } if (begin > 1e18) { printf ("Infinity\n"); } else { cout << begin << endl; } return ;}int main () {#ifdef local freopen("data.txt","r",stdin);#endif int t; cin >> t; while (t--) work (); return 0;}
URAL 1948 H - The Robot on the Line 二分 + 数学
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。