分类： 算法

Cow Tours 
Farmer John has a number of pastures on his farm. Cow paths connect some pastures with certain other pastures, forming a field. But, at the present time, you can find at least two pastures that cannot be connected by any sequence of cow paths, thus partitioning Farmer John\'s farm into multiple fields. 
Farmer John would like add a single a cow path between one pair of pastures using the constraints below. 
A field\'s `diameter\' is defined to be the largest distance of all the shortest walks between any pair of pastures in the field. Consider the field below with five pastures, located at the points shown, and cow paths marked by lines: 
 15,15 20,15 
 D E 
 *-------* 
 | _/| 
 | _/ | 
 | _/ | 
 |/ | 
 *--------*-------* 
 A B C 
 10,10 15,10 20,10 
The `diameter\' of this field is approximately 12.07106, since the longest of the set of shortest paths between pairs of pastures is the path from A to E (which includes the point set {A,B,E}). No other pair of pastures in this field is farther apart when connected by an optimal sequence of cow paths. 
Suppose another field on the same plane is connected by cow paths as follows: 
 *F 30,15 
 / 
 _/ 
 _/ 
 / 
 *------ 
 G H 
 25,10 30,10 
In the scenario of just two fields on his farm, Farmer John would add a cow path between a point in each of these two fields (namely point sets {A,B,C,D,E} and {F,G,H}) so that the joined set of pastures {A,B,C,D,E,F,G,H} has the smallest possible diameter. 
Note that cow paths do not connect just because they cross each other; they only connect at listed points. 
The input contains the pastures, their locations, and a symmetric adjacency matrix that tells whether pastures are connected by cow paths. Pastures are not considered to be connected to themselves. Here\'s one annotated adjacency list for the pasture {A,B,C,D,E,F,G,H} as shown above: 
 A B C D E F G H 
 A 0 1 0 0 0 0 0 0 
 B 1 0 1 1 1 0 0 0 
 C 0 1 0 0 1 0 0 0 
 D 0 1 0 0 1 0 0 0 
 E 0 1 1 1 0 0 0 0 
 F 0 0 0 0 0 0 1 0 
 G 0 0 0 0 0 1 0 1 
 H 0 0 0 0 0 0 1 0 
Other equivalent adjacency lists might permute the rows and columns by using some order other than alphabetical to show the point connections. The input data contains no names for the points. 
The input will contain at least two pastures that are not connected by any sequence of cow paths. 
Find a way to connect exactly two pastures in the input with a cow path so that the new combined field has the smallest possible diameter of any possible pair of connected pastures. Output that smallest possible diameter. 
PROGRAM NAME: cowtour 
INPUT FORMAT 
Line 1: An integer, N (1 <= N <= 150), the number of pastures 
Line 2-N+1: Two integers, X and Y (0 <= X ,Y<= 100000), that denote that X,Y grid location of the pastures; all input pastures are unique. 
Line N+2-2*N+1: lines, each containing N digits (0 or 1) that represent the adjacency matrix as described above, where the rows\' and columns\' indices are in order of the points just listed. 
SAMPLE INPUT (file cowtour.in) 
8 
10 10 
15 10 
20 10 
15 15 
20 15 
30 15 
25 10 
30 10 
01000000 
10111000 
01001000 
01001000 
01110000 
00000010 
00000101 
00000010 
OUTPUT FORMAT 
The output consists of a single line with the diameter of the newly joined pastures. Print the answer to exactly six decimal places. Do not perform any special rounding on your output. 
SAMPLE OUTPUT (file cowtour.out) 
22.071068 

描述
农民 John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区通过任何路径都不连通。这样，Farmer John就有多个牧场了。
John想在农场里添加一条路径(注意，恰好一条)。对这条路径有以下限制：
一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。考虑如下的有5个牧区的牧场，牧区用“*”表示，路径用直线表示。每一个牧区都有自己的坐标：

 (15,15) (20,15) 
 D E 
 *-------* 
 | _/| 
 | _/ | 
 | _/ | 
 |/ | 
 *--------*-------* 
 A B C 
 (10,10) (15,10) (20,10) 

这个牧场的直径大约是12.07106, 最远的两个牧区是A和E，它们之间的最短路径是A-B-E。
这里是另一个牧场：

 *F(30,15) 
 / 
 _/ 
 _/ 
 / 
 *------* 
 G H 
 (25,10) (30,10) 

这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。
注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。
输入文件包括牧区、它们各自的坐标，还有一个如下的对称邻接矩阵：

 A B C D E F G H 
A 0 1 0 0 0 0 0 0 
B 1 0 1 1 1 0 0 0 
C 0 1 0 0 1 0 0 0 
D 0 1 0 0 1 0 0 0 
E 0 1 1 1 0 0 0 0 
F 0 0 0 0 0 0 1 0 
G 0 0 0 0 0 1 0 1 
H 0 0 0 0 0 0 1 0 

输入文件至少包括两个不连通的牧区。
请编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。
格式
PROGRAM NAME: cowtour
INPUT FORMAT:
(file cowtour.in)
第1行: 一个整数N (1 <= N <= 150), 表示牧区数
第2到N+1行: 每行两个整数X,Y (0 <= X ,Y<= 100000), 表示N个牧区的坐标。注意每个 牧区的坐标都是不一样的。
第N+2行到第2*N+1行: 每行包括N个数字(0或1) 表示如上文描述的对称邻接矩阵。
OUTPUT FORMAT:
(file cowtour.out)
只有一行，包括一个实数，表示所求直径。数字保留六位小数。
SAMPLE INPUT
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
SAMPLE OUTPUT
22.071068
====================== 华丽的分割线 ======================
实在是不会写, 直接看标程,, 但是标程也好难看懂` 思路是大致是
point是一个结构体, point[i] 表示第i个牧区的坐标:
引用
struct point{
int x, y;
}point[MAX];
用一个数组dis[i][j] 表示从第i个牧区到第j个牧区的最短距离(直接间接的都包括在内.), 然后还有一个数组fie[i]表示第i个牧区所在的牧场编号. diam[i]表示在fie[i]这个牧场里距离i最远的牧区之间的距离是多少.. 也就是说diam[i]表示的是同一个牧场中, 距离i最远的牧区和i之间的距离. fdiam[i] 表示编号为i的牧场的直径.
代码:
C语言:

