8
26
2012
1

构造式枚举:Prime Palindromes

在解决PackingRectangles这个问题的时候我强调枚举时要“将粗暴进行到底”,但并不是说可以无限度“粗暴”,当粗暴会导致TLE时,适当地构造解空间往往能大大优化程序的执行时间。


The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .


区间上限是1亿,如果我们直接枚举所有数据并检验是否是回文和素数会超时,实际上我们可以先构造出所有的回文数再检测他们是否是素数,n以内的回文数是很稀疏的,构造回文时我们只需枚举各个数位就可以了,这可以用o(√n)时间完成,另外检测n是否是素数的时间是o(√n),所以我们得到了一个o(n)的方法。

进化:

通过PackingRectangles和此问题,我们涉及到了构造和枚举的问题,过度构造会增加编程的复杂度,过度枚举又会超时,这就需要贴切的时间分析来选择了。在可接受的时间之内尽量减少构造,保持K.I.S.S(keep it simple and stupid)原则是个很好的方法。

点击查看我的程序源码:

/*
ID: *******
LANG: C++
TASK: pprime
*/
#include<stdio.h>
#include<stdlib.h>

int a,b;
FILE *fin,*fout;

typedef struct{
	int digital[9];
}Num;

bool isPrime(int n){
	int i;
	for(i=2;i*i<=n;i++)
		if(n%i==0)
			return false;
	return true;
}

void createPalinAndTest(int n,int L,Num num){//构造长度L的回文数
	int i;
	if(L%2==0&&n>L/2 || L%2==1&&n>L/2+1){
		//利用前一半构造整个回文数并且检测是否是素数
		for(i=n;i<=L;i++)
			num.digital[i-1]=num.digital[1+L-i-1];
		int t=1,N=0;
		for(i=0;i<L;i++){
			N+=t*num.digital[i];
			t*=10;
		}
		if(N<=b&&N>=a&&isPrime(N)){
			fprintf(fout,"%d\n",N);
		}
		return;
	}
	for(i=0;i<=9;i++){
		if(n==1&&i==0)continue;//首位不得为0
		num.digital[n-1]=i;
		createPalinAndTest(n+1,L,num);
	}
	return;
}

int main(){
	fin=fopen("pprime.in","r");
	fout=fopen("pprime.out","w");
	fscanf(fin,"%d %d",&a,&b);
	int i;
	Num num;
	for(i=1;i<=8;i++)
		createPalinAndTest(1,i,num);
	return 0;
}

 

Category: USACO | Tags: usaco
8
26
2012
0

深度优先搜索:Mother's Milk

至此第1.4关通关。


 

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

PROGRAM NAME: milk3

INPUT FORMAT

A single line with the three integers A, B, and C.

OUTPUT FORMAT

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when bucket A is empty.

 


状态空间很有限,每个桶最多有21种状态(包括桶为空),最坏情况下总状态数为213,直接进行DFS深度优先搜索,当状态重复时剪枝,这样就遍历了三个桶所有可能的状态。DFS一般递归实现,注意不要在递归函数中过度使用全局变量(由于我使用全局变量用于循环控制,出现了问题,详情请看代码注释)。

点击以查看我的程序源码:

 

/*
ID: *******
LANG: C++
TASK: milk3
*/
#include<stdio.h>
#include<stdlib.h>

bool hash[21][21][21];
int cap[3];//记录容量 
FILE *fin,*fout;
int cc[21];//记录结果 
bool hashCc[21];//用于结果去重 
int tailCc;

int cmpint(const void *a, const void *b){
	return(*(int *)a-*(int *)b); //升序 
}

void dfs(int st[3]){//st[0] st[1] st[2] 分别代表A B C桶的状态 
	if(hash[st[0]][st[1]][st[2]])return;//判断该状态是否扩展过 
	hash[st[0]][st[1]][st[2]]=true;
	if(st[0]==0&&!hashCc[st[2]]){
		hashCc[st[2]]=true;
		cc[++tailCc]=st[2];
	}
	int tt[3];
	int i,j;//如果i,j为全局变量,将出现逻辑错误!这种错误很隐蔽,要注意避免在递归函数中滥用全局变量。
	for(i=0;i<3;i++)
		for(j=0;j<3;j++){//枚举各种倾倒 
			if(i==j)continue;
			tt[0]=st[0];
			tt[1]=st[1];
			tt[2]=st[2];
			if(tt[i]+tt[j]>cap[j]){
				tt[i]=tt[i]+tt[j]-cap[j];
				tt[j]=cap[j];
			}
			else{
				tt[j]+=tt[i];
				tt[i]=0;
			}
			dfs(tt);
		}
	return;
}

