【NOIP2012模拟11.6】混合

Time Limits: 1000 ms Memory Limits: 65536 KB

Description

现在有 a,b,c 三种物品，如果他们安 x:y:z 混合，就能产生一种神奇的物品 D 。 当然不一定只产生一份 D ，但 a,b,c 的最简比一定是 x:y:z 现在给你 3 种可供选择的物品 A,B,C :A,B,C 都是由 a,b,c 以一定比例组合成的 ， 求出最少的物品数 ， 使得他们能凑出整数个 D物品（这里的最少是指三者个数的总和最少）

Input 第一行三个整数，表示 d 的配比（ x,y,z ） 接下来三行，表示 A,B,C 的配比，每行三个整数（ <=10000 ） 。

Output 四个整数，分别表示在 A+B+C 最 小 的前提下 A,B,C ,D 的个数 目标答案 <=10000 如果不存在满足条件的方案，输出 NONE

Sample Input

3 4 5 1 2 3 3 7 1 2 1 2

Sample Output

8 1 5 7

Hint

50% 的数据保证答案中任意一个数 <=100100% 的数据保证答案中任意一个数 <=10000

---

解题思路

---

50%的数据，就不用说了吧，直接暴力枚举。 O(100^3)

var a:array[1..3,1..4]of longint; i,j,k,x,y,z,l,max,ax,ay,az,ar:longint; p:boolean; begin max:=maxlongint; read(a[1,4],a[2,4],a[3,4]) for i:=1 to 3 do read(a[1,i],a[2,i],a[3,i]); for i:=0 to 100 do for j:=0 to 100 do for k:=0 to 100 do if (i<>0)or(j<>0)or(k<>0) then begin x:=a[1,1]*i+a[1,2]*j+a[1,3]*k; y:=a[2,1]*i+a[2,2]*j+a[2,3]*k; z:=a[3,1]*i+a[3,2]*j+a[3,3]*k; l:=x div a[1,4]; if a[1,4]*l=x then if a[2,4]*l=y then if a[3,4]*l=z then if i+j+k<max then begin max:=i+j+k;p:=true; ax:=i;ay:=j;az:=k;ar:=l; end; end; if p then writeln(ax,' ',ay,' ',az,' ',ar) else writeln('NONE'); end.

那么100%如何解决？

这就用到了一个新的数学方法——高斯消元。

高斯消元，就是用来解方程组的，它的时间复杂度O(n^3)还是挺优美的(谁说它不优美的！？一百元一次方程组你用手解啊！！)。

高斯消元的基本思想就是加减消元法，对于n个方程组成的n元方程组，我们对其先消掉第一元，转化为n-1元方程组；然后再消第二元，转化为n-2次方程组，以此类推……

高斯消元的基本流程如下： 假设有方程组： 3x+y+2z=7 2x-3y+5z=23 x+4y+2z=-1 我们只保留系数，即：

3 1 2 7 2 -3 5 23 1 4 2 -1

为了消除第一元，我们应先统一第一元的系数为它们的最小公倍数：

6 2 4 14 6 -9 15 69 6 24 12 -6

然后消去第一元(拿第一行减后面的)：

6 2 4 14 0 11 -11 -55 0 -22 -8 20

将第二行到第三行统一系数：

6 2 4 14 0 -22 22 110 0 -22 -8 20

消第二元：

6 2 4 14 0 -22 22 104 0 0 30 90

最后发现，30z=90，z=3，将z=3带入-22y+22z=104，-22y=44，y=-2,将z=3，y=-2带入6x+2y+4z=6，6x=6，x=1 所以方程组的解为 x=1 y=-2 z=3

统一系数的目的是为了把这个元消掉，而并不是将所有的东西求最小公倍数，假如遇到当前元系数为0的，可以不管它，因为这一条算式就相当于这个元被消掉了。

高斯消元就是利用这样的思路，在n^3的复杂度求解。

现在我们再以高斯消元的思路来想一想这一道题：

A的配比为aA:bA:cA，不妨设用了x个A A的配比为aB:bB:cB，不妨设用了y个B A的配比为aC:bC:cC，不妨设用了z个C 最后合成的原料配比为aD:bD:cD，假设能产生k个。 于是就列下了方程组： aA * x+aB * y+aC * z=aD * k bA * x+bB * y+bC * z=bD * k cA * x+cB * y+cC * z=cD * k 最后我们可以求出?z=!k，这里?和!都是很奇怪的数。接着我们枚举z求出x，y，k，最后求答案就可以了。

Codes:

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; long long f[3][4],ansx=100000,ansy=100000,ansz=100000,ansk; bool p=1; long long Gcd(long long x,long long y){return((y==0)?x:Gcd(y,x%y));} long long GetLcm(long long x,long long y){return(x*y/Gcd(x,y));} int main() { for(int i=0;i<4;i++)for(int j=0;j<3;j++)scanf("%lld",&f[j][(i+3)%4]); for(int o=0;o<2;o++) { long long lcm=1; for(int i=o;i<3;i++)if(f[i][o]!=0) { lcm=GetLcm(abs(f[i][o]),lcm); } for(int i=o;i<3;i++)if(f[i][o]!=0) { int modu=lcm/f[i][o]; for(int j=o;j<=3;j++)f[i][j]*=modu; } for(int i=o+1;i<3;i++)if(f[i][o]!=0) for(int j=o;j<=3;j++)f[i][j]-=f[o][j]; } long long temp=Gcd(f[2][2],f[2][3]),tempz=f[2][2]/temp,tempk=f[2][3]/temp; for(int z=tempk;z<=10000;z+=tempk) { long long k=z/tempk*tempz,y,x; if((f[1][3]*k-f[1][2]*z)%f[1][1]==0)y=(f[1][3]*k-f[1][2]*z)/f[1][1];else continue; if((f[0][3]*k-f[0][2]*z-f[0][1]*y)%f[0][0]==0)x=(f[0][3]*k-f[0][2]*z-f[0][1]*y)/f[0][0];else continue; if(x>10000 || y>10000 || z>10000 || k>10000)continue; if(x<0 || y<0 || z<0 || k<0)continue; p=0; if(ansx+ansy+ansz>x+y+z) { ansx=x;ansy=y;ansz=z;ansk=k; } } if(p)printf("NONE");else printf("%lld %lld %lld %lld",ansx,ansy,ansz,ansk); }