牛客练习赛15 C.吉姆的奇思妙想(化简二分 溢出处理)
E i = a i ∗ ∑ 1 < = j < = n & & d e g j < = s ( d e g j 2 ∗ f r e j ) b i ∗ ∑ 1 < = j < = n & & d e g j > s M ∗ f r e j = ∑ 1 < = j < = n & & d e g j < = s ( ( a i ∗ d e g j 2 − b i ∗ M ) ∗ f r e j ) ∑ 1 < = j < = n b i ∗ M ∗ f r e j E_i=a_i*\sum\limits_{1<=j<=n\&\°_j<=s}(deg_j^2*fre_j) b_i*\sum\limits_{1<=j<=n\&\°_j>s}M*fre_j\\ =\sum\limits_{1<=j<=n\&\°_j<=s}((a_i*deg_j^2-b_i*M)*fre_j) \sum\limits_{1<=j<=n}b_i*M*fre_j\\ Ei=ai∗1<=j<=n&°j<=s∑(degj2∗frej) bi∗1<=j<=n&°j>s∑M∗frej=1<=j<=n&°j<=s∑((ai∗degj2−bi∗M)∗frej) 1<=j<=n∑bi∗M∗frej
注意到 ∑ 1 < = j < = n b i ∗ M ∗ f r e j \sum\limits_{1<=j<=n}b_i*M*fre_j 1<=j<=n∑bi∗M∗frej其实是个常数
而 a i ∗ d e g j 2 − b i ∗ M a_i*deg_j^2-b_i*M ai∗degj2−bi∗M随时 j j j的增大而增大
所以只需要把所有令 a i ∗ d e g j 2 − b i ∗ M a_i*deg_j^2-b_i*M ai∗degj2−bi∗M小于零的项找出来即可
找出这个最大的 j j j即可
话是这么说,但做的过程中千万小心爆掉long long
我用的是unsigned long long
所以判断负数只是比较大小关系,这样比较保险
非常坑
#include <bits/stdc .h>using namespace std;typedef unsigned long long ll;const ll maxn = 2e5 10;ll m,l,deg[maxn],freq[maxn],pref[maxn],pred[maxn],sqrd[maxn];int main(){scanf("%llu%llu",&m,&l);for(int i=1;i<=l;i ){scanf("%llu%llu",°[i],&freq[i] );pred[i] = pred[i-1] deg[i]*deg[i]*freq[i];sqrd[i] = deg[i]*deg[i];pref[i] = pref[i-1] freq[i];}int q; cin >> q;while( q-- ){ll a,b; cin >> a >> b;ll L = 1, R = l, ans = 0;while( R>=L ){ll mid = L R>>1;if( a*sqrd[mid]<b*m )L = mid 1,ans = mid;elseR = mid-1;}cout << a*pred[ans] b*( pref[l]-pref[ans] )*m << endl;}}