自动搬运

查看原文

来自洛谷，原作者为

	liuyuantao 天行健，君子以自强不息；地势坤，君子以厚德载物 最后在线时间：2025/08

搬运于2025-08-24 23:17:37，当前版本为作者最后更新于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;
}