题解：P12711 [KOI 2021 Round 1] 棒球赛季

liuyuantao · 2025-06-07 21:15:55 · 题解

题目传送门
对于区内赛，每支队伍与区内的 M-1 队比 A=kB 场，共有 M 支队伍，N 个区域，故总共比了 \frac{kBNM(M-1)}{2} 场（去重）。
对于区外赛，每支队伍与区外的 (N-1)M 队比 B 场，共有 NM 支球队，总共比了 \frac{BN(N-1)M^2}{2} 场。
故总场数为 \frac{kBNM(M-1)}{2}+\frac{BN(N-1)M^2}{2}=\frac{BNM[k(M-1)+(N-1)M]}{2} \le D，解得 B \le \frac{2D}{NM[k(M-1)+(N-1)M]}，故 B=⌊\frac{2D}{NM[k(M-1)+(N-1)M]}⌋。
之后代回计算即可。
复杂度显然是 O(T) 的。

AC code

#include <bits/stdc++.h>

using namespace std;

#define LL long long

LL n,m,k,T,q,cnt,ans,sum;

int main(){
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--){
        cin>>n>>m>>k>>q;
        sum=m*k*(m-1);
        cnt=m*n*(n-1);
        ans=floor(1.0*2*q/(cnt+sum));
        cout<<(ans*sum+ans*cnt)/2<<endl;
    }

    return 0;
}