int main(){
	int i,j,k;
	fin=fopen("milk3.in","r");
	fout=fopen("milk3.out","w");
	fscanf(fin,"%d %d %d",&cap[0],&cap[1],&cap[2]);
	for(i=0;i<21;i++)
		for(j=0;j<21;j++)
			for(k=0;k<21;k++)
				hash[i][j][k]=false;
	for(i=0;i<21;i++)
		hashCc[i]=false;
	tailCc=-1;
	int st[3];
	st[0]=st[1]=0;
	st[2]=cap[2];
	dfs(st);
	qsort(cc,tailCc+1,sizeof(int),cmpint);
	fprintf(fout,"%d",cc[0]);
	for(i=1;i<=tailCc;i++)
		fprintf(fout," %d",cc[i]);
	fprintf(fout,"\n");
	return 0;
} 
Category: USACO | Tags: usaco
8
26
2012
1

怕超时?哈希一下:Arithmetic Progressions

我们将所有能写成 p2+q(p,q>=0)的数字成为bisquare数,在bisquare集合中有多少长度为N(3<=N<=25)的等差序列?我们规定p,q的取值区间为[0,M](1<=M<=250),且等差序列的公差大于0。

我们很容易想到枚举序列中的前两项(或者首项和尾项,这正是我用的方法,这样便于剪枝)来确定整个序列并检验其余项是否是bisquare,但注意当M=250的时候bisquare集合中有20000多个数字,所以算法的复杂度要控制在o(n2)以内,这样检验是否是bisquare的步骤要用常数时间才行,这时候哈希表就派上用场了。

点击查看我的源代码:

 

/*
ID: *******
LANG: C
TASK: ariprog
*/
#include<stdio.h>
#include<stdlib.h>

int N,M;
FILE *fin,*fout;
typedef struct{
    int first;
    int diff;
}R;
R seq[10001];
int tailSeq;
int bisq[32000];
int tailBisq;
int hash[125001];

int cmpint(const void *a, const void *b){
	return(*(int *)a-*(int *)b); //升序 
}

int cmpR(const void *a, const void *b){//先按公差比较,再按首项比较 
	R aa=*(R*)a;
	R bb=*(R*)b;
	if(aa.diff==bb.diff){
		return aa.first-bb.first;
	}
	return aa.diff-bb.diff;
}

int main(){
    fin=fopen("ariprog.in","r");
    fout=fopen("ariprog.out","w");
    fscanf(fin,"%d %d",&N,&M);
    int i,j;
    for(i=0;i<125001;i++)hash[i]=0;
    tailBisq=-1;
    for(i=0;i<=M;i++){
		for(j=i;j<=M;j++){
			bisq[++tailBisq]=i*i+j*j;
			hash[bisq[tailBisq]]=1;//哈希表记录某数字是否在bisquare数字集合中 
		}
    }
    qsort(bisq,tailBisq+1,sizeof(int),cmpint);
    int count=0;
    int pre=-1;
    for(i=0;i<=tailBisq;i++){//排序后去重 
		if(bisq[i]!=pre){
			bisq[count]=bisq[i];
			count++;
			pre=bisq[i];
		}
	}
	tailBisq=count-1;

    tailSeq=-1;
    int first,last;
    for(first=0;first<=tailBisq;first++){
		for(last=first+N-1;last<=tailBisq;last++){//枚举首项和尾项 
			int diff=bisq[last]-bisq[first];
			if(diff==0)continue;
			if(diff%(N-1)!=0)continue;//剪枝
			diff=diff/(N-1);
			for(i=1;i<=N-2;i++)//查看中间项是否是bisquare数 
				if(hash[bisq[first]+diff*i]==0)
					break;
			if(i>N-2){//记录符合条件的等差序列 
				R r;
				r.first=bisq[first];
				r.diff=diff;
				seq[++tailSeq]=r;
			}
		}
	}
	qsort(seq,tailSeq+1,sizeof(R),cmpR);
	for(i=0;i<=tailSeq;i++){
		fprintf(fout,"%d %d\n",seq[i].first,seq[i].diff);
	}
	if(tailSeq==-1)fprintf(fout,"NONE\n");
    return 0;
}
Category: USACO | Tags: usaco
8
25
2012
0