/*
LANG: C
ID: zqy11001
PROG: cowtour
*/
#include <stdio.h>
#define INF (1e5)
#define MAX (150)
#define getint(i) scanf(%d, &i)

struct point{
 int x, y;
}point[MAX];
double dis[MAX][MAX];
double diam[MAX];
double fdiam[MAX];
int fie[MAX];
int n;

double getdis(int i, int j)
{
 struct point *a, *b;
 a = &point[i];
 b = &point[j];
 return sqrt((double)(a->x - b->x)*
 (a->x - b->x) +
 (double)(a->y - b->y)*
 (a->y - b->y));
}

void mark(int i, int m)
{
 int j;
 if(fie[i] != 0){
 return ;
 }
 fie[i] = m;
 for(j = 0; j < n; j++){
 if(dis[i][j] < INF){
 mark(j, m);
 }
 }
}

int main(void)
{
 int i, j, k;
 int c, now = 1;
 double t, max;
 freopen(cowtour.in, r, stdin);
 freopen(cowtour.out, w, stdout);
 getint(n);
 for(i = 0; i < n; i++){
 getint(point[i].x);
 getint(point[i].y);
 }

 for(i = 0; i < n; i++){
 getchar();
 for(j = 0; j < n; j++){
 c = getchar();
 if(i == j){
 dis[i][j] = 0;
 }else if(c == \'0\'){
 dis[i][j] = INF;
 }else{
 dis[i][j] = getdis(i, j);
 }
 }
 }

 for(i = 0; i < n; i++){
 if(fie[i] == 0){
 mark(i, now++);
 }
 }

 for(k = 0; k < n; k++)
 for(i = 0; i < n; i++)
 for(j = 0; j < n; j++){
 if(dis[i][j] > dis[i][k] + dis[k][j]){
 dis[i][j] = dis[i][k] + dis[k][j];
 }
 }

 for(i = 0; i < n; i++){
 for(j = 0; j < n; j++){
 if(diam[i] < dis[i][j] && dis[i][j] < INF){
 diam[i] = dis[i][j];
 }
 }
 if(fdiam[fie[i]] < diam[i]){
 fdiam[fie[i]] = diam[i];
 }
 }

 max = INF;
 for(i = 0; i < n; i++){
 for(j = 0; j < n; j++){
 if(fie[i] == fie[j]){
 continue;
 }

 t = diam[i] + diam[j] + getdis(i, j);
 if(t < fdiam[fie[i]]){
 t = fdiam[fie[i]];
 }
 if(t < fdiam[fie[j]]){
 t = fdiam[fie[j]];
 }

 if(t < max){
 max = t;
 }
 }
 }
 printf(%.6lf\\n, max);
 return 0;
}

