CF1773F题解

2023-03-20 13:26:18


总思路

总而言之,要让平局越少,我们应尽可能地多选 $1:0$ 和 $0:1$ 的情况。
需要注意的是, $0:0$ 的情况也是平局,所以也要尽可能少。


与其他题解的思路相同(我认为这也是最优思路),我们把比赛结果分为三类处理:

  1. 只踢了一局的;
  2. 总进球数小于总局数的;
  3. 总进球数大于总局数的。

以下分类求解。


第一种:

很简单,要么输赢球数相等,平局;要么不相等,不是平局。

if(n==1){
  if(a==b){//进输球数相等
    cout<<"1"<<endl;//只有一场平局
    cout<<a<<":"<<b;
  }
  else{//不相等
      cout<<"0"<<endl;//没有平局
      cout<<a<<":"<<b;
  }
}

第二种:

每场比赛只进一球(让 $1:0$ 和 $0:1$ 尽可能多),剩下 $n-a-b$ 场比赛必是平局。

if(n>a+b){    
    cout<<n-a-b<<endl;//rt
    for(int i=1;i<=a;i++) cout<<"1:0"<<endl;//a个赢一球的胜场
    for(int i=1;i<=b;i++) cout<<"0:1"<<endl;//b个输一球的败场
    for(int i=n-a-b;i>=1;i--) cout<<"0:0"<<endl;//剩下是真没办法
}

然后就是最大的难点。

第三种:

因为 $a+b>n$ ,所以每场都必有进球,也就是一定存在没有平局的方法。
还需要进一步讨论,把进球数和失球数再分开计算。

else{//不解释
    cout<<"0"<<endl;//肯定没平局
    if(a<=n-1){ //分开讨论  
        for(int i=1;i<=a;i++) cout<<"1:0"<<endl;//用完胜场
        for(int i=1;i<=n-a-1;i++) cout<<"0:1"<<endl;//用尽量多的败场
        cout<<"0:"<<b-n+a+1<<endl;//再用一个败场用完输球数
    }
    else{ //另一种情况  
       for(int i=1;i<=n-2;i++) cout<<"1:0"<<endl;//用n-2个胜场
       //这里要给后面留两场来处理
       if(b!=0){//要处理败场的话
         cout<<a-n+2<<":0"<<endl;//用完胜球数
         cout<<"0:"<<b<<endl; //用完输球数
       }   
       else{//全是胜场
           cout<<"1:0"<<endl;//再来一个 1:0
       cout<<a-n+1<<":0"<<endl;//然后用完胜球数
       }       
   }
}

结束。


完整代码不粘了,问题不大吧。
记住,用 cin 最好带上这个:

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

本题难度还是在的。
主要是 SpecialJudge 的评测方式,加上洛谷上只能爬到四个测试点(一共有五个),所以导致了很多莫名其妙的错误。比如这个,四个点都显示 AC 但结果是 WA 。
除了这个其他就没啥大问题了。
@syhx