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也是事實。