首页 > 程序开发 > 软件开发 > C++ >

uva 1564 - Widget Factory(高斯消元+逆元)

2014-08-19

题目链接:uva 1564 - Widget Factory 题目大意:n种零件,m次工作日程,零件序号从1到n,给出m次工作日程的信息,x,s,e,表示生产了x个零件,从星期s开始到星期e(有可能是多个星期),然后给出生产的x

题目链接:uva 1564 - Widget Factory

题目大意:n种零件,m次工作日程,零件序号从1到n,给出m次工作日程的信息,x,s,e,表示生产了x个零件,从星期s开始到星期e(有可能是多个星期),然后给出生产的x个零件的序号。求每个零件被生产需要多少天(保证在3到10天)

解题思路:因为不能确定每个工作日程具体生产了几天,所以对应列出的方程均为线性模方程(模7),所以在高斯消元的过程中遇到除法要转换成乘上逆元。

#include 
#include 
#include 

using namespace std;

const int maxn = 305;
const int maxd = 7;
const char day[maxd][maxd] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"};
typedef long long ll;
typedef ll Mat[maxn][maxn];

int N, M;
Mat A;

int solve (char *s, char *e) {
    int p = 0;
    while (strcmp(s, day[p])) p++;
    int q = p;
    while (strcmp(e, day[q])) q = (q + 1) % maxd;

    return (q - p + 8) % maxd;
}

void init () {
    int n, x;
    char s[maxn], e[maxn];
    memset(A, 0, sizeof(A));

    for (int i = 0; i < M; i&#43;&#43;) {
        scanf("%d%s%s", &n, s, e);

        for (int j = 0; j < n; j&#43;&#43;) {
            scanf("%d", &x);
            A[i][x-1] = (A[i][x-1] &#43; 1) % maxd;
        }

        A[i][N] = solve(s, e);
    }
}

ll pow_mod(ll x, int n, ll mod) {
    ll ret = 1;

    while (n) {
        if (n&1)
            ret = ret * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ret;
}

ll inv (ll k) {
    return pow_mod(k, maxd-2, maxd);
}

int gauss_elimin (int n, int m) {

    int i = 0, j = 0;

    while (i < m && j < n) {
        int r = i;
        for (int k = i; k < m; k&#43;&#43;) {
            if (A[k][j]) {
                r = k;
                break;
            }
        }

        if (r != i) {
            for (int k = 0; k <= n; k&#43;&#43;)
                swap(A[i][k], A[r][k]);
        }

        if (A[i][j] == 0) {
            j&#43;&#43;;
            continue;
        }

        for (int k = 0; k < m; k&#43;&#43;) {
            if (A[k][j] == 0 || i == k)
                continue;

            ll f = A[k][j] * inv(A[i][j]) % maxd;

            for (int t = j; t <= n; t&#43;&#43;)
                A[k][t] = ((A[k][t] - f * A[i][t]) % maxd &#43; maxd) % maxd;
        }
        i&#43;&#43;;
    }

    for (int k = i; k < m; k&#43;&#43;)
        if (A[k][n])
            return 0;

    if (i < n)
        return 2;


    for (int k = 0; k < n; k&#43;&#43;) {
        A[k][n] = A[k][n] * inv(A[k][k]) % maxd;
        if (A[k][n] < 3)
            A[k][n] &#43;= maxd;
        printf("%lld%c", A[k][n], k == n-1 ? '\n' : ' ');
    }

    return 1;
}

int main () {
    while (~scanf("%d%d", &N, &M) && N) {
        init();
        int type = gauss_elimin(N, M);
        if (type == 0)
            printf("Inconsistent data.\n");
        else if (type == 2)
            printf("Multiple solutions.\n");
    }
    return 0;
}
相关文章
最新文章
热点推荐