题解 P5027 【Barracuda】

· · 题解

前言

因为一个 fabs 卡了一天的题=_=，一开始读题不认真导致后面WAWA的裂开，所以特别想写一篇题解纪念一下

题意

给出 n+1 一个方程 n 个未知数，其中有一个是错误的，要求在有唯一合法的情况下输出最大的砝码的编号，反之输出无解 illegal

那么什么是唯一合法呢?

首先，题目说了， 如果你在枚举不同的两个方程不合法的时候出现了都合法的方案，那么这就直接无解就可以啦

其次，合法的方案中未知数的最大值必须是唯一的，否则也是不合法的

思路

首先，输入是一个神奇的问题，系数其实就是这个位置数被拿的次数，每一次 +1 就可以啦

我们肯定是要枚举出错的方程的编号，我们可以设置一个二维数组 ans[i][j] 表示在第 i 个方程出错时第 j 个未知数的值，每一次求解的时候记得将不合法的放到最后面，方便计算

在计算的时候用到高斯-约旦消元法求解即可，加上随机化更加保险，

最重要的是，每一次计算完以后，要记得检查一下是否合法，如果遇到了不合法的值或者某一个元素无解或者无数解的时候，设为 0 即可，因为合法方案中值都是正整数。

当遇到不合法的时候记录一下 i 方程出错时不存在合法方案，并且记录一下不合法的个数，如果最后不是 n 个不合法的话，直接无解即可啦，因为合法方案必须是唯一的，否则就找到最大值的编号输出就好了

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define random(a,b) ((a)+rand()%((b)-(a)+1))
using namespace std;
const int N=1e2+9;
int a[N][N];
int b[N][N];
int n,m;
int ans=0;
int idx=0;
int lim=0;
bool hang[N];//记录行是不是合法方案 
int cun[N][N];//表示第i个出错时j的值 
int tong[N*10000]; 
int cnt;
bool check()//存入每一个解 
{
    memset(tong,0,sizeof(tong));//清空 
    int maxn=0;
    for(int i=1;i<=n;i++)
    {
        if(!b[i][i])//有0，不对 
        cun[lim][i]=0,hang[lim]=true;
        else if(b[i][i]&&!b[i][n+1])//系数为零，值不为零，更不对 
        cun[lim][i]=0,hang[lim]=true;
        else if(b[i][n+1]/b[i][i]<=0)//是负数，也不对 
        cun[lim][i]=0,hang[lim]=true;
        else //找到最大值，并且在计算过程中桶存每一个值的个数 
        {
            cun[lim][i]=b[i][n+1]/b[i][i];  
            tong[cun[lim][i]]++;
            maxn=max(maxn,cun[lim][i]);
        }
    }
    if(tong[maxn]>1) hang[lim]=true;//最大值不唯一，也不合法 
    if(hang[lim]==true) cnt++;//如果不合法，就记录不合法的方案数 
}
void search()
{
    for(int i=1;i<=n+1;i++)
        swap(b[lim][i],b[n+1][i]);//将没有用的一行换到最下面 
    for(int i=1;i<=n;i++)
    {
        int maxn=i;
        for(int j=i+1;j<=n;j++)
            if(abs(b[j][i])>abs(b[maxn][i]))//记得要加绝对值鸭 
                maxn=j;
        for(int j=1;j<=n+1;j++)
            swap(b[i][j],b[maxn][j]);//高斯约旦消元法 
        if(!b[i][i]) continue;
        for(int j=1;j<=n;j++)
        {
            if(j==i) continue;//别忘了判断i，i 
            int tmp=b[j][i]/b[i][i];
            for(int k=i+1;k<=n+1;k++)
                b[j][k]-=b[i][k]*tmp;
        } 
    }
}
int main()
{
    srand(time(NULL));
    scanf("%d",&n);
    for(int i=1;i<=n+1;i++)
    {
        scanf("%d",&m);
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            a[i][x]++; 
        } 
        scanf("%d",&a[i][n+1]);
    }//按照方程组的方式输入
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            int x=random(1,100);
            if(x&1)
                for(int k=1;k<=n+1;k++)
                    swap(a[i][k],a[j][k]);
        }//随机打乱，貌似没啥用 
    }
    for(int i=1;i<=n+1;i++)//枚举所有的情况 
    {
        memcpy(b,a,sizeof(a));//拷贝一下，防止用原方程计算只能应用一次的情况 
        lim=i;
        search();//计算 
        check();//判断一下是否合法 
    }
    if(cnt!=n)//合法方案没有或者不是唯一的，直接无解 
    {
        cout<<"illegal"<<endl;
        return 0;
    }
    for(int i=1;i<=n+1;i++)
    {
        if(hang[i]) continue;//找出唯一和法的一行来  
        for(int j=1;j<=n;j++)
        {
            if(cun[i][j]>ans)
            {
                ans=cun[i][j];
                idx=j;
            } 
        }
    }
    cout<<idx<<endl;
    return 0;
}