2025 河北ICPC( D. 金泰园（二分）-- C.年少的誓约(公式转化))

2025 河北ICPC

题目链接：

Attachments - The 9th Hebei Collegiate Programming Contest - Codeforces

sdccpc20250522 - Virtual Judge

赛时：5道

D. 金泰园（二分）

没想到二分，偶然间听到，还没想出怎么二分，此题借助题解和其他人代码。

• 二分对象是谁？

​ 本题，如果二分答案即和的最小值，check函数怎么写呢？

​ 似乎解决不了。那还可以二分什么呢？

​ 二分找到所选择的k对中的最大差值 ，

• check函数怎么写？

  对于x ，如果差值小于等于x的对数大于等于 k ，说明最小差值小于等于 x。

• 怎么查找差值小于等于x的对数

  对于排好序的数组，如果a[i+p]-a[i]<=x,p是满足条件的最大值，

  那么对于a[i+1+t]-a[i+1]<=x 满足条件的 t 一定大于 p。

  易知，所有满足的下标值是不断增大的，最大为 n 。

  循环计算每个a[i],所构成的对数。

• 已知x,再通过前缀和 计算 差值小于等于 x 的和

• 用cnt记录满足条件的对数有多少个

• 最大差值为 x ，不代表所有差值等于 x 都需要选择。用cnt-k,就是多计算的。

int a[N],n,k,pre[N];
bool check(int x)
{int sum=0,p=1;for(int i=1;i<=n;i++){while(p<=n&&a[p]-a[i]<=x) p++;sum+=p-i-1;}return sum>=k;
}
void solve()
{cin>>n>>k;fir(i,1,n)cin>>a[i];sort(a+1,a+n+1);int l=1,r=1e8;//找到前k个的最大差值while(l<r){int mid=(l+r)>>1;if(check(mid))r=mid;else l=mid+1;}fir(i,1,n)pre[i]+=pre[i-1]+a[i];int ans=0,cnt=0,p=1;for(int i=1;i<=n;i++){while(p<=n&&a[p]-a[i]<=l)p++;ans+=pre[p-1]-pre[i]-a[i]*(p-i-1);cnt+=p-i-1;//计算有几个>=l}ans-=(cnt-k)*l;//减去多余的cout<<ans;
}

C.年少的誓约(公式转化)

有几个坑：

• n*x<m ,输出NO。不然可能WA/RE
• 数据范围 ：__int128

对所有的c-b*k进行排序，按顺序分配 x , x , x , m%x , 0 , 0 , 0

int a[N];
void solve()
{ int n,m,k,x;cin>>n>>m>>k>>x;__int128 sum=0,ans=0;fir(i,1,n){int xx,yy;cin>>xx>>yy;a[i]=yy-k*xx;      sum+=xx*yy;}  if(n*x<m){cout<<"NO\n";return;}  int f=m/x,g=m%x;ans+=(__int128)x*x*k*f+(__int128)g*g*k;sort(a+1,a+n+1,greater<int>());fir(i,1,f){ans+=(__int128)a[i]*x;}ans+=(__int128)a[f+1]*g;if(ans<=sum)cout<<"NO\n";else cout<<"YES\n";}

总结

赛时C、D题没写出来，太可惜了。虽然目前只过了7道题，不过也还可以。

今天是CCPC训练赛第一天，我们队稳扎稳打，凡是过的题，都没有WA

就是慢了一点，但目前不构成影响。

希望明天训练赛，大脑在线。

今天D题竟然没看出二分！！！每次的二分都意料之外，虽然现在看来不过如此，没A也是事实。