USACO 2.4 Overfencing 穿越栅栏 
Overfencing 
Kolstad and Schrijvers 
Farmer John went crazy and created a huge maze of fences out in a field. Happily, he left out two fence segments on the edges, and thus created two exits for the maze. Even more happily, the maze he created by this overfencing experience is a `perfect\' maze: you can find a way out of the maze from any point inside it. 

Given W (1 <= W <= 38), the width of the maze; H (1 <= H <= 100), the height of the maze; 2*H+1 lines with width 2*W+1 characters that represent the maze in a format like that shown later - then calculate the number of steps required to exit the maze from the `worst\' point in the maze (the point that is `farther\' from either exit even when walking optimally to the closest exit). Of course, cows walk only parallel or perpendicular to the x-y axes; they do not walk on a diagonal. Each move to a new square counts as a single unit of distance (including the move out of the maze. 

Here\'s what one particular W=5, H=3 maze looks like: 

+-+-+-+-+-+ 
| | 
+-+ +-+ + + 
| | | | 
+ +-+-+ + + 
| | | 
+-+ +-+-+-+ 

Fenceposts appear only in odd numbered rows and and odd numbered columns (as in the example). The format should be obvious and self explanatory. Each maze has exactly two blank walls on the outside for exiting. 

PROGRAM NAME: maze1 
INPUT FORMAT 
Line 1: W and H, space separated 
Lines 2 through 2*H+2: 2*W+1 characters that represent the maze 

SAMPLE INPUT (file maze1.in) 
5 3 
+-+-+-+-+-+ 
| | 
+-+ +-+ + + 
| | | | 
+ +-+-+ + + 
| | | 
+-+ +-+-+-+ 

OUTPUT FORMAT 
A single integer on a single output line. The integer specifies the minimal number of steps that guarantee a cow can exit the maze from any possible point inside the maze. 
SAMPLE OUTPUT (file maze1.out) 
9 

The lower left-hand corner is *nine* steps from the closest exit. 

描述
农夫John在外面的田野上搭建了一个巨大的用栅栏围成的迷宫。幸运的是，他在迷宫的边界上留出了两段栅栏作为迷宫的出口。更幸运的是，他所建造的迷宫是一个“完美的”迷宫：即你能从迷宫中的任意一点找到一条走出迷宫的路。给定迷宫的宽W(1<=W<=38)及长H(1<=H<=100)。 2H+1行，每行2W+1的字符以下面给出的格式表示一个迷宫。然后计算从迷宫中最“糟糕”的那一个点走出迷宫所需的步数(就是从最“糟糕”的一点，走出迷宫的最少步数）。（即使从这一点以最优的方式走向最靠近的出口，它仍然需要最多的步数）当然了，牛们只会水平或垂直地在X或Y轴上移动，他们从来不走对角线。每移动到一个新的方格算作一步（包括移出迷宫的那一步）这是一个W=5,H=3的迷宫：

+-+-+-+-+-+ 
| | 
+-+ +-+ + + 
| | | | 
+ +-+-+ + + 
| | | 
+-+ +-+-+-+ 

如上图的例子，栅栏的柱子只出现在奇数行或奇数列。每个迷宫只有两个出口。

格式
PROGRAM NAME: maze1

INPUT FORMAT:

(file maze1.in)

第一行： W和H（用空格隔开）
第二行至第2H+1行： 每行2W+1个字符表示迷宫
OUTPUT FORMAT:

(file maze1.out)

输出一个单独的整数，表示能保证牛从迷宫中任意一点走出迷宫的最小步数。

SAMPLE INPUT 
5 3 
+-+-+-+-+-+ 
| | 
+-+ +-+ + + 
| | | | 
+ +-+-+ + + 
| | | 
+-+ +-+-+-+ 
SAMPLE OUTPUT 
9 

=========================== 华丽的分割线===========================
这一题看网上都说用Flood Fill,, 我感觉的话应该用广搜, 其实仔细想一想, 这一题的广搜等于Flood Fill.
我的思想是, 用广搜, visited[101][40]判重, 从两个起点开始搜索, 这两个点的初始值为1(就是说一步就能到终点). 每搜索到一个就把相应的visited中的值设置为1, 并且把并且把下一个的值加一(在自己的值上)..
代码写好了之后就是不能AC, 提示内存溢出,, 查了好久好久.. 才发现定义变量的时候错了,, 本来我是定义的: visited[40][101], 那么当i > 40的时候就可能溢出!!
大家注意下吧..
代码:
C语言:

/* 
LANG: C 
ID: zqy11001 
PROG: maze1 
*/ 
#include <stdio.h> 
#include <string.h> 

#define getint(i) scanf(%d, &i) 
#define MAX 1000 
#define left 1 
#define right 2 
#define up 4 
#define down 8 
#define isempty() (tail == head) 
#define add(i, a, b) if(map[t.x][t.y] & i){\\ 
 en(a, b, t.t + 1);\\ 
} 

