usaco银组解题报告
一．石子游戏
如果把‘O’当作0，‘X’当做1，则N个洞的每一种状态都可以看做是一个N位二进制数。于是，这个问题就变成了求环绕的N位格雷码。幸运的是，这个结构很容易就能够用一个简单的递归式计算出来。
假设我们有一组K位格雷码序列，第一个为K个0. 我们可以复制这个格雷码序列，并将其倒序，然后将它加在原来的格雷码序列之后。现在，在原来的格雷码序列中的每个数之前都加上数字0，而在复制的序列中每个数的前面都加上1。然后，结果序列就将称为一个有效的k+1位的格雷码。这儿是一个K=2的例子。
1. 原来的格雷码序列，K=2
00
01
11
10
2. 复制并倒序，然后加在原来序列的后面。
00
01
11
10
10
11
01
00
3. 在前面加一个数字。
000
001
011
010
110
111
101
100
如果我们使用这种构造方法，得到的以100……00结尾的序列正是我们想要的。这种算法的时间复杂度是O(2^N)，因为每一个数都是从其他的地方精确的复制过来，每一次复制都花费一个常数时间。
下面给出这个问题的一个简单的以位运算实现的源程序。
01 /*
02 LANG: C++
03 Coded by Jaehyun park
04 */
05
06 #include<cstdio>
07 int n;
08 int a[1<<15+1];
09 int main() {
10 int i, j, k;
11 FILE *ifp=fopen("rocks.in", "r"), *ofp=fopen("rocks.out", "w");
12 fscanf(ifp, "%d", &n);
13 for(k=0;k<n;k++)
14 for(i=0;i<(1<<k);i++)
15 a[(1<<(k+1))-i-1]=a[i]|(1<<k);
16 for(i=0;i<=(1<<n);i++) {
17 for(j=0;j<n;j++)
18 fprintf(ofp, "%c", a[i]&(1<<j)?'X':'O');
19 fprintf(ofp, "
");
20 }
21 return 0;
22 }
2.考试
考察下面给出的三种情况：
1. 设t_max为所有t_i的最大值。不管其他的t_i的值为多少，FJ能够保证N-t_max个正确答案，他只需全部选择false。
2. 设t_min为所有t_i的最小值。不管其他的t_i值为多少，FJ能够保证t_min个正确答案，他只需全部选择true。
3. 将所有按从大到小排序，t_i设t_x 和 t_y是相邻的两个t_i（t_x>t_y）,FJ可以保证（t_x-t_y）/2个正确答案，他只需选择N-[(t_x+t_y)/2]个正确答案，其余全部选择false。
这是一个例子：
|----->120
|--------->200
|---------------->340
|-------------------->420
|--------------------------------->680
|--------------------------------------->800
0 |----+----+----+----+----+----+----+----+----+----| 1000
总共有1000个题，答案为true的题分别为120，200，340，420，680，800，1000.我们将它们排序后，再来查看相邻的数据。
Case1：1000 - 800 = 200个正确答案可以保证，只需全部选false。
Case2：120个正确答案可以保证，只需要全部选true。
Case3：对于相邻的两个值420和680，(680 - 420) / 2 = 130个正确答案可以保证，只需要选择1000 - [(680 + 420) / 2] = 450个true。因为，如果有420个为true的答案，可以保证1000-420-450=130个false选择正确，而如果有680个true，也能保证有680+450-1000个true被选中。
现在，我们可以通过排序然后检查相邻值的差来解决这个问题。比较三种情形，找出其中最大的就行了。从上面这个例子，我们可以得到答案是200.
下面给出源代码：
01 #include <iostream>
02 #include <algorithm>
03 #include <memory.h>
04 using namespace std;
05
06 int a[10100];
07
08 int main () {
09 FILE* in = fopen ("teststr.in", "r");
10 FILE* out = fopen ("teststr.out", "w");
11
12 int N, K;
13 fscanf (in, "%d %d", &N, &K);
14
15 for (int i = 0; i < K; i++) {
16 int v; fscanf (in, "%d", &v);
17 a[i] = N - v;
18 }
19 sort (a, a + K);
20
21 int best = a[0];
22 for (int i = 0; i < K-1; i++)
23 best = max (best, (a[i+1] - a[i]) / 2);
24 best = max (best, N - a[K-1]);
25 fprintf (out, "%d ", best);
26
27 fclose (in);
28 fclose (out);
29 }
三．赛车
在这道题中，关键就是下面这个结论：
对于任意的i和j，如果
F F_i F_j
--- < ----- < -----
M M_i M_j
则有
F F + F_i F + F_j
--- < --------- < ---------
M M + M_i M + M_j
换句话说，配件的加速性能越好，那么它加到汽车上，给车子带来的加速性能也越好。于是，解决方案就是按配件的加速性能（F_i/M_i）从高到低一个个加到汽车上，直到汽车的加速性能不能再提升为止。因为配件的数目N很大，所以对于配件按加速性能的排序要控制在O(N log N)的时间复杂度以内。否则，如果是O(N^2)的话，可能会超时。
例如，排序后的配件如下：
i F_i M_i F_i/M_i F/M
4 200 8 25.0 15.7407
3 120 5 24.0 16.1062
2 150 9 16.7 16.1475 <-- stop adding parts here
1 250 25 10.0 15.1020
上面的F/M列显示了最后的加速性能及对应的配件。我们一次增加配件4，3，2，再增加了配件2以后，再增加配件1已经不能提高车子的加速性能了，相反还会下降到15.1020.
下面给出源程序：
01 #include <fstream>
02 #include <algorithm>
03 #define MAX 10000
04 using namespace std;
05
06 int M,N;
07 double F;
08 bool mark[MAX+1];
09
10 struct Boost {
11 int id, m;
12 double f;
13 bool operator<(const Boost& y) const
14 { return f*y.m > y.f*m; }
15 } p[MAX];
16
17 int main () {
18 ifstream fin("sboost.in");
19 fin >> F >> M >> N;
20 for (int i=0; i<N; p[i].id=++i)
21 fin >> p[i].f >> p[i].m;
22 fin.close();
23
24 bool add=false;
25 // sort accelerations of the boosters
26 sort(p,p+N);
27 // take the booster if new acceleration is greater than current
28 for (int i=0; i<N; i++)
29 if (F/M < (F+p[i].f)/(M+p[i].m))
30 F+=p[i].f, M+=p[i].m, mark[p[i].id]=true, add=true;
31
32 ofstream fout("sboost.out");
33 if (!add)
34 fout << "NONE ";
35 else
36 for (int i=1; i<=N; i++)
37 if (mark[i]) fout << i << " ";
38 fout.close();
39 }