1 条题解

  • 4
    @ 2026-11-3 14:21:17

    对于每一个当前处理的队伍 ii,显然它应该赢,设其分数为 m=pi+3m=p_i+3。

    接下来分类讨论所有其他比赛:

    让我们化身 【数据删除】 贪心的操纵比赛。

    设 l,rl,r 分别是一场比赛中双方在比赛开始前的得分(l<=rl<=r)。

    若 l<m,r<ml<m,r<m 显然可以令两者打平不对 ii 造成影响。

    若 l<m,r=ml<m,r=m 应该令 ll 获胜。若 l∈[m−2,m−1]l\in[m-2,m-1] 比 mm 大的数量加一。

    若 l=m,r=ml=m,r=m 随便令其中一个获胜,答案加一。

    若 l>m,r>ml>m,r>m 分数太多操控也没用,答案加二。

    但是暴力相加是不优的,注意到最后一类可以预处理,三四类有一个共同特点是右端点是 m,直接在预处理的时候开桶计算,前两类没有贡献直接忽视。

    #include<bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=2e5+19;
    int a[N],n,b[N];
    int t[N*3];
    signed main(){
    	freopen("football.in","r",stdin);
    	freopen("football.out","w",stdout);
    	cin >> n;
    	for(int i=1;i<=n*2;i++){
    		cin >> a[i];b[i]=a[i];
    	}sort(b+1,b+n+n+1);
    	for(int i=1;i<=n;i++){
    		int x,y;cin>>x>>y;
    		x++,y++;
    		if(a[x]>a[y]) swap(x,y);
    		if(a[y]-2<=a[x]&&a[x]<=a[y]){
    			t[a[y]]++;
    		}
    	}
    	for(int i=1;i<=n*2;i++){
    		int ct=upper_bound(b+1,b+n+n+1,a[i]+3)-b-1;
    		//cout << ct << "()\n";
    		int ans=n+n-ct+1+t[a[i]+3];
    		cout << ans << ' ';
    	} 
    	return 0;
    } 
    

    [2026济南登峰营] D1 P1 足球乱斗(football) - 文件读写

    信息

    ID
    962
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    31
    已通过
    11
    上传者