struct node{ 
 int x, y; 
 int t; 
}queue[MAX]; 
int head, tail; 
int visited[101][40]; 
int map[101][40]; 
int w, h; 

void en(int i, int j, int n) 
{ 
 if(tail == (head + 1)%MAX){ 
 exit(-1); 
 } 
 if(i < 1 || i > h || j < 1 || j > w){ 
 return; 
 } 
 if(visited[i][j]){ 
 return; 
 } 
 visited[i][j] = 1; 
 queue[head] = (struct node){i, j, n}; 
 head = (head + 1) % MAX; 
} 

void out(struct node *n) 
{ 
 if(tail == head){ 
 exit(-1); 
 } 
 *n = queue[tail]; 
 tail = (tail + 1)%MAX; 
} 

int main(void) 
{ 
 int i, j, ch; 
 int max = 0; 
 struct node t; 
 freopen(maze1.in, r, stdin); 
 freopen(maze1.out, w, stdout); 
 getint(w); 
 getint(h); 
 for(i = 1; i <= h; i++){ 
 for(j = 1; j <= w; j++){ 
 map[i][j] = 15; 
 } 
 } 

 for(i = 1; i <= 2 * h + 1; i++){ 
 getchar(); 
 for(j = 1; j <= 2 * w + 1; j++){ 
 ch = getchar(); 
 if((i == 1 || i == 2*h+1) && ch == \' \'){ 
 en((i + 1) / 2, j / 2, 1); 
 en(i / 2, j / 2, 1); 
 } 
 if((j == 1 || j == 2*w+1) && ch == \' \'){ 
 en(i / 2, (j + 1)/2, 1); 
 en(i / 2, j / 2, 1); 
 } 
 if(strchr( +, ch) != NULL){ 
 continue; 
 } 
 if(i & 1){ 
 map[(i + 1)/2][j/2] -= up; 
 map[i / 2][j / 2] -= down; 
 }else{ 
 map[i/2][(j+1)/2] -= left; 
 map[i/2][j/2] -= right; 
 } 
 } 
 } 
 while(!isempty()){ 
 out(&t); 
 add(left, t.x, t.y - 1); 
 add(right, t.x, t.y + 1); 
 add(up, t.x - 1, t.y); 
 add(down, t.x + 1, t.y); 
 if(max < t.t){ 
 max = t.t; 
 } 
 } 
 printf(%d\\n, max); 
 return 0; 
}

