首页 > 代码库 > POJ2947Widget Factory(高斯消元解同模方程)

POJ2947Widget Factory(高斯消元解同模方程)

2024-07-16 19:11:47   221人阅读

http://poj.org/problem?id=2947

题目大意：有n 种装饰物，m 个已知条件,每个已知条件的描述如下：
p start end
a1,a2......ap (1<=ai<=n)
第一行表示从星期start 到星期end 一共生产了p 件装饰物(工作的天数为end-start+1+7*x,
加7*x 是因为它可能生产很多周)，第二行表示这p 件装饰物的种类(可能出现相同的种类，
即ai=aj)。规定每件装饰物至少生产3 天，最多生产9 天。问每种装饰物需要生产的天数。
如果没有解，则输出“Inconsistent data.”，如果有多解，则输出“Multiple solutions.”，如果
只有唯一解，则输出每种装饰物需要生产的天数。
解题思路：高斯消元。设每种装饰物需要生产的天数为xi(1<=i<=n)。每一个条件就相当于
给定了一个方程式，假设生产1 类装饰物a1 件、2 类装饰物a2 件、i 类装饰物ai 件所花费
的天数为b，则可以列出下列方程：
a1*x1+a2*x2+...an*xn = b (mod 7)
这样一共可以列出m 个方程式，然后使用高斯消元来解此方程组即可。
 
  1 #include <map>  2 #include <set>  3 #include <stack>  4 #include <queue>  5 #include <cmath>  6 #include <ctime>  7 #include <vector>  8 #include <cstdio>  9 #include <cctype> 10 #include <cstring> 11 #include <cstdlib> 12 #include <iostream> 13 //#include <algorithm> 14 using namespace std; 15 #define INF 0x3f3f3f3f 16 #define inf ((LL)1<<40) 17 #define lson k<<1, L, mid 18 #define rson k<<1|1, mid+1, R 19 #define mem0(a) memset(a,0,sizeof(a)) 20 #define mem1(a) memset(a,-1,sizeof(a)) 21 #define mem(a, b) memset(a, b, sizeof(a)) 22 #define FOPENIN(IN) freopen(IN, "r", stdin) 23 #define FOPENOUT(OUT) freopen(OUT, "w", stdout) 24 template<class T> T ABS ( T a) { return a >= 0 ? a : -a;   } 25 template<class T> T CMP_MIN ( T a, T b ) { return a < b;   } 26 template<class T> T CMP_MAX ( T a, T b ) { return a > b;   } 27 template<class T> T MAX ( T a, T b ) { return a > b ? a : b; } 28 template<class T> T MIN ( T a, T b ) { return a < b ? a : b; } 29 template<class T> T GCD ( T a, T b ) { return b ? GCD ( b, a % b ) : a; } 30 template<class T> T LCM ( T a, T b ) { return a / GCD ( a, b ) * b;     } 31 template<class T> void SWAP( T& a, T& b ) { T t = a; a = b;  b = t;     } 32  33 typedef __int64 LL; 34 //typedef long long LL; 35 const int MAXN = 310; 36 const int MAXM = 110000; 37 const double eps = 1e-14; 38 const double PI = 4.0 * atan(1.0); 39  40 char str[7][10] = {"MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"}; 41  42 int findNum(char *s) 43 { 44     for(int i = 0; i < 7; i ++ ) 45     { 46         if(strcmp(str[i], s) == 0) return i; 47     } 48     return 0; 49 } 50 int n, m, k, cnt[MAXN]; 51 int var, equ, a[MAXN][MAXN], ans[MAXN]; 52  53 void init() 54 { 55     int x; 56     char st[10], ed[10]; 57     mem0(a); 58     var = n; 59     equ = m; 60     for(int i = 0; i < m; i ++ ) 61     { 62         mem0(cnt); 63         scanf("%d %s %s", &k, st, ed); 64         for(int j = 0; j < k; j ++ ) 65         { 66             scanf("%d", &x); 67             cnt[x-1] ++; 68         } 69         a[i][var] = findNum(ed) - findNum(st) + 1; 70         for(int j = 0; j < var; j ++ ) 71             a[i][j] = cnt[j] % 7; 72     } 73 } 74  75 void exgcd(int a, int b, int& x, int& y) 76 { 77     if(!b) { x = 1; y = 0; } 78     else { exgcd(b, a % b, y, x); y -= x*(a/b); } 79 } 80  81 int gauss() 82 { 83     int x, y; 84     int k, col = 0; 85     for(k = 0; k < equ && col < var; k ++, col ++) 86     { 87         int Max = 0, row = -1; 88         for(int r = k ; r < equ; r ++) 89         { 90             if( Max < ABS(a[r][col]) ) 91                 Max = ABS( a[r][col] ), row = r; 92         } 93         if(row == -1) 94         { 95             k--; 96             continue; 97         } 98         for(int c = col; c <= var; c ++) 99             SWAP(a[k][c], a[row][c]);100         for(int r = k + 1; r < equ; r ++)101         {102             if(a[r][col])103             {104                 int lcm = LCM(ABS(a[k][col]), ABS(a[r][col]));105                 int ta = lcm / a[r][col];106                 int tb = lcm / a[k][col];107                 if(a[r][col] * a[k][col] < 0) tb = -tb;108                 for(int c = col; c <= var; c ++ )109                 {110                     a[r][c] = a[r][c] * ta - a[k][c] * tb;111                     a[r][c] = (a[r][c] % 7 + 7) % 7;112                 }113             }114         }115     }116     for(int r = k; r < equ; r ++)117     {118         if(a[r][var]) return -1;119     }120     if(k < var) return 1;121     for(int r = var - 1; r >= 0; r --)122     {123         int tmp = a[r][var];124         for(int c = var - 1; c > r; c -- )125         {126             tmp -= ans[c] * a[r][c] % 7;127         }128         tmp = (tmp % 7 + 7) % 7;129         exgcd(a[r][r], 7, x, y);130         ans[r] = (tmp * x % 7 + 7) % 7;131         if(ans[r] < 3) ans[r] += 7;132     }133     return 0;134 }135 136 int main()137 {138     //FOPENIN("in.txt");139     while(~scanf("%d %d", &n, &m) && (n || m))140     {141         init();142         int free_num = gauss();143         if(free_num == -1)144         {145             printf("Inconsistent data.\n");146         }147         else if(free_num == 1)148         {149             printf("Multiple solutions.\n");150         }151         else152         {153             for(int i = 0; i < var; i ++ )154             {155                 printf("%d%c", ans[i], i == var-1 ? ‘\n‘ : ‘ ‘);156             }157         }158     }159     return 0;160 }

 


联系
我们