【大意】
生产一些零件,已知有n种零件,m条记录,
记录只记录了某次生产从周几开始,周几结束,以及生产了哪些产品。
每件商品生产所需天数为3-9天。
求每样产品需要多少天才能完成。
【输入】
多组数据
每组数据第一行n,m
之后m行描述m条记录
其中MON TUE WED THU FRI SAT SUN分别表示周一到周日
每条记录第一个数x表示有x件产品,之后两个日期表示起始和结束时间
接下来一行x个数分别表示生产了哪些产品
输入以0 0结束
【输出】
对于每组数据,若有唯一解,则按产品编号顺序输出该解,若有多解,则输出'Multiple solutions.',若无解则输出'Inconsistent data.'
Sample Input
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
Sample Output
8 3 Inconsistent data.
高斯消元解同余方程组
自己将这个想的过于复杂
因为是同模一个数,实际上就类似于普通的同余高斯方程解方程
对于一条记录,可以列出一条方程
(a1x1+a2x2+...+anxn) mod 7 = k
这里需要注意的是系数需要模下7,否则会溢出
然后就是从第一行往下代入消元了
因为是求整数解,所以求一下两个方程要消元的最小公倍数然后再求,消完元后需要重新模7
理所应当的,如果消元过程中出现之下所有式子某项系数都为0,该项未知数就是自由元
但这并不能说明有多解……
这道题比较麻烦的就是区分多解和无解
若m>n则有一些式子是多余的,他们可能造成无解
所以高斯消元消完后应当验证多余式子是否系数全为0,等式右边是否为0
若存在自由元,将会造成一些式子变成多余的式子,我的方法是先求解,然后倒着带入验证
消成 ax mod 7 = k 的时候,枚举一下x,可能会有多解或无解……这个没注意过是否会有这种情况,但还是判断了一下
写的比较乱……
program poj2947; type equation=array [0..301] of longint; var temp:equation; s1:boolean; n,m,i,j,k,l,s,e,who,ooo,q,p,z:longint; point:array [0..301] of longint; line:array [0..301] of equation; con:array [0..301] of longint; stri:string; function min (a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; function convert (now:string):longint; begin if now='MON' then exit(1); if now='TUE' then exit(2); if now='WED' then exit(3); if now='THU' then exit(4); if now='FRI' then exit(5); if now='SAT' then exit(6); if now='SUN' then exit(7); end; function gcd(a,b:longint):longint; begin if a mod b = 0 then exit(b) else exit(gcd(b,a mod b)); end; function over (a,b:equation):longint; var i:longint; begin for i:=1 to n do if a[i]>b[i] then exit(1) else if a[i]<b[i] then exit(-1); exit(0); end; procedure gauss; begin s1:=false; for i:=1 to n do begin if line[i][i]=0 then for j:=i+1 to m do if line[j][i]<>0 then begin temp:=line[i]; line[i]:=line[j]; line[j]:=temp; ooo:=con[i]; con[i]:=con[j]; con[j]:=ooo; break; end; if line[i][i]=0 then begin s1:=true; continue; end; for j:=i+1 to m do begin if line[j][i]=0 then continue; k:=gcd(line[i][i],line[j][i]); q:=line[j][i] div k; p:=line[i][i] div k; con[j]:=(con[j]*p-con[i]*q) mod 7; if con[j]<0 then con[j]:=con[j]+7; for l:=i to n do begin line[j][l]:=(line[j][l]*p-line[i][l]*q) mod 7; if line[j][l]<0 then line[j][l]:=line[j][l]+7; end; end; end; for i:=1 to m do if (over(line[i],line[0])=0)and(con[i]<>0) then begin writeln('Inconsistent data.'); exit; end; for i:=1 to n do point[i]:=-1; for i:=n downto 1 do begin k:=con[i]; for j:=n downto i+1 do if (point[j]=-1)and(line[i][j]<>0) then break else k:=k-point[j]*line[i][j]; if (point[j]=-1)and(line[i][j]<>0)and(i<>min(n,m)) then continue; if line[i][i]=0 then begin if k mod 7 <>0 then begin writeln('Inconsistent data.'); exit; end; continue; end; k:=k mod 7; if k<0 then k:=k+7; for j:=3 to 9 do if line[i][i] * j mod 7 = k then if point[i]=-1 then point[i]:=j else s1:=true; if point[i]=-1 then begin writeln('Inconsistent data.'); exit; end; end; if s1 then begin writeln('Multiple solutions.'); exit; end; for i:=1 to n do begin write(point[i]); if i<>n then write(' '); end; writeln; end; begin repeat fillchar(line,sizeof(line),0); fillchar(con,sizeof(con),0); readln(n,m); if n=0 then break; for i:=1 to m do begin readln(stri); val(copy(stri,1,pos(' ',stri)-1),k,who); delete(stri,1,pos(' ',stri)); s:=convert(copy(stri,1,pos(' ',stri)-1)); delete(stri,1,pos(' ',stri)); e:=convert(stri); if s<=e then con[i]:=e-s+1 else con[i]:=7-(s-e-1); if con[i]=7 then con[i]:=0; j:=k; while j<>0 do begin read(k); inc(line[i][k]); if line[i][k]>=7 then line[i][k]:=line[i][k]-7; dec(j); end; readln; end; gauss; until false; end.