集训队作业程序sgu

1、SGU306 Balance 解题浙江省杭州二中骞题目大意：n 个球中有一个是坏的，重量和其它不一样，其它的重量都是一样的。现在有一个天平，请给出一种称球的方案，使得情况下，称出坏球的次数最小。方法：因为天平每一次会返回三种结果相等、左边重、右边重，而一共的状态有 2*n 种（n个球，轻重两种情况），所以要称出哪个球轻了或者重了的次数下限是有了标准球之后1、当前的球没有被称过。那么好象回到了初始时的状态，但其实这时已经拥有了标准球，可以应付有3k+1 个球的情况。那就是用 k+1 个球和 k 个球加一个标准球去称，这样，如果平衡，状态只剩下了 2k；如果一边轻或者重，状态也只剩下了 2k+1。

2、这样就满足了 3 分的条件。还有一个问题，那就是现在有 m+1 个球，本来应该有 2m+2 种状态，但希望这里只有 2m+1种状态。其实，假设其中的第 m+1 个球，只有一种状态，要么好的，要么坏的，这样总的状态数就只有 2m+1 了。这样所对应的策略就是都不将第 m+1 个球放上天平，那么如果最后只剩余了这个球，本来有两种状态轻或者重，但是这里是坏的，而不管它是轻是重。直接输出这个球2、有 m+n 个已经在天平上称过的球，其中的 m 个要么是好的，要么是轻的；另外的 n个要么是好的，要么是重的。此时又要分几种小情况来。1）m=3p，n=3q 时，那么从可能轻的 3p 中选出 p 个放在 A

3、组中，选 p 个放在 B 组中，再从可能重的 3q 中选出 q 个放在 A 组中，选 q 个放在 B 组中。然后称A 和 B，如果 A 比 B 重，那么显然要么是轻的放在 B 中的p 个有问题，要么是重的放在A 中的q 个有问题，这样的剩余状态是 p+q，满足条件。同理，A 比 B 轻也满足条件。如果 A 和 B 一样中，那就是 A 中没有称的 p 个或者 B 中没有称的q 个有问题，同样满足条件。2）m=3p+1, n=3q+1。此时，希望称一次后剩余状态不超过 p+q+1。这里就要借助标准球。将 m 中的 p+1 和 p 个分别放在 A 和 B 组中，把 n中的 q 和 q 个分别放在 A

4、 和 B 组中，由于 A 和 B 组中球个数不一样，所以须在 B 中补一个标准球。此时，就能满足条件了。那么同理，m 模 3 有 3 种情况，n 模 3 有 3 种情况，它们的组合一共有 9 种情况。其他的几种就不在这里详细说明，具体可以参考程序或者自己思考。程序#include #include #include n, standard;void prSet(*A)prf(%d, A1);for(i=2; i=A0; i+)prf(+%d, Ai);void check(*a)if (aa0 = standard) a0-;void make2(*A,*B,d);void make3(*A,

5、d)if (A0 = 1)for(i=0; id; i+) prf( );prf(fake %dn, A1);return;*a = newA0/3+2, *b = newA0/3+2, *c = newA0/3+2;a0 = b0 = c0 = 0;for(i=1; i=A0/3; i+)a+a0 = Ai;b+b0 = Ai+A0/3;c+c0 = Ai+A0/3*2;if (A0%3 = 1)a+a0 = AA0;b+b0 = standard;else if (A0%3 = 2)a+a0 = AA0-1;b+b0 = standard; c+c0 = AA0;for( pr pr pr

6、 prpri=0; i 0)for(i=0; id; i+) prf();prf(case 0)for(i=0; i 0)for(i=0; i:n);make2(b, a, d+1);for(i=0; id; i+) prf();prf(endn);void prSet2(*c = new c0 = 0;*a,*b)a0+b0+1;for(i=1; i=a0; i+)c+c0 = ai;i=1; i=b0; i+)c+c0 = bi;for(prSet(c);delete c;void make2(*A,*B,d)if (A0+B0 = 1)for(i=0; i 0) prf(%dn, A1)

7、;else prf(%dn, B1); return;*alfa = newA0/3+2, *beta = newA0/3+2, *gama = newA0/3+2;alfa0 = beta0 = gama0 = 0;*a = newB0/3+2, *b = newB0/3+2, *c = newB0/3+2;a0 = b0 = c0 = 0;for(i=1; i=A0/3; i+)alfa+alfa0 = Ai;beta+beta0 = Ai+A0/3; gama+gama0 = Ai+A0/3*2;for(i=1; i=B0/3; i+)a+a0 = Bi;b+b0 = Bi+B0/3;c

8、+c0 = Bi+B0/3*2;if (A0%3 = 0 & B0%3 = 1) c+c0 = BB0;else if (A0%3 = 0 & B0%3 = 2)a+a0 = BB0-1;b+b0 = standard; c+c0 = BB0;else if (A0%3 = 1 & B0%3 = 1)alfa+alfa0 = AA0; b+b0 = standard; c+c0 = BB0;else if (A0%3 = 1 & B0%3 = 2)gama+gama0 = AA0;a+a0 = BB0-1;b+b0 = BB0;else if (A0%3 = 2 & B0%3 = 2)alfa

9、+alfa0 = AA0-1;beta+beta0 = AA0;a+a0 = BB0-1;b+b0 = BB0;else if (A0%3 = 1 & B0%3 = 0)gama+gama0 = AA0;else if (A0%3 = 2 & B0%3 = 0)alfa+alfa0 = AA0-1;beta+beta0 = standard;gama+gama0 = AA0;else if (A0%3 = 2 & B0%3 = 1)c+c0 = BB0;alfa+alfa0 = AA0-1;beta+beta0 = AA0;for( pr pr pr prpri=0; i 0)for(i=0;

10、 id; i+) prf();prf(case 0)for(i=0; i 0)for(i=0; i:n);make2(beta, a, d+1);delete alfa, delete beta, delete gama; delete a, delete b, delete c;for(i=0; id; i+) prf( );prf(endn);void make1(n)*A = newn/3+2, *B = new if (n%3 = 0)A0 = B0 = C0 = 0;for(i=1; i=n/3; i+)A+A0 = i;B+B0 = i+n/3; C+C0 = i+n/3*2;el

11、se if (n%3 = 1)A0 = B0 = C0 = 0;for(i=1; i=n/3; i+)A+A0 = i;B+B0 = i+n/3; C+C0 = i+n/3*2;C+C0 = n;else if (n%3 = 2)A0 = B0 = C0 = 0;for(i=1; i=n/3; i+)A+A0 = i;B+B0 = i+n/3; C+C0 = i+n/3*2;A+A0 = n-1;B+B0 = n;n/3+2, *C = newn/3+2;pr pr pr pr prprf(weigh ); Set(A);f( vs ); Set(B);f(n);f(case :n); standard = C1; make2(B, A, 1);delete A, delete