题解 SP2883 Widget Factory

· · 题解

首先对题意进行转化，设生产第 i 个零件的时间是 x_i，每一条记录里给出了开始日期和结束日期，对此我们可以算出第 i 条记录里生产这些零件用了多少天 t_i，设在这些天内第 j 个零件生产了 a_{i,j} 个。对此可以得到一个方程。但是这里的天数并不是确定的，而是有可能制作了多周，所以实际时间在模 7 意义下与 t_i 同余。

接下来将 m 条记录的同余方程联立起来，可得一个同余方程组。

\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n\equiv t_1\pmod{7}\\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n\equiv t_2\pmod{7}\\\cdots\\a_{m,1}x_1+a_{m,2}x_2+\cdots+a_{m,n}x_n\equiv t_m\pmod{7}\end{cases}

解同余方程组，可使用类似高斯消元的方法，因为高斯消元中用到的加减乘在模意义下都适用，但是除不行，需要求逆元，这里用不到递推，使用费马小定理即可。直接套消元的板子。

最后得到一堆形式如下的方程

b_ix_i\equiv c_i\pmod{7}

可使用扩展欧几里得求解。但注意到此题 x_i\in\{3,4,5,6,7,8,9\}，可暴力枚举求解。

这里求解大抵结束了，但是还有一车细节。

一、判有解或是无数解。

注意在高斯消元部分中要进行第一次判断，在扩展欧几里得或者暴力枚举中要进行第二次判断。

二、由于题目中 m 与 n 不一定相等，所以进行分类讨论。

三、注意输出时多余的空格。

我的代码中使用了高斯-约旦消元法和暴力枚举。

#include <bits/stdc++.h>
using namespace std;

const int N=305;

int n,m,ok=1,pren;
int a[N][N],ans[N];

int getn(string x){
    if(x=="SUN") return 7;
    if(x=="MON") return 1;
    if(x=="TUE") return 2;
    if(x=="WED") return 3;
    if(x=="THU") return 4;
    if(x=="FRI") return 5;
    if(x=="SAT") return 6;
}

int cal(string a,string b){
    int x=getn(a),y=getn(b);
    return (y+7-x+1)%7;
}

int qp(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans=1ll*ans*a%7;
        a=1ll*a*a%7;
        b>>=1;
    }
    return ans;
}

void gauss(){
    for(int j=1;j<=n;j++){
        int maxn=j;
        for(int i=1;i<=n;i++){
            if(a[i][i]&&i<j) continue;
            if(a[i][j]>a[maxn][j]) maxn=i;
        }
        for(int i=1;i<=n+1;i++){
            swap(a[maxn][i],a[j][i]);
        }
        if(!a[j][j]) continue;
        for(int i=1;i<=n;i++){
            if(i==j) continue;
            int tmp=a[i][j]*qp(a[j][j],5)%7;
            for(int k=1;k<=n+1;k++){
                a[i][k]-=a[j][k]*tmp%7;
                a[i][k]=(a[i][k]+7)%7;
            }
        }
    }
}

int getan(int x,int y){
    int ans=0;
    for(int i=3;i<=9;i++){
        if((x*i)%7==y){
            if(ans) return -2;
            ans=i;
        }
    }
    if(ans!=0) return ans;
    return -1;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    while(1){
        memset(a,0,sizeof(a));
        memset(ans,0,sizeof(ans));
        ok=1;
        cin>>n>>m;
        if(!n&&!m) return 0;
        int nn=max(n,m);
        for(int i=1,k;i<=m;i++){
            string s,t;
            cin>>k>>s>>t;
            a[i][nn+1]=cal(s,t);
            for(int j=1,x;j<=k;j++){
                cin>>x;
                a[i][x]++;a[i][x]%=7;
            }
        }
        pren=n;
        n=nn;
        gauss();
        for(int i=1;i<=n;i++){
            if(!a[i][i]){
                if(a[i][n+1]){
                    ok=-1;
                    break;
                }
                else if(ok!=-1){
                    ok=0;
                }
            }
        }
        if(ok==-1){
            cout<<"Inconsistent data.\n";
        }
        else if(ok==0){
            cout<<"Multiple solutions.\n";  
        }
        else{
            for(int i=1;i<=pren;i++){
                ans[i]=getan(a[i][i],a[i][n+1]);
                if(ans[i]==-1){
                    cout<<"Inconsistent data.\n";
                    ok=-1;
                    break;
                }
                if(ans[i]==-2){
                    cout<<"Multiple solutions.\n";
                    ok=-2;
                    break;
                }
            }
            if(ok!=-1&&ok!=-2){
                for(int i=1;i<=pren;i++){
                    cout<<ans[i]<<(i==pren?"":" ");
                }
            }
            cout<<"\n";
        }
    }
    return 0;
}