时间和空间的矛盾:The Clocks

Consider nine clocks arranged in a 3x3 array thusly:

|-------|    |-------|    |-------|    
|       |    |       |    |   |   |    
|---O   |    |---O   |    |   O   |          
|       |    |       |    |       |           
|-------|    |-------|    |-------|    
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

Move Affected clocks
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI

Example

Each number represents a time accoring to following table:

9 9 12       9 12 12       9 12 12        12 12 12      12 12 12 
6 6 6  5 ->  9  9  9  8->  9  9  9  4 ->  12  9  9  9-> 12 12 12 
6 3 6        6  6  6       9  9  9        12  9  9      12 12 12 

[But this might or might not be the `correct' answer; see below.]

PROGRAM NAME: clocks

INPUT FORMAT

Lines 1-3: Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above.

SAMPLE INPUT (file clocks.in)

9 9 12
6 6 6
6 3 6

OUTPUT FORMAT

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

SAMPLE OUTPUT (file clocks.out)

4 5 8 9

这个问题要求用最少的步骤把所有的表盘都调整到12点,所能使用的操作集合是给定的。首先我们也许会担心这九种操作是否总能给出一个解决方案,答案是肯定的,因为对于任意表盘,都有一个操作序列能使表针不多不少顺时针转动90度同时其他表盘最终回到原状态(通过应用我们的算法可以预计算出这些操作序列,实际上这些序列的计算只是原问题的特例)。如此以来,通过累积这些序列的操作,我们肯定能得到一个问题的解(这正是USACO题解中给出的一种方法)。

然后我们注意到所有操作最多可以做3次(如果一种操作做4次,等价于没有做任何操作),而且操作顺序对结果没有影响(因为操作的效果是累加的)。这样以来所有可能的操作序列有4^9=262144个,这个数量级完全可以暴力破解(USACO对程序的限制是:运行时间<1s,内存<14M,栈<1M)。

如此一来通过DFS枚举所有情况是完全可行的。但是由于这个问题实质上属于求“最短路径”(这里路径就是操作序列),我选择了BFS以保证得到的第一个解就是最优解(DFS因为是深度优先,不遵循路径长度的顺序进行搜索,第一个解一般不是最优解,所以需要遍历所有情况,这消耗了不必要的时间),当然这需要对搜索的顺序做一定的安排:按非递减顺序遍历,每种操作最多三次。

BFS看似是个不错的选择,但是最多262144个搜索节点数让人头疼,为此我MLE(Memory Limit Exceeded)了一次。之后我想到了使用循环队列【1】


【1】循环队列开多大?找到搜索树中节点数之和最多的相邻两层,如果这个节点数之和是n,那么循环队列开到n+1应该就可以了。假设队列长度为n+1但是搜索过程中队尾循环回来覆盖了队头,这说明队头节点和队尾节点之间有n个节点,这与相邻两层节点数之和最多为n相矛盾(注意到BFS时队头节点永远在队尾节点的上一层)。

但是对于这道题,我的搜索树形状很奇特,这给估算n值带来了很大麻烦,在尝试之后我取了n=50000并且AC。这显然是BFS在解决这个问题时最大的坏处。

作为一个对空间的优化,实际上可以使用位运算,这样可以用一个整数的比特位表示所有表盘的状态,这让它既省空间又省时间。但我没有尝试。


我的程序代码:

/*
ID: *******
LANG: C
TASK: clocks
*/
#include<stdio.h>
FILE *fin,*fout;
typedef struct{
	int clo[9];//表盘状态
	int beg;//第一个要尝试的操作的编号
	int count[9];//每种操作的次数
	int memo[27];//操作序列
	int pMemo;
}CL;//搜索树节点的定义
CL queue[50001];
int tailQue=-1;
int headQue=-1;
int move[9][9]={
	{3,3,0,3,3,0,0,0,0},
	{3,3,3,0,0,0,0,0,0},
	{0,3,3,0,3,3,0,0,0},
	{3,0,0,3,0,0,3,0,0},
	{0,3,0,3,3,3,0,3,0},
	{0,0,3,0,0,3,0,0,3},
	{0,0,0,3,3,0,3,3,0},
	{0,0,0,0,0,0,3,3,3},
	{0,0,0,0,3,3,0,3,3}
};

int testOutput(int po){
	int isAnswer=1;
	int i;
	for(i=0;i<9;i++){
		if(queue[po].clo[i]!=12){
			isAnswer=0;
			break;
		}
	}
	if(isAnswer==1&&queue[po].pMemo>=0){
		fout=fopen("clocks.out","w");
		fprintf(fout,"%d",queue[po].memo[0]+1);
		for(i=1;i<=queue[po].pMemo;i++){
			fprintf(fout," %d",queue[po].memo[i]+1);
		}
		fprintf(fout,"\n");
	}
	return isAnswer;
}

int main(){
	fin=fopen("clocks.in","r");
	int i;
	headQue=0;
	tailQue=1;
	for(i=0;i<9;i++){
		fscanf(fin,"%d",&queue[headQue].clo[i]);
		queue[headQue].count[i]=0;
	}
	queue[headQue].pMemo=-1;
	queue[headQue].beg=0;
	while(headQue!=tailQue){//开始BFS
		if(testOutput(headQue)==1)break;
		for(i=queue[headQue].beg;i<9;i++){
			if(queue[headQue].count[i]>=3)continue;
			int j;
			for(j=0;j<9;j++){
				queue[tailQue].clo[j]=queue[headQue].clo[j]+move[i][j];
				if(queue[tailQue].clo[j]>12)
					queue[tailQue].clo[j]-=12;
				queue[tailQue].count[j]=queue[headQue].count[j];
			}
			for(j=0;j<=queue[headQue].pMemo;j++)
				queue[tailQue].memo[j]=queue[headQue].memo[j];
			queue[tailQue].count[i]++;
			queue[tailQue].pMemo=queue[headQue].pMemo+1;
			queue[tailQue].memo[queue[tailQue].pMemo]=i;
			queue[tailQue].beg=i;
			//printf("tail:%d\n",tailQue);
			tailQue++;
			if(tailQue>50000)tailQue=0;
		}
		headQue++;
		if(headQue>50000)headQue=0;
	}
	return 0;
}

USACO题解的第一种方法是DFS:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <ctype.h>

#define INF 60000	/* bigger than longest possible path */

char *movestr[] = { "abde", "abc", "bcef", "adg", "bdefh", "cfi", "degh",
                    "ghi", "efhi" };

int movedist[9][9];
int clock[9];

int bestmove[9];
int nbestmove;

/* translate move strings into array "movedist" of which clocks change on each move */
void
mkmove(void)
{
    int i;
    char *p;

    for(i=0; i<9; i++)
	for(p=movestr[i]; *p; p++)
	    movedist[i][*p-'a'] = 3;
}

/* apply some number of each move from k to 9 */
/* move contains the number of times each move is applied */
void
solve(int *move, int k)
{
    int i, j, n, rep;

    if(k == 9) {
	for(j=0; j<9; j++)
	    if(clock[j]%12 != 0)
		return;

	/* we have a successful sequence of moves */
	n = 0;
	for(j=0; j<9; j++)
	    n += move[j];

	if(nbestmove == 0 || n < nbestmove) {
	    nbestmove = n;
	    for(j=0; j<9; j++)
		bestmove[j] = move[j];
	}
	return;
    }

    /*
     * the for loop counts down so we
     * generate smaller numbers first by
     * trying more of small numbered
     * moves before we try less of them.
     */
    for(rep=3; rep>=0; rep--) {
	/* apply move k rep times */
	for(i=0; i<rep; i++)
	    for(j=0; j<9; j++)
		clock[j] += movedist[k][j];
	move[k] = rep;

	solve(move, k+1);

	/* undo move */
	for(i=0; i<rep; i++)
	    for(j=0; j<9; j++)
		clock[j] -= movedist[k][j];
    }
}

void
main(void)
{
    FILE *fin, *fout;
    int i, j, move[9];
    char *sep;

    fin = fopen("clocks.in", "r");
    fout = fopen("clocks.out", "w");
    assert(fin != NULL && fout != NULL);

    mkmove();

    for(i=0; i<9; i++)
	fscanf(fin, "%d", &clock[i]);

    solve(move, 0);

    sep = "";
    for(i=0; i<9; i++) {
	for(j=0; j<bestmove[i]; j++) {
	    fprintf(fout, "%s%d", sep, i+1);
	    sep = " ";
	}
    }
    fprintf(fout, "\n");

    exit(0);
}

第二种方法很独特,正如文章开头提到的“对于任意表盘,都有一个操作序列能使表针不多不少顺时针转动90度同时其他表盘最终回到原状态”。这是USACO的原文:


You can precalculate a matrix a as following:

a[i][0],a[i][1],....,a[i][8] is the number of moves '1','2','3',...'9' necessarly to move ONLY clock i (where 0 < i <= 8 - there are 9 clocks: 0=A, 1=B, ... 8=I) 90 degrees clockwise. So, you have the matrix:

int a[9][9]= { {3,3,3,3,3,2,3,2,0},
               {2,3,2,3,2,3,1,0,1},
               {3,3,3,2,3,3,0,2,3},
               {2,3,1,3,2,0,2,3,1},
               {2,3,2,3,1,3,2,3,2},
               {1,3,2,0,2,3,1,3,2},
               {3,2,0,3,3,2,3,3,3},
               {1,0,1,3,2,3,2,3,2},
               {0,2,3,2,3,3,3,3,3} };

That means: to move ONLY the clock 0 (clock A) 90 degrees clockwise you have to do {3,3,3,3,3,2,3,2,0}, 3 moves of type 1, three moves of type 2, ..., 2 moves of type 8, 0 moves of type 9, etc.

To move ONLY the clock 8 (clock I), you have to do the moves {0,2,3,2,3,3,3,3,3}: 0 moves of type 1, 2 moves of type 2... 3 moves of type 9....

That's it! You count in a vector v[9] how many moves of each type you have to do, and the results will be modulo 4 (%4 - 5 moves of any type have the same effect 1 move has).


代码:

#include <stdio.h>

int a[9][9]= { {3,3,3,3,3,2,3,2,0},
               {2,3,2,3,2,3,1,0,1},
               {3,3,3,2,3,3,0,2,3},
               {2,3,1,3,2,0,2,3,1},
               {2,3,2,3,1,3,2,3,2},
               {1,3,2,0,2,3,1,3,2},
               {3,2,0,3,3,2,3,3,3},
               {1,0,1,3,2,3,2,3,2},
               {0,2,3,2,3,3,3,3,3} };
int v[9];

int main() {
    int i,j,k;
    freopen("clocks.in","r",stdin);
    for (i=0; i<9; i++) {
        scanf("%d",&k);
        for(j=0; j<9; j++)
             v[j]=(v[j]+(4-k/3)*a[i][j])%4;
    }
    fclose(stdin);

    k=0;
    freopen("clocks.out","w",stdout);
    for (i=0; i<9; i++)
        for (j=0; j<v[i]; j++)
            if (!k) { printf("%d",i+1); k=1; }
            else    printf(" %d",i+1);
    printf("\n");
    fclose(stdout);
    return 0;
}

方法就是预先计算出所有这些序列,然后针对具体问题简单地叠加这些操作序列,如果一种操作超过了4次,将操作次数模4取余。这种方法可以在O(1)时间内解决问题。问题是这种方法能够总是得到最优解吗?

我认为这种方法成立的一个重要前提是 9种基本操作中任意一种不能由其余操作的组合来等效!

这样一来,操作2(ABC)等于a[0]+a[1]+a[2](a[i]表示一个向量),也就是说(a[0]+a[1]+a[2])mod 4 == {0,1,0,0,0,0,0,0,0} (参照原文中的int a[9][9]),也就是说a矩阵中各种操作的叠加不仅和操作2等效,而且实际上就是操作2。相反,如果这个重要前提不成立,例如操作2可以由操作1和操作3叠加得到,那么a[0]+a[1]+a[2]有可能等于{1,0,1,0,0,0,0,0,0} 这样由此算法得到的解不一定是最优解(一个操作变成了两个操作,操作步骤增加了)。

如果这个前提成立,那么这个算法肯定是安全的,当然这只是一个充分条件,至于其必要性我没能证明。不过从另一角度考虑,一个“九维”的表盘组,表盘之间没有相关性,如果操作2可以由操作1和3叠加的话,实际上我们只有8种操作方式,这显然是不够的,对于一些情况它甚至不能成功的将所有表盘调到12点!

那么这个安全性如何被保证呢?当这个前提成立时,我们的搜索算法和这个常数时间算法是等价的。因为9种操作的每一种都和a矩阵中的某操作序列唯一等价。当你被告知a矩阵向量的某种组合可以组合出最优解,而且把重复4次的向量消去后你只有唯一一种组合方式,那么这个组合不是最优解又能是什么呢?

PS. 本文所有推理都是意淫,事实上本人没有什么数学造诣以至于不能给出形式化的证明。

Category: USACO | Tags: usaco
8
24
2012
0

枚举,将粗暴进行到底:Packing Rectangles

image packing rectangles

 

Four rectangles are given. Find the smallest enclosing (new) rectangle into which these four may be fitted without overlapping. By smallest rectangle, we mean the one with the smallest area.

All four rectangles should have their sides parallel to the corresponding sides of the enclosing rectangle. Figure 1 shows six ways to fit four rectangles together. These six are the only possible basic layouts, since any other layout can be obtained from a basic layout by rotation or reflection. Rectangles may be rotated 90 degrees during packing.

There may exist several different enclosing rectangles fulfilling the requirements, all with the same area. You must produce all such enclosing rectangles.

 

INPUT FORMAT

Four lines, each containing two positive space-separated integers that represent the lengths of a rectangle's two sides. Each side of a rectangle is at least 1 and at most 50.

SAMPLE INPUT (file packrec.in)

1 2
2 3
3 4
4 5

OUTPUT FORMAT

The output file contains one line more than the number of solutions. The first line contains a single integer: the minimum area of the enclosing rectangles. Each of the following lines contains one solution described by two numbers p and q with p<=q. These lines must be sorted in ascending order of p, and must all be different.

 

SAMPLE OUTPUT (file packrec.out)

40
4 10
5 8

 

这个问题给出四个矩形的边长,要求找出所有能同时包裹这四个矩形的大矩形中面积最小的那些并且按一定顺序输出,要求四个矩形要保持边之间平行放置。四个矩形的排布都可以等效为上图中六种方案之一。

方法很简单——枚举各种情况,而且稍加观察还可以发现第4和第5种放置方案是等效的。复杂的一点是第6种方案不太直观。经过一些尝试我认为可以采取以下步骤丢弃不必要的放置方式并保证结果最优: (这个方案没有经过严密的证明,是通过人肉剪枝在我脑子里形成的,只能算我的“经验步骤”。根据这个方案写的程序已经AC,不过可能有疏漏但是OJ的数据没有检测出来)


1.枚举四个位置上的矩形。

布局为:

rc rd
ra rb

2.仅考虑ra高度(用h(ra)表示)大于或等于rb的情况,其余情况可以简单地由此翻转得到。

我们将ra和rb紧贴并且将他们的下边沿对齐。

3.放置rc。

让rc的左边沿和ra的左边沿对齐。由于h(ra)>h(rb),rc可以伸展到rb上空。

4.放置rd。

让rd的下边沿紧贴rb并尽量向左移动。


利用此步骤,可以省略很多不必要的考虑并计算包络矩形的宽度和高度。

当然小矩形们可以90度旋转,所以要针对这一情况进行枚举。

以下是可能产生的一些特殊排布:


进化:

USACO给出的题解用递归的方法让代码看起来干净了很多,而且解法更具普遍性,在解决第6种布局时更是体现出了枚举方法简单粗暴的奥义:并不人为干涉矩形的拼装过程而是简单地列举出所有可能构成包络大矩形边长的几种情况并取最大的那种(请仔细瞅代码)。这看似粗暴却比我的方法高明很多,因为人为的剪枝有可能变成很耗费体力的活动。所以,这个问题教会我们:要枚举,就粗暴到底!(当然是在可接受的时间复杂度之内)


点击查看我的程序源码和USACO题解:

/*
ID: ******
LANG: C
TASK: packrec
*/
#include<stdio.h>

FILE *fin,*fout;
int minArea;
typedef struct {
	int area;//面积
	int p;//短边
	int q;//长边
}M;//表示矩形的结构体
M memo[500];
int tailMemo;//指向memo数组最后一个记录
int rec[4][2];
int w[4];//宽度的下标用于枚举小矩形的旋转
int h[4];//高度的下标

//记录《可能》的最优方案
void testAndInsert(int rw,int rh){
	int tArea = rw*rh;
	if(tArea<=minArea){
		minArea = tArea;
		M m;
		m.area = tArea;
		m.p = rw<rh?rw:rh;
		m.q = rw+rh-m.p;
		int po = tailMemo;
		if(tailMemo==-1)po=0;
		else if(memo[tailMemo].area>tArea)po=tailMemo+1;
		else if(memo[tailMemo].area==tArea){
			if(memo[tailMemo].p>=m.p){
				po=tailMemo+1;
			}
			int t = tailMemo;
			while(memo[t].area==tArea && memo[t].p<m.p){
				memo[t+1]=memo[t];
				po=t;
				t--;
			}//这里做一个插入排序,以便按顺序输出结果
		}
		tailMemo++;
		memo[po]=m;
	}
}
int main(){
	fin = fopen("packrec.in","r");
	fout = fopen("packrec.out","w");
	minArea = 0x7fffffff;
	tailMemo = -1;
	int i;
	for(i=0;i<4;i++)fscanf(fin,"%d %d",&rec[i][0],&rec[i][1]);
	for(w[0]=0;w[0]<=1;w[0]++)
	for(w[1]=0;w[1]<=1;w[1]++)
	for(w[2]=0;w[2]<=1;w[2]++)
	for(w[3]=0;w[3]<=1;w[3]++){//枚举矩形的旋转
		int j;
		for(j=0;j<4;j++)h[j]=1-w[j];
		int rw,rh;
		//layout 1
		rw = 0;
		for(j=0;j<4;j++)rw+=rec[j][w[j]];
		rh = rec[0][h[0]];
		for(j=1;j<4;j++)rh = rec[j][h[j]]>rh?rec[j][h[j]]:rh;
		testAndInsert(rw,rh);
		//layout 2
		for(j=0;j<4;j++){
			rw = rec[j][w[j]];
			int tw = 0;
			rh = 0;
			int k;
			for(k=0;k<4;k++){
				if(k!=j){
					tw+=rec[k][w[k]];
					rh =rec[k][h[k]]>rh?rec[k][h[k]]:rh;
				}
			}
			rw = tw>rw?tw:rw;
			rh+=rec[j][h[j]];
			testAndInsert(rw,rh);
		}
		//layout 3 4 5
		int ra,rb;
		for(ra=0;ra<4;ra++)
			for(rb=0;rb<4;rb++){
				if(rb==ra)continue;
				//3
				rw=rec[ra][w[ra]];
				rh=rec[rb][h[rb]];
				int th=0;
				int tw=0;
				for(j=0;j<4;j++)if(j!=ra&&j!=rb){
					tw+=rec[j][w[j]];
					th=rec[j][h[j]]>th?rec[j][h[j]]:th;
				}
				th+=rec[ra][h[ra]];
				rh=rh>th?rh:th;
				rw=rw>tw?rw:tw;
				rw+=rec[rb][w[rb]];
				testAndInsert(rw,rh);
				//4 5
				int rw1,rh1;
				rh1=rec[ra][h[ra]]+rec[rb][h[rb]];
				rw1=rec[ra][w[ra]]>rec[rb][w[rb]]?rec[ra][w[ra]]:rec[rb][w[rb]];
				for(j=0;j<4;j++)if(j!=ra&&j!=rb){
					rw1+=rec[j][w[j]];
					rh1=rh1>rec[j][h[j]]?rh1:rec[j][h[j]];
				}
				testAndInsert(rw1,rh1);
				
			}
		//layout 6
		int rc,rd;
		for(ra=0;ra<4;ra++)
			for(rb=0;rb<4;rb++){
				if(rb==ra)continue;
				for(rc=0;rc<4;rc++){
					if(rc==ra||rc==rb)continue;
					for(rd=0;rd<4;rd++){
						if(rd==ra||rd==rb||rd==rc)continue;
						if(rec[ra][h[ra]]>=rec[rb][h[rb]]){
							rw=rec[ra][w[ra]]+rec[rb][w[rb]];
							int tw=rec[ra][w[ra]]>rec[rc][w[rc]]?rec[ra][w[ra]]:rec[rc][w[rc]];
							tw+=rec[rd][w[rd]];
							if(rw<tw)rw=tw;
							rh=rec[ra][h[ra]]+rec[rc][h[rc]];
							int th=rec[rb][h[rb]]+rec[rd][h[rd]];
							rh=rh>th?rh:th;
							testAndInsert(rw,rh);
						}
					}
				}
			}

	}
	int prep=0;
	int po=tailMemo;
	fprintf(fout,"%d\n",minArea);
	while(po>=0&&memo[po].area==minArea){
		if(memo[po].p==prep){
			po--;
			continue;
		}
		prep=memo[po].p;
		fprintf(fout,"%d %d\n",memo[po].p,memo[po].q);
		po--;
	}

	return 0;
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef struct Rect Rect;
struct Rect {
    int wid;
    int ht;
};

Rect
rotate(Rect r)
{
    Rect nr;

    nr.wid = r.ht;
    nr.ht = r.wid;
    return nr;
}

int
max(int a, int b)
{
    return a > b ? a : b;
}

int
min(int a, int b)
{
    return a < b ? a : b;
}

int tot;
int bestarea;
int bestht[101];

void
record(Rect r)
{
    int i;

    if(r.wid*r.ht < tot)
        *(long*)0=0;

    if(r.wid*r.ht < bestarea || bestarea == 0) {
        bestarea = r.wid*r.ht;
        for(i=0; i<=100; i++)
            bestht[i] = 0;
    }
    if(r.wid*r.ht == bestarea)
        bestht[min(r.wid, r.ht)] = 1;
}

void
check(Rect *r)
{
    Rect big;
    int i;

    /* schema 1: all lined up next to each other */
    big.wid = 0;
    big.ht = 0;
    for(i=0; i<4; i++) {
        big.wid += r[i].wid;
        big.ht = max(big.ht, r[i].ht);
    }
    record(big);

    /* schema 2: first three lined up, fourth on bottom */
    big.wid = 0;
    big.ht = 0;
    for(i=0; i<3; i++) {
        big.wid += r[i].wid;
        big.ht = max(big.ht, r[i].ht);
    }
    big.ht += r[3].ht;
    big.wid = max(big.wid, r[3].wid);
    record(big);

    /* schema 3: first two lined up, third under them, fourth to side */
    big.wid = r[0].wid + r[1].wid;
    big.ht = max(r[0].ht, r[1].ht);
    big.ht += r[2].ht;
    big.wid = max(big.wid, r[2].wid);
    big.wid += r[3].wid;
    big.ht = max(big.ht, r[3].ht);
    record(big);

    /* schema 4, 5: first two rectangles lined up, next two stacked */
    big.wid = r[0].wid + r[1].wid;
    big.ht = max(r[0].ht, r[1].ht);
    big.wid += max(r[2].wid, r[3].wid);
    big.ht = max(big.ht, r[2].ht+r[3].ht);
    record(big);

    /*
     * schema 6: first two pressed next to each other, next two on top, like: 
     * 2 3
     * 0 1
     */
    big.ht = max(r[0].ht+r[2].ht, r[1].ht+r[3].ht);
    big.wid = r[0].wid + r[1].wid;

    /* do 2 and 1 touch? */
    if(r[0].ht < r[1].ht)
        big.wid = max(big.wid, r[2].wid+r[1].wid);
    /* do 2 and 3 touch? */
    if(r[0].ht+r[2].ht > r[1].ht)
        big.wid = max(big.wid, r[2].wid+r[3].wid);
    /* do 0 and 3 touch? */
    if(r[1].ht < r[0].ht)
        big.wid = max(big.wid, r[0].wid+r[3].wid);

    /* maybe 2 or 3 sits by itself */
    big.wid = max(big.wid, r[2].wid);
    big.wid = max(big.wid, r[3].wid);
    record(big);    
}

void
checkrotate(Rect *r, int n)
{
    if(n == 4) {
        check(r);
        return;
    }

    checkrotate(r, n+1);
    r[n] = rotate(r[n]);
    checkrotate(r, n+1);
    r[n] = rotate(r[n]);
}

void
checkpermute(Rect *r, int n)
{
    Rect t;
    int i;

    if(n == 4)
        checkrotate(r, 0);

    for(i=n; i<4; i++) {
        t = r[n], r[n] = r[i], r[i] = t;    /* swap r[i], r[n] */
        checkpermute(r, n+1);
        t = r[n], r[n] = r[i], r[i] = t;    /* swap r[i], r[n] */
    }
}

void
main(void)
{
    FILE *fin, *fout;
    Rect r[4];
    int i;

    fin = fopen("packrec.in", "r");
    fout = fopen("packrec.out", "w");
    assert(fin != NULL && fout != NULL);

    for(i=0; i<4; i++)
        fscanf(fin, "%d %d", &r[i].wid, &r[i].ht);

    tot=(r[0].wid*r[0].ht+r[1].wid*r[1].ht+r[2].wid*r[2].ht+r[3].wid*r[3].ht);

    checkpermute(r, 0);
    fprintf(fout, "%d\n", bestarea);
    for(i=0; i<=100; i++)
        if(bestht[i])
            fprintf(fout, "%d %d\n", i, bestarea/i);
    exit(0);
}
Category: USACO | Tags: usaco

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com