USACO 2.2 Subset Sums集合
For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical.
For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets are identical:
{3} and {1,2}
This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, … 7} so that each partition has the same sum:
{1,6,7} and {2,3,4,5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways.
Your program must calculate the answer, not look it up from a table.
PROGRAM NAME: subset
INPUT FORMAT
The input file contains a single line with a single integer representing N, as above.
SAMPLE INPUT (file subset.in)
7
OUTPUT FORMAT
The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, …, N}. The output file should contain 0 if there are no ways to make a same-sum partition.
SAMPLE OUTPUT (file subset.out)
4
Description
对于从1到N (1 <= N <= 39) 的连续整数集合，能划分成两个子集合，且保证每个集合的数字和是相等的。举个例子，如果N=3，对于{1，2，3}能划分成两个子集合，他们每个的所有数字和是相等的：
{3} and {1,2}
这是唯一一种分法（交换集合位置被认为是同一种划分方案，因此不会增加划分方案总数）如果N=7，有四种方法能划分集合{1，2，3，4，5，6，7}，每一种分发的子集合各数字和是相等的:
{1,6,7} and {2,3,4,5} {注 1+6+7=2+3+4+5}
{2,5,7} and {1,3,4,6}
{3,4,7} and {1,2,5,6}
{1,2,4,7} and {3,5,6}
给出N，你的程序应该输出划分方案总数，如果不存在这样的划分方案，则输出0。程序不能预存结果直接输出。
Input
输入文件只有一行，且只有一个整数N
Output
输出划分方案总数，如果不存在则输出0。
Sample Input
7
Sample Output
4
刚看到这题完全不知道怎么下手，就是枚举都不知道怎么下手的好，就直接看了看分析：ｎ个数字的累加和为tot，只有当tot为偶数的时候题目才可能有解。一下就有点感觉了，在题目给出的例子中左边的集合的和等于右边的也等于整个集合{1…N}的和的一半，所以只有当tot为偶数的时候才能够有解。
忽然感觉灵光爆满，知道怎么写了，可是仔细想一想，就是枚举我也还是不知道怎么下手的好啊。
今天做出来了, 首先是自己做了一个枚举的, 提交测试一看, 果然第4个测试点超时, 后来看了网上的分析, 其实昨天我就看了分析, 只是没看懂而已, 后来自己的思考, 加上爸爸的一句话的指点, 就弄懂了, 自然而然的AC了.
思路就是一个DP的思路, DP的公式就是：
将数据{1…N}分成两个子集, f[i][j]就表示前i个数能够组合成和是j的个数. 最后要输出的也就是f[n][n*(n+1)/4].
然后DP方程就是： f[i][j] = f[i – 1][j] + f[i – 1][j – i]
意思就是说前i个数能够凑成和为j的个数是, 前i-1个数能够凑成和为j的数加上前i-1个数能够凑成和为j – i的个数. f[i – 1][j] 比较好理解, 但是f[i – 1][j – i]难理解一点, 后者的意思就是说前面i – 1个只需要凑成j – i就够了, 因为第i个数也能够加进来了..
不知道说清楚没有, 总之我是看得懂自己写的这些东西,（貌似是废话..）
但是还有一种情况要考虑阿, 因为这是动态规划, 而且使用两个循环来实习的, 如
for(i = 2; i <= n; i++)
for(j = 1; j <= tot; j++)
…..
在这种情况下, 如果直接把上面的….替换成f[I][j] = f[i – 1][j] + f[i – 1][j – i]就错了（Ps: 我提交的时候就是直接这样子的, 不知道为什么两个网站AC了~), 因为j – i可能会小于0 自然而然是不合法的, 所以需要判断一下, 如果j – i < 0的话f[i][j] = f[i – 1][j]..
C语言:

/*
LANG: C
ID: zqy11001
PROG: subset
*/
#include <stdio.h>

#define min(a, b) ((a) < (b) ? (a) : (b))

int f[40][390];

int main(void)
{
 int n, tot;
 int i, j,t;
 freopen(subset.in, r, stdin);
 freopen(subset.out, w, stdout);
 scanf(%d, &n);
 tot = n*(n + 1) >> 1;
 if(tot & 1){
 printf(\\n);
 return 0;
 }
 tot = tot >> 1;
 f[1][1] = 1;
 for(i = 2; i <= n; i++){
 for(j = 1; j <= tot; j++){
 f[i][j] = f[i - 1][j];
 if(j - i >= 0){
 f[i][j] += f[i - 1][j - i];
 }
 }
 }
 printf(%d\\n, f[n][tot]);
 return 0;
}

Packing Rectangles 铺放矩形块 (IOI 95)

