题面:
题目背景
小正方形的冒险旅途,并不顺利。
一路上,小正方形看到了壮美秀丽的小岛被污染,看到了雄伟壮观的火山,还碰到了许许多多的敌人。
眼下,小正方形正在对付一个巨大的三角形。
题目描述
大三角形给小正方形讲起自己的过去:过去的它是一个挖宝工,后来被黑暗之主污染才会落到此番境地。
它也希望小正方形去战胜黑暗之主,不过限于黑暗之主的眼线密布,因此必须给小正方形设置障碍才能骗过那些“眼线”。
他给小正方形的问题是:它有 nn 个小三角形,每个小三角形有一定的质量,它对这些三角形进行了 n + 1n+1次称量,然而由于托盘天平(?)的问题,有一次称量的结果是有误的。
现在,大三角形想要知道最重的小三角形的 编号。
一组输入是合法的,当且仅当输入满足以下条件:
不存在一组 ii,jj,使得当我们假定第 ii 条称量数据有误时能求出一种合法方案且我们假定第 jj 条称量数据有误时也能求出一种合法方案。
合法方案定义如下:
1、最重的三角形只有一个。
2、不存在重量不确定的三角形。
3、所有三角形的重量均为正整数。
输入格式
输入的第一行为一个正整数 nn,表示小三角形的数目。
接下来 n + 1n+1 行,每行按照以下格式输入:
首先是一个正整数 mm,表示这次称量抓了几个小三角形。
接下来 mm 个整数,表示称量的小三角形的编号。
最后一个整数 weightweight ,表示这次称量的结果。
输出格式
若合法,输出最重小三角形的编号,否则输出 "illegal"(不含引号)。
因为这道题很有趣 (其实是我毒了13遍才过) ,同时也为了写给自己供复习,于是决定写篇题解
首先,本题n<=100,而高斯消元n^3,如果暴力枚举错误的式子就是n^4,是卡得过去的
这道题的细节处理很多,由题意可以得出这样几个无解情况
1.判断答案是否为正整数
2.是否有多个最重三角形
3.重量不确定,即有多种删掉一个式子的情况合法
于是,上代码 (不喜勿喷)
#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<queue> using namespace std; int n; int a[105][105]; double b[105][105]; int ans; int ansbj; int Gauss() { for(int i=1;i<=n;i++) { int no=i; for(int j=i+1;j<=n;j++)if(abs(b[j][i])>abs(b[no][i]))no=j; for(int j=1;j<=n+1;j++)swap(b[i][j],b[no][j]); double x=b[i][i]; for(int j=i;j<=n+1;j++)b[i][j]/=x; for(int j=1;j<=n;j++) { double y=b[j][i]; for(int k=1;k<=n+1;k++) if(i!=j) b[j][k]-=y*b[i][k]; } }//高斯消元模版,此时第i个未知数的解存在b[i][n+1]中 int num; for(int i=1;i<=n;i++) { num=0; for(int j=1;j<=n+1;j++)if(!b[i][j])num++; if(num==n+1)return 0;//全为0,无数解 } for(int i=1;i<=n;i++)if(b[i][n+1]<=0)return 0;//是否为正数 for(int i=1;i<=n;i++)if(b[i][n+1]!=(int)b[i][n+1])return 0;//是否为整数 double maxx=-0x3f3f3f3f;int bjbj=0; for(int i=1;i<=n;i++)maxx=max(maxx,b[i][n+1]);//求出最重三角形 for(int i=1;i<=n;i++)if(b[i][n+1]==maxx){if(bjbj)return 0;maxx=b[i][n+1];bjbj=i;}//判断是否有多个最重三角形 //如果到这里还没有return就说明答案合法 return bjbj;//返回最重三角形的编号 } int main() { int k,x; scanf("%d",&n); for(int i=1;i<=n+1;i++) { scanf("%d",&k); for(int j=1;j<=k;j++) { scanf("%d",&x); a[i][x]=1; } scanf("%d",&a[i][n+1]); } for(int i=1;i<=n+1;i++) { swap(a[i],a[n+1]);//把错的式子换到第n+1行 for(int j=1;j<=n;j++) for(int k=1;k<=n+1;k++)b[j][k]=a[j][k];//将删去错误式子的矩阵存在b中 swap(a[i],a[n+1]);//换回去 int nobj=Gauss();//判断是否合法 if(nobj) { if(ansbj){printf("illegal");return 0;}//有多种情况合法 ans=nobj;ansbj=1;// } } if(!ansbj)printf("illegal");else printf("%d",ans);//判断是否有合法结果 return 0; }