题目描述

小部件工厂生产几种不同类型的小部件。

每个小部件都是精心制作而成。

制作小部件所需的时间取决于其类型：简单小部件仅需要3天，但最复杂的小部件可能需要多达9天。

工厂目前处于完全混乱的状态：最近，工厂被一位新主人收购，新主人解雇了几乎所有员工。

新员工对制作小部件毫无经验，没有人清楚制作每个不同类型的小部件分别需要多少天。

当客户订购小部件，工厂却无法告诉客户生产所需商品需要多少天时显得十分尴尬。

幸运的是，这里有记录记载了每个工人开始制作的日期，完成制作的日期以及制作的小部件型号。

但是问题是记录没有明确记载工人开始和完成工作的确切日期，只记录了该天是星期几。

尽管如此，这些信息也是有些帮助的：例如，如果一个人在星期二开始制作一个41型小部件，并在周五完成，那么我们就知道了制作一个41型小部件需要4天时间（因为最多不超过9天，所以不可能是11天或更多）。

您的任务是从这些记录中（如果可能）找出制作不同类型的小部件所需的天数。

样例

输入
2 3
2 MON THU
1 2
3 MON FRI
1 1 2
3 MON SUN
1 2 2
10 2
1 MON TUE 
3
1 MON WED
3
0 0

输出8 3
Inconsistent data.

算法1

(高斯消元) $O(n^2)$

题意：有很多个零件，每个零件的生产时间都在3-9天之间，现在只知道每个工人的生产部件有哪些，还有生产日期的星期几和完成日期的星期几，求每个部件的具体生产日期

思路：首先我们根据两个星期，我们实际上可以计算出具体时间，然后我们到每个工人生产零件的数目还有时间，相当于我们可以建立这么多个方程组，然后我们就可以消元得出答案

注意处理3-9天范围的细节即可

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define N 305
char day[][20]={"","MON","TUE","WED","THU","FRI","SAT","SUN"};
int n,m,k,mat[N][N],ans[N];

int gcd(int a,int b)
{
    if(b==0)
        return a;
    else return gcd(b,a%b);
}
bool mul_solu;
bool gauss(int mat[N][N],int m,int n)
{
    mul_solu=false;
    int row,col;
    for(row=0,col=0;row<m && col<n;++row,++col)
    {
        int p=row;
        for(int j=row+1;j<m;++j)
            if(abs(mat[j][col])>abs(mat[p][col]))
                p=j;
        if(p!=row)
        {
            for(int j=0;j<=n;++j)
                swap(mat[row][j],mat[p][j]);
        }
        if(mat[row][col]==0) // 最大的都为0，说明这一列以下全是0
        {
            row--;
            continue;
        }
        for(int j=row+1;j<m;++j)
        {
            int gg=gcd(mat[row][col],mat[j][col]);
            int muli=mat[j][col]/gg%7;
            int mulj=mat[row][col]/gg%7;
            for(int k=col;k<=n;++k)
            {
                mat[j][k]=mat[j][k]*mulj-mat[row][k]*muli;
                mat[j][k]=(mat[j][k]%7+7)%7;
            }
        }
    }
    for(int i=row;i<m;++i) // inconsistent必须先与multiple判断
        if(mat[i][n])
            return false;
    if(row<n) // free variable 少
    {
        mul_solu=true;
        return true;
    }

    for(int i=n-1;i>=0;--i)
    {
        bool flag=false;
        for(int j=3;j<=9;++j)
        {
            int rr=0;
            for(int k=i+1;k<n;++k)
                rr+=mat[k][n]*mat[i][k]%7,rr%=7;
            rr+=j*mat[i][i];
            if(rr%7==mat[i][n])
            {
                mat[i][n]=j;
                flag=true;
                break;
            }
        }
        if(!flag)
            return false;
    }

    return true;
}

int get_time(char *t1,char *t2)
{
    int st,ed;
    for(int i=1;i<=7;++i)
    {
        if(strcmp(t1,day[i])==0)
            st=i;
        if(strcmp(t2,day[i])==0)
            ed=i;
    }
    if(ed-st>=0)
        return ed-st+1;
    else return ed+8-st;
}
char t1[10],t2[10];
int tt;
int main ()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        if(n==0 && m==0) break;
        memset(mat,0,sizeof(mat));
        for(int i=0;i<m;++i)
        {
            scanf("%d%s%s",&k,t1,t2);
            mat[i][n]=get_time(t1,t2)%7;
            for(int j=1;j<=k;++j)
            {
                scanf("%d",&tt);
                mat[i][tt-1]++;
                mat[i][tt-1]%=7;
            }
        }
        if(gauss(mat,m,n))
        {
            if(mul_solu)
            {
                printf("Multiple solutions.\n");
            }
            else
            {
                for(int i=0;i<n-1;++i)
                    printf("%d ",mat[i][n]);
                printf("%d\n",mat[n-1][n]);
            }
        }
        else printf("Inconsistent data.\n");
    }
    return 0;
}