在网上看了挺多解释这一题的文章，总感觉没看大懂，所以自己写一篇文章吧。希望能够帮助大家理解一下这一题。题目如下：

http://www.nocow.cn/index.php/Translate:USACO/packrec

开始拿到题目确实没怎么看懂，网上也有很多人说它是个水题，我倒感觉不以为然，我看了一些网上的人写的代码，说它是水题的人都是怎么写的。整个程序框架就是第一种情况循环+判断，第二种情况循环+判断，…………（以此类推）

接下来我来说下我的做法，（我的语言表达能力却是不强，可能会看不懂，所以如果你看不懂分析的话直接看代码的注释吧。）

对于任何一个矩形都有两种数据：长和宽，然而在这个程序中这方面是最难处理的也就是如何交换长和宽，也就是说在同一个矩形会拥有两种状况——横着摆，竖着摆。我就用srch1这个函数来实现所有矩形长和宽的交换。

接下来就是位置的问题，该把哪个矩形放在哪里面积最小呢呢？当然，这个是看不出来的。所以也需要进行反复的迭代，我用srch2来实现的。

最后再就是判断6种情况（其实只有五种，4和5是一样的）。

（不知道描述清楚没有。）接下来我把代码进行一下简单的注释吧。

C语言: Codee#12439

/*
LANG: C
ID: zqy11001
PROG: packrec
QQ: 328400264
*/
#include <stdio.h>

#define swap(a, b) do{\\
 a ^= b;\\
 b ^= a;\\
 a ^= b;\\
}while(0);
#define max(a, b) ((a)>(b)?(a):(b))

int m;
int ans[300], s1[4], s2[4];
int a[4], b[4];

void update(int x, int y)
{
 if(x * y < m){
 m = x * y;
 memset(ans, 0, sizeof(ans));
 }
 if(x * y == m){
 ans[x] = ans[y] = 1;
 }
}

int box(int x1, int y1, int x2, int y2, int x3, int y3,
 int x4, int y4)
{
 int x, y;
 x = x1 + x2 + x3 + x4;
 y = max(max(y1, y2), max(y3, y4));
 update(x, y);

 x = max(x1, x2 + x3 + x4);
 y = y1 + max(y2, max(y3, y4));
 update(x, y);

 x = x1 + max(x2, x3 + x4);
 y = max(y1, y2 + max(y3, y4));
 update(x, y);

 x = x1 + x4 + max(x2, x3);
 y = max(y1, max(y4, y2 + y3));
 update(x, y);

 x = max(max(x1 + x2, x3 + x4), x1 + x4);
 y = max(max(y1 + y3, y2 + y4), y2 + y3);
 update(x, y);
}

void srch2(int n)
{
 int i;
 if(n == 4){
 box(a[s2[0]], b[s2[0]], a[s2[1]], b[s2[1]],
 a[s2[2]], b[s2[2]], a[s2[3]], b[s23]]);
 }else{
 for(i = 0; i < 4; i++){
 if(!s1[i]){
 s2[n] = i;
 s1[i] = 1;
 srch2(n + 1);
 s1[i] = 0;
 }
 }
 }
}

void srch1(int n)
{
 if(n == 4){
 memset(s1, 0, sizeof(s1));
 srch2(0);
 }else{
 srch1(n + 1);
 swap(a[n], b[n]);
 srch1(n + 1);
 swap(a[n], b[n]);
 }
}

int main(void)
{
 int i, j;
 freopen(packrec.in, r, stdin);
 freopen(packrec.out, w, stdout);
 for(i = 0; i < 4; i++){
 scanf(%d%d, &a[i], &b[i]);
 }
 m = 10000;
 srch1(0);
 j = sqrt(m);
 printf(%d\\n, m);
 for(i = 1; i <= j; i++){
 if(ans[i]){
 printf(%d %d\\n, i, m / i);
 }
 }
 return 0;
}

接下来我对函数一个个进行一下简单的分析吧。
首先

#define swap(a, b) do{\\
 a ^= b;\\
 b ^= a;\\
 a ^= b;\\
}while(0);
#define max(a, b) ((a)>(b)?(a):(b))

这两个宏是很简单的，swap把a和b交换一下位置，max是求两者最大值。

