USACO/ratios

数学

其实就是求解一个线性方程组，这里用向量的语言叙述了。

所求的实际上就是一个最简配比x,y,z,k,使得x(a1,b1,c1)+y(a2,b2,c2)+z(a3,b3,c3)=k(g1,g2,g3) 我们定义$\vec{p}=(a1,b1,c1), \vec{q}=(a2,b2,c2), \vec{r}=(a3,b3,c3), \vec{k}=(g1,g2,g3),$ 有$x*\vec{p}+y*\vec{q}+z*\vec{r}=k*\vec{k}$ 我们用行列式求解这个问题，假设所得系数行列式分别为D1,D2,D3,D,则D=0(要么无解，要么多解，题目说没有任两个向量的线性组合是第三个，所以不成立)或是解不同号的情况则无解,要不然(D1,D2,D3,D)就是一组(x,y,z,k)，只需要用gcd约减下公约数就可以了。O(1);

  Test 1: TEST OK [0.000 secs, 204 KB]
  Test 2: TEST OK [0.000 secs, 208 KB]
  Test 3: TEST OK [0.000 secs, 204 KB]
  Test 4: TEST OK [0.000 secs, 204 KB]
  Test 5: TEST OK [0.000 secs, 204 KB]
  Test 6: TEST OK [0.000 secs, 204 KB]

oibh上leokan牛讲的不错，而且是中文的 查看

高斯消元+枚举目标量

从小到大枚举目标量，遇到有解输出结束，详情看C++。----消逝者

  Test 1: TEST OK [0.000 secs, 3176 KB]
  Test 2: TEST OK [0.000 secs, 3176 KB]
  Test 3: TEST OK [0.000 secs, 3176 KB]
  Test 4: TEST OK [0.000 secs, 3176 KB]
  Test 5: TEST OK [0.000 secs, 3176 KB]
  Test 6: TEST OK [0.000 secs, 3176 KB]

---

克莱姆法则

克莱姆法则,判断是否是分数解或者负解。枚举一下最后一个输出数的倍数即可。 -- yuhc

请问为何是枚举到100？题目只说了每种配料最多到100啊。

基于分数表示的高斯消元

虽然比较复杂,某人大概写了170行,但几乎不需要用到什么特殊的理论知识,时间复杂度O( n^3 ).

  Test 1: TEST OK [0.000 secs, 284 KB]
  Test 2: TEST OK [0.000 secs, 288 KB]
  Test 3: TEST OK [0.011 secs, 288 KB]
  Test 4: TEST OK [0.000 secs, 288 KB]
  Test 5: TEST OK [0.000 secs, 288 KB]
  Test 6: TEST OK [0.000 secs, 284 KB]

枚举

只用简单的穷举也可以，只有100^3=1000000,约0.3~0.4s 注意0的情况！

枚举i=0..99.j=0..99,k=0..99。i,j,k分别为三种饲料的份数。当三种饲料恰能构成目标饲料时，记录，保留最小值

很简单的算法，运行也很快

  Test 1: TEST OK [0.032 secs, 2840 KB]
  Test 2: TEST OK [0.022 secs, 2836 KB]
  Test 3: TEST OK [0.032 secs, 2836 KB]
  Test 4: TEST OK [0.032 secs, 2840 KB]
  Test 5: TEST OK [0.011 secs, 2836 KB]
  Test 6: TEST OK [0.022 secs, 2836 KB]

枚举total,i,j会好一点，k=total-i-j,这样不用记录最小数 ——by George-Gate

可用 comp[0]*goal[1]==comp[1]*goal[0] 判断是否线性相关，包含0的情况。Skyxxzc 19:55 2011年11月1日 (CST)

参考代码

C

C++

Pascal

Java

引用

[1]

[2]