Widget Factory
题目大意：有n种零件，已知每种零件的加工时间最少为3天最多为9天，现在只知道有m个工程用的时间和加工的零件数，问可不可以求出每种零件的加工时间。
/* 求解同余方程组问题。 与一般求解线性方程组的问题类似，只要在求解过程中加入取余即可。 注意：当方程组唯一解时，求解过程中要保证解在[3, 9]之间。 */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 310 using namespace std; int n,m,a[maxn][maxn],ans[maxn]; char str[8][10]={"S","MON","TUE","WED","THU","FRI","SAT","SUN"}; char s1[10],s2[10]; int guass(){ int k=1,num=0; for(int i=1;i<=m&&k<=n;i++){//一共n个未知量 int p=m+1; for(int j=i;j<=m;j++)if(a[j][k]){p=j;break;}//可以用第j个工程求第k个零件,与高斯消元模板中取最大是一样的 if(p==m+1){k++;i--;continue;}//没有任何一个工程可以用来求第k个零件，那么求下一个零件 for(int j=1;j<=n+1;j++)swap(a[i][j],a[p][j]);//因为我们只需要阶梯状的部分，所以从k开始也无所谓 for(int j=i+1;j<=m;j++){ if(!a[j][k])continue; int tmp=a[j][k]; for(int l=k;l<=n+1;l++){//将下面各个方程的这一项化为0 a[j][l]=a[i][l]*tmp-a[j][l]*a[i][k];//这里是为了保证所有数字都是整数 a[j][l]=(a[j][l]%7+7)%7; } } num++;k++; } for(int i=num+1;i<=m;i++)if(a[i][n+1])return 0;//无解 if(num!=n)return 1;//多解 for(int i=n;i>=1;i--){ for(int j=i+1;j<=n;j++){ a[i][n+1]=a[i][n+1]-ans[j]*a[i][j]; a[i][n+1]=(a[i][n+1]%7+7)%7; } ans[i]=0; for(int j=3;j<=9;j++){//枚举答案 if(a[i][i]*j%7==a[i][n+1])ans[i]=j; } } return 2; } int main(){ freopen("Cola.txt","r",stdin); while(1){ memset(a,0,sizeof(a)); scanf("%d%d",&n,&m); if(n==0&&m==0)return 0; int k1,k2,x,num; for(int i=1;i<=m;i++){ scanf("%d%s%s",&num,s1,s2); for(int j=1;j<=7;j++){ if(!strcmp(str[j],s1))k1=j; if(!strcmp(str[j],s2))k2=j; } a[i][n+1]=(k2-k1+1+7)%7; for(int j=1;j<=num;j++){ scanf("%d",&x); a[i][x]++; if(a[i][x]>=7)a[i][x]-=7; } } k1=guass(); if(k1==0)printf("Inconsistent data. "); else if(k1==1)printf("Multiple solutions. "); else{ for(int i=1;i<=n;i++)printf("%d ",ans[i]); puts(""); } } }