题解：P6458 [COCI2006-2007#5] LIGA

tiantianyang · 2025-01-08 16:55:43 · 题解

题目传送门

题目大意

有 n 支队伍参加了一场比赛，每胜一场记三分，每平一场记一分，负场不计分。

思路

方案一（暴力）：

先让我们康一下数据一百场，这不就很棒吗！O(n^3) 都可以跑过，我们直接暴力启动。

我们暴力枚举一至一百的每一个参数的污染数据，同时因为题目保证有唯一解，所以并不存在无法推出来的情况。

代码（暴力）

#include<bits/stdc++.h>
using namespace std;
int n,vis[1005][10];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=5;j++){
            string s;cin>>s;
            if(s == "?"){vis[i][j]=-1;continue;}
            int now=0;
            for(int k=0;k<s.length();k++) now=now*10+s[k]-'0';
            vis[i][j]=now;
        }
    for(int i=1;i<=n;i++){
        for(int a=0;a<=100;a++)
            for(int b=0;b<=100-a;b++)
                for(int c=0;c<=100-a-b;c++) if((a+b+c==vis[i][1]||vis[i][1]==-1)&&(a==vis[i][2]||vis[i][2]==-1)&&(b==vis[i][3]||vis[i][3]==-1)&&(c==vis[i][4]||vis[i][4]==-1)&&(3*a+b==vis[i][5]||vis[i][5]==-1)) {vis[i][1]=a+b+c;vis[i][2]=a;vis[i][3]=b;vis[i][4]=c;vis[i][5]=3*a+b;break;}
        for(int j=1;j<=5;j++) cout<<vis[i][j]<< ' ';
        cout<<endl;
    }
    return 0;
}

方案二（由已知推未知）：

设第一个为 a 第二个为 b 第三个为 c 第四个为 d 第五个为 e。

未知一个：

• 未知 a，a=b+c+d。
• 未知 b，b=a-c-d。
• 未知 e，e=3b+c。省略其他。

未知两个：

• 未知 a 与 d，无唯一解。
• 未知 a 与 b，b=\frac{e-c}{3}，a=b+c+d。省略其他。

未知三个：

• 未知 a 与 b 与 c 或 b 与 d 与 e 或 c 与 d 与 e，这样的有约束，可求其他无解。

未知四个：

• 都无解。

注意：文章中明确说明了不会出现超过一百个的，所以我们可以判断这个比赛数假如超过了一百个就说明有问题！

代码

无！