首页 > 代码库 > [Gauss]POJ2947 Widget Factory
[Gauss]POJ2947 Widget Factory
题意: 有n种小工具要加工，每种工具的加工时间为3到9天，给了m条加工记录。
每条记录 X s1 s2 分别代表 这个工人在s1到s2(前闭后闭)的时间里加工了X件小工具
下一行给出这X件小工具的种类
要求的是每件工具的加工时间 (唯一解：输出各个时间；无解：Inconsistent data.；多个解：Multiple solutions.)
可以列出同余方程组：∑(ai*xi)≡T(mod 7)
(ai是此人加工第i件物品的个数，xi是第i件物品加工所需的时间，T是此人干活的时间)
这样列出m个同余方程 组成方程组 用高斯消元
比如第一个案例:
2 32 MON THU1 23 MON FRI1 1 23 MON SUN1 2 2
可以列出方程组： 1*x0+1*x1≡4(mod 7)
2*x0+1*x1≡5(mod 7)
1*x0+2*x1≡7(mod 7)
1 1 4 1 1 4 1 0 1
2 1 5 → 1 0 1 → 0 1 3
1 2 7 0 1 3 0 0 0
即得 x0=1，x1=3
由题意 每种工具的加工时间为3到9天
故 x0=8，x1=3
解毕
下面是代码：
有mod就会有要求逆元
两种求逆元的方法
1. extend gcd
注意得到的x可能为负 要x=(x%mod+mod)%mod;
1 void ex_gcd(int a, int b, int &x, int &y) 2 { 3 if(b) 4 { 5 ex_gcd(b, a%b, x, y); 6 int tmp=x; 7 x=y; 8 y=tmp-(a/b)*y; 9 }10 else11 {12 x=1, y=0;13 return ;14 }15 }
2.inverse element
注意 只适用于a<b 并且 ab互质
1 int inv(int a, int b)2 {3 return a==1? 1:inv(b%a, b)*(b-b/a)%b;4 }
此题还有一法不求逆元：
即 把被除数不断加上mod 直到它能被除数整除为止
1 while(tmp%a[i][i]) 2 tmp+=mod; 3 x[i]=(tmp/a[i][i])%mod; 4 5 与以下等价 6 7 int xx, yy; 8 ex_gcd(a[i][i], mod, xx, yy); 9 xx=(xx%mod+mod)%mod;10 x[i]=(tmp*xx)%mod;11 12 与以下等价13 14 x[i]=(tmp*inv(a[i][i], mod))%mod;
完整代码：
1 const int mod=7; 2 int gcd(int a, int b) 3 { 4 return b==0? a:gcd(b, a%b); 5 } 6 int lcm(int a, int b) 7 { 8 return a/gcd(a, b)*b; 9 } 10 void ex_gcd(int a, int b, int &x, int &y) 11 { 12 if(b) 13 { 14 ex_gcd(b, a%b, x, y); 15 int tmp=x; 16 x=y; 17 y=tmp-(a/b)*y; 18 } 19 else 20 { 21 x=1, y=0; 22 return ; 23 } 24 } 25 26 int a[300][300]; // 增广矩阵 27 int x[300]; // 解 28 int free_x[300]; // 标记是否为自由未知量 29 30 int Gauss(int n, int m) // n个方程 m个未知数 即 n行m+1列 31 { 32 //转换为阶梯形式 33 int col=0, k, num=0; 34 for(k=0;k<n && col<m;k++, col++) 35 {//枚举行 36 int max_r=k; 37 for(int i=k+1;i<n;i++)//找到第col列元素绝对值最大的那行与第k行交换 38 if(abs(a[i][col])>abs(a[max_r][col])) 39 max_r=i; 40 if(max_r!=k)// 与第k行交换 41 for(int j=col;j<m+1;j++) 42 swap(a[k][j], a[max_r][j]); 43 if(!a[k][col])// 说明该col列第k行以下全是0了 44 { 45 k--; 46 free_x[num++]=col; 47 continue; 48 } 49 for(int i=k+1;i<n;i++)// 枚举要删除的行 50 if(a[i][col]) 51 { 52 int LCM=lcm(abs(a[i][col]), abs(a[k][col])); 53 int ta=LCM/abs(a[i][col]); 54 int tb=LCM/abs(a[k][col]); 55 if(a[i][col]*a[k][col]<0) 56 tb=-tb; 57 for(int j=col;j<m+1;j++) 58 a[i][j]=((a[i][j]*ta-a[k][j]*tb)%mod+mod)%mod; 59 } 60 } 61 62 for(int i=k;i<n;i++) 63 if(a[i][col]) 64 return -1; // 无解 65 66 if(k<m) //m-k为自由未知量个数 67 return m-k; 68 69 // 唯一解 回代 70 for(int i=m-1;i>=0;i--) 71 { 72 int tmp=a[i][m]; 73 for(int j=i+1;j<m;j++) 74 { 75 if(a[i][j]) 76 tmp-=a[i][j]*x[j]; 77 tmp=(tmp%7+7)%7; 78 } 79 int xx, yy; 80 ex_gcd(a[i][i], mod, xx, yy); 81 xx=(xx%mod+mod)%mod; 82 x[i]=(tmp*xx)%mod; 83 } 84 return 0; 85 } 86 87 88 void init() 89 { 90 memset(a, 0, sizeof(a)); 91 memset(x, 0, sizeof(x)); 92 } 93 94 int change(char c1, char c2) 95 { 96 if(c1==‘M‘) 97 return 1; 98 if(c1==‘T‘ && c2==‘U‘) 99 return 2;100 if(c1==‘W‘)101 return 3;102 if(c1==‘T‘)103 return 4;104 if(c1==‘F‘)105 return 5;106 if(c1==‘S‘ && c2==‘A‘)107 return 6;108 return 7;109 }110 111 char s1[10], s2[10];112 int main()113 {114 int n, m;115 while(~scanf("%d%d", &n, &m))116 {117 if(!n && !m)118 break;119 init();120 for(int i=0;i<m;i++)121 {122 int X;123 scanf("%d%s%s", &X, s1, s2);124 a[i][n]=((change(s2[0], s2[1])-change(s1[0], s1[1])+1)%mod+mod)%mod;125 while(X--)126 {127 int t;128 scanf("%d", &t);129 a[i][t-1]=(a[i][t-1]+1)%mod;130 }131 }132 int t=Gauss(m, n);133 if(t==-1)134 {135 printf("Inconsistent data.\n");136 continue;137 }138 if(t==0)139 {140 for(int i=0;i<n;i++)141 if(x[i]<=2)142 x[i]+=7;143 for(int i=0;i<n;i++)144 {145 printf("%d", x[i]);146 if(i==n-1)147 printf("\n");148 else149 printf(" ");150 }151 continue;152 }153 printf("Multiple solutions.\n");154 }155 return 0;156 }
[Gauss]POJ2947 Widget Factory
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。