Tip: 对于swap的话，三个异或就能完成问题，这个可能部分读者看不懂，本文是对这个题目的分析，如果看不大懂的话就改成

#define swap(a, b) do{\\
 int t;\\
 t = a;
 a = b;
 b = t;
}while(0);

然后再是对变量进行分析，ans是存储结果用的，因为题目要求输出的时候要从小到大，所以使用ans来存储，输出的时候判断如果当前的值是1的话就输出，不然的话就继续寻找下一个。m是面积最大值。a和b是存储长和宽的。s1和s2到要用的时候再介绍吧。

box函数就是对六种情况算面积，再用update函数来更新m和ans两个全局变量，如果这一种情况求出的面积和m的一样，那么就用这个面积的长和宽来更新ans。如果面积比m还要小，那么将m设置成这个面积，将ans置空，再用长和宽来更新ans。

接下来先介绍srch1吧。

void srch1(int n)
{
 if(n == 4){
 memset(s1, 0, sizeof(s1));
 srch2(0);
 }else{
 srch1(n + 1);
 swap(a[n], b[n]);
 srch1(n + 1);
 swap(a[n], b[n]);
 }
}

这个n表示当前这种方案的下标。

这个函数可以这么理解，

先直接调用一次srch1(n + 1);就是枚举四个矩形用a做底，b做高的所有情况，接下来在把第n个矩形的长和高调一下位置再srch1(n + 1).因为刚刚把第n个矩形的长和高换了位置，所以还要把它换回来。

然后当n==4的时候，四个矩形都递归完了，就该做些什么了，做些什么呢？

继续看就知道了。

调用srch2之前为什么要把s1置0呢`?

看看srch2是怎么写的`

void srch2(int n)
{
 int i;
 if(n == 4){
 box(a[s2[0]], b[s2[0]], a[s2[1]], b[s2[1]],
 a[s2[2]], b[s2[2]], a[s2[3]], b[s2[3]]);
 }else{
 for(i = 0; i < 4; i++){
 if(!s1[i]){
 s2[n] = i;
 s1[i] = 1;
 srch2(n + 1);
 s1[i] = 0;
 }
 }
 }
}

可能有读者要说了，这跟srch1有点像啊.. 好吧, 我承认, 我摘抄了srch1的部分代码，但是srch2的功能未必也是将第n个矩形的长和高交换？肯定不是啦。

当n==4的时候就是真正的进行判断了，所以理解else是重点.本函数的功能是，对四个矩形的长和高调用box的时候的顺序进行反复的交换。所以else里面是一个for循环，这里s1和s2就是用来判断重复的情况的，s1标志当前这个矩形是否已经被使用了？s2标志当前这个矩形的实质是什么？

汗，，自己都没看懂这段话，再理一下。。

s2[i]的意思是第i个矩形实际上是第几个矩形。因为四个矩形要反复的进行交换，所以s2就是交换的中间变量。那有人会问了。

 if(!s1[i]){
 s2[n] = i;
 s1[i] = 1;
 srch2(n + 1);
 s1[i] = 0;
 }

这段是什么意思呢？ 呵呵，你们想想，如果直接

s2[n] = i;

srch2(n + 1);

的话那会有这种可能s2[0] == 0, s2[1] == 0, s2[2]==0, 也就是说在调用box的时候这些矩形分身了。s1在这里就是用来防止这种情况，s1用来标志这一个矩形是否被别的s2给使用了，如果使用了那s1就会是1，那么循环只好继续。

整个程序大概分析完了。。

如果还没看懂，那不是你蠢了，是我没写清楚吧。

总之如果还有问题，联系我的QQ：328400264

这题很简单，一位一位算就是，唯一要注意的就是mod 11 = 10的时候，要用X。代码：

C语言:

#include <stdio.h>
#include <ctype.h>
char isbn[14];

char getint(void)
{
 static int i = 0;
 int t;
 do{
 t = isbn[i++];
 }while(!isdigit(t));
 return t - \'0\';
}

int main(void)
{
 int a = 0;
 int i;
 char t;
 scanf(%s, isbn);
 for(i = 1; i <= 9; i++){
 t = getint();
 a += t * i;
 }
 t = isbn[12];
 a %= 11;
 if(a == 10){
 a = \'X\';
 }else{
 a += \'0\';
 }
 if(t == a){
 printf(Right\\n);
 }else{
 isbn[12] = a;
 printf(%s\\n, isbn);
 }
 return 0;
}

不知道这题该属于哪个类别，，贪心？枚举？反正不难，，代码：

C语言:

#include <stdio.h>

int main(void)
{
 int i;
 int a, b;
 int ans = 0, t = 0;
 for(i = 1; i <= 7; i++){
 scanf(%d%d, &a, &b);
 if((a + b > 8) && (a + b > t)){
 ans = i;
 t = a + b;
 }
 }
 printf(%d\\n, ans);
 return 0;
}

这题的话，怎么说呢？就是暴力！！

C语言:

#include <stdio.h>
int ans[10];

void count(int num)
{
 while(num != 0){
 ans[num % 10]++;
 num /= 10;
 }
}

int main(void)
{
 int i, j;
 scanf(%d%d, &i, &j);
 while(i <= j){
 count(i++);
 }
 for(i = 0; i < 10; i++){
 if(i != 0){
 printf( );
 }
 printf(%d, ans[i]);
 }
 printf(\\n);
 return 0;
}

这题不会做，那你就应该砸机子了。

C语言:

#include <stdio.h>

int main(void)
{
 int i, j;
 scanf(%d%d, &i, &j);
 printf(%d\\n, i + j);
 return 0;
}

开到这个题目，想起了浏览器Lynx，用过两次，太难用了，汗，，貌似跑题了。
整个题目就是要了解一下浏览器的向前向后的特性，浏览器向后几步之后再输入网址就不能够向前浏览了。整个程序我就用一个数组来维护的，额，具体的细节看代码吧：

C语言:

#include <stdio.h>
#include <string.h>
#define MAX 10000
char link[MAX][71];
int tail, now;

void add(char *str)
{
 int t = (now + 1) % MAX;
 if(now == MAX){
 exit(-1);
 }
 strcpy(link[t], str);
 now = t;
 tail = now + 1;
}

char *back(void)
{
 if(now == 0){
 return NULL;
 }
 return link[--now];
}

char *forward(void)
{
 if(now + 1 == tail){
 return NULL;
 }
 return link[++now];
}

void init(void)
{
 tail = 0;
 now = -1;
 add(http://www.acm.org/);
}

int main(void)
{
 char *t;
 char command[8], address[71];

 init();
 while(scanf(%s, command)){
 if(strcmp(command, BACK) == 0){
 t = back();
 if(t == NULL){
 printf(Ignored\\n);
 }else{
 printf(%s\\n, t);
 }
 }else if(strcmp(command, FORWARD) == 0){
 t = forward();
 if(t == NULL){
 printf(Ignored\\n);
 }else{
 printf(%s\\n, t);
 }
 }else if(strcmp(command, VISIT) == 0){
 scanf(%s, address);
 add(address);
 printf(%s\\n, address);
 }else{
 break;
 }
 }

 return 0;
}

这题我就什么都不说了吧，这题不会做你就回去把语言好好学学，学习输入输出的一些空格和换行。

C语言:

#include <stdio.h>
#define getint(i) scanf(%d, &i)

int main(void)
{
 int n, i;
 int t1, t2, t3;
 char c2, c1;
 int tot = 0;
 int max = 0;
 int grade;
 char maname[100], name[100];
 getint(n);
 for(i = 0; i < n; i++){
 grade = 0;
 scanf(%s%d%d %c %c%d\\n, name, &t1, &t2, &c1, &c2, &t3);
 if((t1 > 80) && (t3 > 0)){
 grade += 8000;
 }
 if((t1 > 85) && (t2 > 80)){
 grade += 4000;
 }
 if(t1 > 90){
 grade += 2000;
 }
 if((t1 > 85) && (c2 == \'Y\')){
 grade += 1000;
 }
 if((t2 > 80) && (c1 == \'Y\')){
 grade += 850;
 }
 if(grade > max){
 strcpy(maname, name);
 max = grade;
 }
 tot += grade;
 }
 printf(%s\\n%d\\n%d\\n, maname, max, tot);
 return 0;
}