9
20
2012
0

USACO 2.4

 

Section 2.4 DONE 2012.09.12 TEXT Shortest Paths
DONE 2012.09.12 PROB The Tamworth Two [ANALYSIS]
DONE 2012.09.17 PROB Overfencing [ANALYSIS]
DONE 2012.09.18 PROB Cow Tours [ANALYSIS]
DONE 2012.09.19 PROB Bessie Come Home [ANALYSIS]
DONE 2012.09.20 PROB Fractions to Decimals [ANALYSIS]

 

2.4关需要应用基础的最短路径算法,此外还有一些模拟题,难度不大。

The Tamworth Two

状态空间很有限,可以直接模拟,直到John和牛相遇或者出现重复的状态。

Overfencing

特殊的最短路径问题,图中的边权全部为1,所以可以使用广度优先搜索,不用考虑松弛的问题。

Cow Tours

应用floyd-warshall算法,然后枚举加入的边。

Bessie Come Home

单源最短路径问题,使用Dijkstra算法解决。需要注意的是处理重边。

Fractions to Decimals

简单的模拟笔算除法,对于无限循环小数,在笔算过程中第二次出现同样的余数时则可判定循环节出现。

Category: USACO | Tags: usaco
9
12
2012
1

USACO 2.3

 

Section 2.3 DONE 2012.09.08 PROB The Longest Prefix [ANALYSIS]
DONE 2012.09.09 PROB Cow Pedigrees [ANALYSIS]
DONE 2012.09.09 PROB Zero Sum [ANALYSIS]
DONE 2012.09.09 PROB Money Systems [ANALYSIS]
DONE 2012.09.12 PROB Controlling Companies [ANALYSIS]

2.3关开始出现更多动态规划问题。


The Longest Prefix

给定一个字符串集合S={s1,s2,s3...}和一个长字符串s,S中的字符串可以拼接出的s的最长前缀。

如果我们用dp[l]表示长为l的前缀能否被拼接出来(true表示能,false表示不能),则状态转移方程:dp[l]=ORk ( dp[l-length(sk)] and sk等于"s[l-length(sk)+1]s[l-length(sk)+2]...s[l]" ),其中OR表示“或”逻辑,and表示“与”逻辑。于是我们可以边输入边动归,试验集合中每个字符串。

点击查看我的代码:

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

char str[200001];
bool dp[200000];
char set[201][11];
int len[201];
int numset;
int tail;
FILE *fin,*fout;
int max;

int main(){
	fin=fopen("prefix.in","r");
	fout=fopen("prefix.out","w");
	numset=0;
	while(fscanf(fin,"%s",set[numset]) && set[numset][0]!='.'){
		len[numset]=strlen(set[numset]);
		numset++;
	}
	char c;
	tail=-1;
	max=0;
	while((c=fgetc(fin))!=EOF){
		if(c=='\n')continue;
		str[++tail]=c;
		dp[tail]=false;
		int i;
		for(i=0;i<numset;i++){
			if(tail+1>=len[i]){
				if(tail+1>len[i] && !dp[tail-len[i]])continue;
				int j;
				for(j=0;j<len[i];j++){
					if(str[tail-(len[i]-j)+1]!=set[i][j])break;
				}
				if(j==len[i]){
					dp[tail]=true;
					if(tail+1>max)max=tail+1;
					break;
				}
			}
		}
	}
	fprintf(fout,"%d\n",max);
	return 0;
}

Cow Pedigrees

一种二叉树每个节点都有零个或两个儿子节点,用N个节点构造一个高度为K的这种二叉树一共有多少种方法?这里的高度指的是根节点到叶子节点的最多节点数。

二叉树有天然的子结构。所以如果用dp[n][k]表示n个节点构造高度为k的二叉树的放法数,我们有这样一个状态转移方程:

dp[n][k]=dp[1][k-1]*dp[n-2][k-1]
         +dp[3][k-1]*dp[n-4][k-1]
         +...
         +dp[n-2][k-1]*dp[1][k-1]
当然如果n为偶数,则不可能构成一个这种二叉树。
点击查看我的代码:
/*
ID: xxxxxxx
LANG: C++
TASK: nocows
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int N,K;
int dp[200][100];

int main(){
	fin=fopen("nocows.in","r");
	fout=fopen("nocows.out","w");
	fscanf(fin,"%d %d",&N,&K);
	if(N%2==0){
		fprintf(fout,"%d\n",0);
		return 0;
	}
	int n,k;
	for(n=1;n<=N;n++)
		dp[n][0]=0;
	for(k=1;k<=K;k++)
		dp[1][k]=1;
	for(n=3;n<=N;n+=2)
		for(k=1;k<=K;k++){
			dp[n][k]=0;
			int i;
			for(i=1;i<=n-2;i++)
				dp[n][k]+=(dp[i][k-1]*dp[n-1-i][k-1])%9901;
			dp[n][k]%=9901;
		}
	int ans=dp[N][K]-dp[N][K-1];
	if(ans<0)
		ans+=9901;
	fprintf(fout,"%d\n",ans);
	return 0;
}

Zero Sum

在一列数1 2 3 ... N之间插入加号,减号或者空格,组合成一个算式,输出算式结果为0的那些

又是简单粗暴的枚举,dfs搜索所有情况,然后对算式求值:

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

FILE *fin,*fout;
int N;
int num[9]={1,2,3,4,5,6,7,8,9};
char sign[8];

void check(){
	int i;
	int sum=0;
	int n=1;
	int pre=1;
	for(i=0;i<=N-2;i++){
		if(sign[i]==' '){
			n=n*10+num[i+1];
		}
		else if(sign[i]=='+'){
			sum+=pre*n;
			pre=1;
			n=num[i+1];
		}
		else if(sign[i]=='-'){
			sum+=pre*n;
			pre=-1;
			n=num[i+1];
		}
	}
	sum+=pre*n;
	if(sum==0){
		fprintf(fout,"%d",num[0]);
		for(i=1;i<N;i++){
			fprintf(fout,"%c%d",sign[i-1],num[i]);
		}
		fprintf(fout,"\n");
	}
}

void dfs(int c){
	if(c==N-1){
		check();
		return;
	}
	sign[c]=' ';
	dfs(c+1);
	sign[c]='+';
	dfs(c+1);
	sign[c]='-';
	dfs(c+1);
	return;
}

int main(){
	fin=fopen("zerosum.in","r");
	fout=fopen("zerosum.out","w");
	fscanf(fin,"%d",&N);
	dfs(0);
	return 0;
}

Money Systems

用几种面值的硬币组合出一个钱数一共有多少种办法?完全背包问题,在初始化边界条件和设计状态转移方程的时候有一定技巧,详情见经典的背包九讲。我们用dp[v][n]表示前v种硬币组合出钱数n的方法数,状态转移方程:

dp[v][n]=dp[v-1][n]+dp[v][n-value(v)]

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

FILE *fin,*fout;
int V,N;
int value[26];
long long dp[26][10001];


int main(){
	fin=fopen("money.in","r");
	fout=fopen("money.out","w");
	fscanf(fin,"%d %d",&V,&N);
	int v,n;
	for(v=1;v<=V;v++)
		fscanf(fin,"%d",&value[v]);
	for(v=0;v<=V;v++)
		dp[v][0]=1;
	for(n=1;n<=N;n++)
		dp[0][n]=0;
	for(v=1;v<=V;v++){
		for(n=1;n<=N;n++){
			dp[v][n]=dp[v-1][n];
			if(n-value[v]>=0)
				dp[v][n]+=dp[v][n-value[v]];
		}
		printf("\n");
	}
	fprintf(fout,"%lld\n",dp[V][N]);
	return 0;
}

Controlling Companies

着实被这道题卡了不少时间,实际上不用考虑太多,一个二维表表示公司之间控股情况,不断借助可控的公司更新这个表,直到这个表不在变化,就表示我们得到了最终的结果。我认为这个题没有什么可以发掘的,想多了反而容易钻牛角尖。

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

FILE *fin,*fout;
int N;
int control[101][101];
int count[101][101];
bool done[101][101];

int main(){
        fin=fopen("concom.in","r");
        fout=fopen("concom.out","w");
        fscanf(fin,"%d",&N);
        int i,j,p;
        while(N){
                fscanf(fin,"%d %d %d",&i,&j,&p);
                count[i][j]=control[i][j]=p;
                N--;
        }
        for(i=1;i<=100;i++){
                while(1){
                        bool change=false;
                        for(j=1;j<=100;j++){
                                if(count[i][j]>50&&!done[i][j]){
                                        done[i][j]=true;
                                        change=true;
                                        for(p=1;p<=100;p++)
                                                if(i!=p)
                                                        count[i][p]+=control[j][p];
                                }
                        }
                        if(!change)break;
                }
        }
        for(i=1;i<=100;i++)
                for(j=1;j<=100;j++)
                        if(i!=j&&count[i][j]>50)
                                fprintf(fout,"%d %d\n",i,j);
        return 0;
}
Category: USACO | Tags: usaco
8
31
2012
0

USACO 2.2

 

Section 2.2 DONE 2012.08.29 TEXT Data Structures
DONE 2012.08.29 TEXT Dynamic Programming
DONE 2012.08.30 PROB Preface Numbering [ANALYSIS]
DONE 2012.08.29 PROB Subset Sums [ANALYSIS]
DONE 2012.08.31 PROB Runaround Numbers [ANALYSIS]
DONE 2012.08.31 PROB Party Lamps [ANALYSIS]

2.2关的参考材料讲解了常用的散列表、二叉树、堆等数据结构和动态规划(DP)的思想。


Preface Numbering:

罗马数字用一系列符号表示特定数值,I 1 V 5 X 10 L 50 C 100 D 500 M 1000。

一本书的页码从1到N(N<=3500)用罗马数字表示,统计所用的各种罗马数字符号的个数。

比如N=5时, I, II, III, IV, V一共需要7个I和2个V。

N的上限不大,关键是找到将一般数字转化为罗马数字的方法。为此我根据罗马数字组成规则先将其能表示的“不可分解”数值由大到小列出:M 1000,CM 900,D 500,CD 400,C 100,XC 90,L 50,XL 40,X 10,IX 9,V 5I,V 4,I 1

对特定页码,按从大到小的顺序用这些数值对其进行分解,比如3409=3*1000+400+9=MMMCDIX

点击查看我的源码:

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

/*M  1000
  CM 900
  D  500
  CD 400
  C  100
  XC 90
  L  50
  XL 40
  X  10
  IX 9
  V  5
  IV 4
  I  1
  I V X L C D M
 */
FILE *fin,*fout;
int N;
int count[3501][7];
int dict[13][7]={
        {0,0,0,0,0,0,1},
        {0,0,0,0,1,0,1},
        {0,0,0,0,0,1,0},
        {0,0,0,0,1,1,0},
        {0,0,0,0,1,0,0},
        {0,0,1,0,1,0,0},
        {0,0,0,1,0,0,0},
        {0,0,1,1,0,0,0},
        {0,0,1,0,0,0,0},
        {1,0,1,0,0,0,0},
        {0,1,0,0,0,0,0},
        {1,1,0,0,0,0,0},
        {1,0,0,0,0,0,0}
};
int hash[13]={
        1000,900,500,400,100,90,50,40,10,9,5,4,1
};
char ch[7]={'I','V','X','L','C','D','M'};
int main(){
        fin=fopen("preface.in","r");
        fout=fopen("preface.out","w");
        fscanf(fin,"%d",&N);
        int i,j;
        for(i=1;i<=N;i++){
                for(j=0;j<7;j++)
                        count[i][j]=count[i-1][j];
                int t=i;
                for(j=0;j<13;j++){
                        if(t==0)break;
                        int m=t/hash[j];
                        int k;
                        for(k=0;k<7;k++)
                                count[i][k]+=dict[j][k]*m;
                        t%=hash[j];
                }
        }
        for(i=0;i<7;i++)
                if(count[N][i]>0)
                        fprintf(fout,"%c %d\n",ch[i],count[N][i]);
        return 0;
}

Subset Sums:

对于集合{1,2,...,N}(N<=39),将其划分为两个互补的子集,使得两个子集各自元素之和相等,求可行的划分方法数。

比如{1,2,...,7}可以有4种划分:

  • {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}

集合的子集一共有2N个,直接枚举显然会超时。实际上这是一个典型的动态规划问题。

首先我们对问题做进一步的抽象(这一步很重要)。给定一个N之后,元素的总和为(N+1)*N/2,那么实际上我们是要求出所有元素和为(N+1)*N/4的子集,然后这个子集数量除以2就是我们要的结果。当然如果(N+1)*N/2为奇数,那么一定无解。我们用dp[i][s]表示集合{1,2,...,i}的元素总和为s的子集的数量,比如根据上边的例子,dp[7][14]=8。

状态转移方程:

dp[i][s]=dp[i-1][s]+dp[i-1][s-i]

这个状态转移方程是怎么得到的呢?我们对第i个元素(也就是i)进行讨论,如果符合条件的子集中不包含i,这样的子集个数是dp[i-1][s];如果符合条件的子集中包含i,这样的子集个数是dp[i-1][s-i]!这样我们就把计算dp[i][s]转换成了更小规模的子问题(计算dp[i-1][s]和dp[i-1][s-i]),并且能在常数时间内对子问题进行“拼装”构造出更大规模的问题的解!这也正是动态规划的奥义所在。

下一步我们就要确定问题的“边界条件”了。在计算dp[i][s]的时候,问题规模越来越小(换句话说,参数i、s的值越来越小),但是总归要有一个界限,这个界限就是“边界条件”。边界条件一般是一些极限情况,比如在这里我们考虑i=1,s>0时的情况,显然除了dp[1][1]=1 其余dp[1][s]都为0。那么当s足够小的时候会出现什么情况呢,我们考虑s=0,那么dp[i][0]=1,这是为什么呢,因为任何集合有一个空集作为子集。现在我们可以将dp矩阵表示为下图,从图示中我们可以看到“边界条件”的确在dp矩阵中占据了边界位置。

1 1 0 0 0 0 0
1            
1            
1            
1            
1            

 

 

 

 

 

因为dp[i][s]的计算只会用到dp矩阵中同一层的左边和上一层的值,我们从i=2开始,将迭代计算的顺序安排为从上到下,从左到右,一直计算到dp[N][N*(N+1)/4],这个值的一半即为答案。

点击查看我的源码:

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

FILE *fin,*fout;
int N;
long long dp[40][391];
//dp[i][sum]=dp[i-1][sum-i]+dp[i-1][sum]
int main(){
	fin=fopen("subset.in","r");
	fout=fopen("subset.out","w");
	fscanf(fin,"%d",&N);
	int sum=(N+1)*N/2;
	if(sum%2==1){
		fprintf(fout,"0\n");
		return 0;
	}
	sum/=2;
	int i,j;
	dp[1][1]=1;
	for(j=2;j<=sum;j++)
		dp[1][j]=0;
	for(i=1;i<=N;i++)
		dp[i][0]=1;
	for(i=2;i<=N;i++)
		for(j=1;j<=sum;j++){
			dp[i][j]=dp[i-1][j];
			if(j-i>=0)
				dp[i][j]+=dp[i-1][j-i];
		}
	fprintf(fout,"%lld\n",dp[N][sum]/2);
	return 0;
}

Runaround Numbers:

一个Runaround Number的例子是81362

Runaround numbers are integers with unique digits, none of which is zero (e.g., 81362) that also have an interesting property, exemplified by this demonstration:

 

  • If you start at the left digit (8 in our number) and count that number of digits to the right (wrapping back to the first digit when no digits on the right are available), you'll end up at a new digit (a number which does not end up at a new digit is not a Runaround Number). Consider: 8 1 3 6 2 which cycles through eight digits: 1 3 6 2 8 1 3 6 so the next digit is 6.
  • Repeat this cycle (this time for the six counts designed by the `6') and you should end on a new digit: 2 8 1 3 6 2, namely 2.
  • Repeat again (two digits this time): 8 1
  • Continue again (one digit this time): 3
  • One more time: 6 2 8 and you have ended up back where you started, after touching each digit once. If you don't end up back where you started after touching each digit once, your number is not a Runaround number.

Given a number M (that has anywhere from 1 through 9 digits), find and print the next runaround number higher than M, which will always fit into an unsigned long integer for the given test data.


方法一:

如果能注意到开始的“Runaround numbers are integers with unique digits”这个信息,可以想到Runaround Number最多只有9位,我们最多需要排列9个数字,枚举每种可能并且检验其是否为大于M的Runaround Number,然后从中选取一个最小的Runaround Number,枚举量为9!=362880,即使考虑到M比位数相同的数字中最大的Runaround Number还要大的情况,枚举量最多也只有8!+9!=403200,是可行的。


至于数字的全排列可以用“洗牌”算法搞定,比如1 2 3 4 四个数字的全排列,我们可以从1开始,让1不动或者与其后的数字交换,然后我们对第二位、第三位执行相同的步骤,让这些位置上的数字不动或者与其后的数字进行交换,这样就构造出了所有可能的排列。


方法二:

实际上我没有注意到“Runaround numbers are integers with unique digits”这个条件。但是我用一种构造方法同样解决了这个问题。首先我意识到一个Runaround Number各个数位上的值是由我们做“Runaround”的顺序决定的,比如81362循环的顺序是8-6-2-1-3。我们把每个数字用它出现的顺序代替就得到了14523,这实际上是{1,2,3,4,5}全排列的一种情况!这样我们通过生成一个5位的全排列就能决定一种Runaround Number,之所以我在这里说“一种”是因为一个排列可能对应多个Runaround Number,比如从排列14523生成,“1”和“2”之间相差3位,那么第一位上我们可以放置3或者8。由于我们总是从第一位开始数,所以要生成所有n位的Runaround Number,我们只需要做一个{1,2,3,...,n-1}的全排列,对于M=9,枚举量为8!,考虑到M比位数相同的数字中最大的Runaround Number还要大的情况,枚举量最多为8!+7!=45360。由于这种方法直接生成所有可能的Runaround Number,效率比方法一要高,但是构造过程增加了编程的复杂度。

点击查看我的代码:

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

FILE *fin,*fout;
int order[10];
int num[10];
unsigned long int M;
unsigned long int ans;
int L;
bool found;
int max[10]={4,2,9,4,9,6,7,2,9,5};

void check(int l){
        int i;
        if(l==10)
                for(i=0;i<10;i++){
                        if(num[i]<max[i])break;
                        else if(num[i]>max[i])
                                return;
                }
        int j;
        for(i=0;i<l;i++)
                for(j=0;j<l;j++){
                        if(i!=j && num[i]==num[j])
                                return;
                }
        unsigned long int t=0;
        unsigned long int weight=1;
        for(i=l-1;i>=0;i--){
                t+=weight*num[i];
                weight*=10;
        }
        if(t>M && t<ans){
                found=true;
                ans=t;
        }
        return;
}

void createNum(int po,int l){
        if(po==l){
                check(l);
                return;
        }
        int next=(order[po]+1)%l;
        int nextPo;
        for(nextPo=0;nextPo<l;nextPo++)
                if(order[nextPo]==next)
                        break;
        int numPo=nextPo-po;
        if(numPo<0)
                numPo+=l;
        while(numPo<10){
                num[po]=numPo;
                createNum(po+1,l);
                numPo+=l;
        }
        return;
}

void swap(int *a,int *b){
        int t=*a;
        *a=*b;
        *b=t;
        return;
}

void createOrder(int po,int l){
        if(po==l){
                createNum(0,l);
                return;
        }
        int i;
        for(i=po;i<l;i++){
                swap(&order[po],&order[i]);
                createOrder(po+1,l);
                swap(&order[po],&order[i]);
        }
        return;
}

int main(){
        fin=fopen("runround.in","r");
        fout=fopen("runround.out","w");
        fscanf(fin,"%lu",&M);
        L=0;
        unsigned long int t=M;
        while(t){
                L++;
                t/=10;
        }
        found=false;
        ans=0xffffffff;
        int i;
        for(i=0;i<L;i++)
                order[i]=i;
        createOrder(1,L);
        if(!found && L<10){
                for(i=0;i<L+1;i++)
                        order[i]=i;
                createOrder(1,L+1);
        }
        fprintf(fout,"%lu\n",ans);
        return 0;
}

Party Lamps:

To brighten up the gala dinner of the IOI'98 we have a set of N (10 <= N <= 100) colored lamps numbered from 1 to N.

The lamps are connected to four buttons:

  • Button 1: When this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.
  • Button 2: Changes the state of all the odd numbered lamps.
  • Button 3: Changes the state of all the even numbered lamps.
  • Button 4: Changes the state of the lamps whose number is of the form 3xK+1 (with K>=0), i.e., 1,4,7,...

A counter C records the total number of button presses.

When the party starts, all the lamps are ON and the counter C is set to zero.

You are given the value of counter C (0 <= C <= 10000) and the final state of some of the lamps after some operations have been executed. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.


我们首先注意到每个按钮按2次相当于没有按,同时按钮的顺序对结果没有影响。这样对于每种按钮实际上只有按和不按两种效果,枚举每个按钮按或不按,那么最终状态最多为16种(虽然有重复,比如 按下按钮1 和 按下按钮2与按钮3 就可以得到同样的结果,但我们仍然认为这是两种,因为达到这一状态的基本操作是不同的,这在我们判断此状态能否通过C次按键得到时很重要)。我们计算出这16种情况,找出最终状态符合题设的那些并且检验能否用C次按键达到这种状态就可以了。

如何检验某种状态是否可以在C次按键后达到?这16种状态每种都有一个最小按键数(最小为0,最大为4),也就是我们枚举过程中按下的按钮总数。对于状态x,如果C超过了它的最小按键数,那么我们按C次按钮可以得到状态x吗?答案是如果C超出最小按键数1次则不可能,否则完全可以。首先我们可以随意按某个按钮两次来增加按键数,此外按下1 2 3三个按钮各一次也相当于没按!而任意一个大于1的数都能用2和3的线性组合得到,这样我们一定能够通过叠加这些“无用操作”保持最小按键数的效果,同时将按键数增加到C!

点击查看我的源码:

/*
ID: *******
LANG: C++
PROG: lamps
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int N;
int C;
bool onset[100];
bool offset[100];
bool ansset[16][100];
bool change[4][100];
bool tmp[100];
int count[16];
int tailAns;

void createChange(){
        int i;
        for(i=1;i<=100;i++){
                change[0][i-1]=true;
                if(i%2==1)
                        change[1][i-1]=true;
                if(i%2==0)
                        change[2][i-1]=true;
                if(i%3==1)
                        change[3][i-1]=true;
        }
}

void changeLamps(int n,bool *t){
        int i;
        for(i=1;i<=N;i++)
                if(change[n][i-1])
                        t[i-1]=1-t[i-1];
}

int cmp(bool *a,bool *b,int l){
        int i;
        for(i=0;i<l;i++)
                if(a[i]>b[i])return 1;
                else if(a[i]<b[i])return -1;
        return 0;
}

void createAnsset(int n,int c){
        int i,j;
        if(n==4){
                for(i=tailAns;i>=0;i--){
                        if(cmp(tmp,ansset[i],N)==-1){
                                count[i+1]=count[i];
                                for(j=0;j<N;j++)
                                        ansset[i+1][j]=ansset[i][j];
                        }
                        else 
                                break;
                }
                tailAns++;
                count[i+1]=c;
                for(j=1;j<=N;j++)
                        ansset[i+1][j-1]=tmp[j-1];
                return;
        }
        createAnsset(n+1,c);
        changeLamps(n,tmp);
        createAnsset(n+1,c+1);
        changeLamps(n,tmp);
        return;
}

bool check(int n,int pre){
        int i;
        for(i=0;i<N;i++){
                if(onset[i] && !ansset[n][i])return false;
                if(offset[i] && ansset[n][i])return false;
        }
        if(C-count[n]==1||C-count[n]<0){
                return false;
        }
        if(pre==-1)return true;
        for(i=0;i<N;i++)
                if(ansset[n][i]!=ansset[pre][i])
                        return true;
        return false;
}

int main(){
        fin=fopen("lamps.in","r");
        fout=fopen("lamps.out","w");
        fscanf(fin,"%d\n%d",&N,&C);
        int t=0;
        int i;
        while(t!=-1){
                fscanf(fin,"%d",&t);
                onset[t-1]=true;
        }
        t=0;
        while(t!=-1){
                fscanf(fin,"%d",&t);
                offset[t-1]=true;
        }
        createChange();
        for(i=1;i<=N;i++)
                tmp[i-1]=true;
        tailAns=-1;
        createAnsset(0,0);
        int pre=-1;
        bool exit=false;
        for(i=0;i<=tailAns;i++){
                if(check(i,pre)){
                        exit=true;
                        int j;
                        for(j=0;j<N;j++)
                                fprintf(fout,"%d",ansset[i][j]);
                        fprintf(fout,"\n");
                        pre=i;
                }
        }
        if(!exit)fprintf(fout,"IMPOSSIBLE\n");
        return 0;
}
Category: USACO | Tags: usaco
8
29
2012
1

USACO 2.1

 

DONE 2012.08.27 TEXT Flood Fill Algorithms
DONE 2012.08.28 PROB The Castle [ANALYSIS]
DONE 2012.08.28 PROB Ordered Fractions [ANALYSIS]
DONE 2012.08.28 PROB Sorting A Three-Valued Sequence [ANALYSIS]
DONE 2012.08.29 PROB Healthy Holsteins [ANALYSIS]
DONE 2012.08.29 PROB Hamming Codes [ANALYSIS]

这一关的指导内容是Flood Fill算法,并且在 The Castle 中得到了应用(参见 种子染色法:The Castle)。

其余的问题是一些巩固练习:

Ordered Fractions:顺序输出分母在N(N<=160)以内的最简真分数。N值不大,暴搜,用欧几里德算法判断分子分母是否互质。

Sorting A Three-Valued Sequence:对一个由1、2、3组成的序列按非降序进行排序,求最少的交换次数。我使用一个贪心策略,先计算三个数字各自的数目n(1)、n(2)、n(3) ,原序列中前n(1)个数字中不是1的必须要和n(1)之后的1进行交换,为了节省交换步骤,我们将n(1)之前的2和n(1)以后靠前的1进行交换,而把3交换到后边。我们检测之后的n(2)个数字,把其中的3找出来和后面的2交换,这样就完成了排序。

Healthy Holsteins 和 Hamming Codes:简单的搜索/枚举。

Category: USACO | Tags: usaco
8
28
2012
3

种子染色法:The Castle

种子染色法

种子染色法英文叫做Flood Fill ,实际上Flood Fill这个名称更贴切一点,因为这个方法作用在一个图的结点上时恰似洪水一样“淹没”与之相连的其他结点并以相同的方式蔓延出去,这个方法通常用于计算一个图的极大连通子图(这里的“图”是图论的概念)。设想一个无向图,我们从这个图中一个未标号(“标号”可以理解为“染色”)的结点开始,将此结点和从这个结点出发可达的所有结点都赋予相同的标号(染上相同的颜色),那么我们就得到了这些被标号的结点所组成的一个极大连通子图,搜索下一个未标号的结点并重复上述过程我们便可以找到所有的极大连通子图。“染色”的过程可以用DFS或者BFS实现,如果结点数为V,边数为E,因为我们在Flood Fill过程中“造访”每个结点两次,“造访”每条边两次,所以得到所有极大连通子图的时间复杂度为o(V+E) 。

来自Wikipedia的一个示例:

想象每个白色方块为图中的结点,相邻的方块(上下左右)有边相连,那么这个图就有三个极大连通子图,这演示了Flood Fill查找其中一个极大连通子图的过程。


应用

给定一个城堡的平面图,例如:

 

     1   2   3   4   5   6   7
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#   
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #   
   #---#########---#####---#---#
 4 # ->#   |   |   |   |   #   #   
   ############################# 

#  = Wall     -,|  = No wall
-> = Points to the wall to remove to
     make the largest possible new room

要求求出房间数和最大的房间的面积,另外找到一堵墙,我们将其拆掉之后可以得到一个尽可能大的新房间,平面图的表示以及输出遵循以下规则:

 

INPUT FORMAT

The map is stored in the form of numbers, one number for each module, M numbers on each of N lines to describe the floorplan. The input order corresponds to the numbering in the example diagram above.

Each module number tells how many of the four walls exist and is the sum of up to four integers:

  • 1: wall to the west
  • 2: wall to the north
  • 4: wall to the east
  • 8: wall to the south

Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1.

Line 1: Two space-separated integers: M and N
Line 2..: M x N integers, several per line.

 

SAMPLE INPUT (file castle.in)

7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

OUTPUT FORMAT

The output contains several lines:

Line 1: The number of rooms the castle has.
Line 2: The size of the largest room
Line 3: The size of the largest room creatable by removing one wall
Line 4: The single wall to remove to make the largest room possible

 

Choose the optimal wall to remove from the set of optimal walls by choosing the module farthest to the west (and then, if still tied, farthest to the south). If still tied, choose 'N' before 'E'. Name that wall by naming the module that borders it on either the west or south, along with a direction of N or E giving the location of the wall with respect to the module.

SAMPLE OUTPUT (file castle.out)

5
9
16
4 1 E

平面图的块数最多为50*50=2500,墙数最多为49*50*2=4900,枚举要拆掉的墙,并应用 Flood Fill 填充整个图我们可以求得每种情况下最大的房间面积,应用DFS进行搜索,使用位运算检测相应的比特位以确定四周有没有墙壁,同样使用位运算可以模拟拆墙(注意要同时对相邻两个块进行操作以拆掉一面墙)和补墙。计算量最多为4900*(2*2500+2*4900)=72520000 不会超时。因为我们要保留最优解中最靠西边和南边的墙,所以要自东向西,自北向南进行枚举,因为要优先使用北面的墙,我们按“东”、“北”的顺序枚举每个块对应的两面墙。

查看我的程序源码:

 

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

int row,col;
int map[50][50];
FILE *fin,*fout;
int num;//房间数
int max;//最大房间面积
int count;//房间面积
bool filled[50][50];
int direct[4][2]={
	{0,-1},{-1,0},{0,1},{1,0}
};

void dfs(int i,int j){
	if(i<0||i>=row||j<0||j>=col)return;
	if(filled[i][j])return;
	count++;
	filled[i][j]=true;
	int a=1,p;
	for(p=0;p<=3;p++){
		if(((a<<p)&map[i][j])==0)
			dfs(i+direct[p][0],j+direct[p][1]);
	}
}

void floodfill(){
	int i,j;
	max=0;
	num=0;
	for(i=0;i<row;i++)
		for(j=0;j<col;j++)
			filled[i][j]=false;
	for(i=0;i<row;i++)
		for(j=0;j<col;j++)
			if(!filled[i][j]){//寻找未标号的块
				count=0;
				dfs(i,j);
				num++;
				if(max<count)
					max=count;
			}
}

int main(){
	fin=fopen("castle.in","r");
	fout=fopen("castle.out","w");
	fscanf(fin,"%d %d",&col,&row);
	int i,j;
	for(i=0;i<row;i++)
		for(j=0;j<col;j++)
			fscanf(fin,"%d",&map[i][j]);
	floodfill();
	fprintf(fout,"%d\n%d\n",num,max);
	int verymax=0;
	int mi,mj;
	char w;
	for(j=col-1;j>=0;j--)
		for(i=0;i<row;i++){
			int a=4,p;
			for(p=1;p<=2;p++){
				a/=p;
				int b=a==2?8:1;
				if(!(map[i][j]&a))continue;//判断有没有墙
				map[i][j]&=~a;//拆墙
				if(a==2&&i-1>=0)map[i-1][j]&=~b;
				if(a==4&&j+1<col)map[i][j+1]&=~b;//拆掉相邻块对应的墙
				floodfill();
				if(verymax<=max){
					verymax=max;
					mi=i;
					mj=j;
					w=a==2?'N':'E';
				}
				map[i][j]|=a;
				if(a==2&&i-1>=0)map[i-1][j]|=b;
				if(a==4&&j+1<col)map[i][j+1]|=b;//补墙以继续枚举
			}
		}
	fprintf(fout,"%d\n%d %d %c\n",verymax,mi+1,mj+1,w);
	return 0;
}
Category: USACO | Tags: usaco
8
27
2012
3

USACO 第一章终结

至此第1.5关通关,第一章也随之终结,第二章开启。

1.5关除了Prime Palindromes(参见 构造式枚举:Prime Palindromes )之外还有:

Number Triangles - 简单的动态规划。

SuperPrime Rib - 又一个搜索特殊素数的问题,一个SuperPrime是形如2333的数(它的“子数”2, 23,233和它自己全是素数),要求找出长度为N的所有SuperPrime。我用BFS按数位扩展解决

Checker Challenge - 8皇后问题加强版,最多扩展至13皇后,为了不超时我加入了一个小优化:因为棋盘是对称的,所以可以只搜索前一半。

这些问题我没有特殊的体会,所以没有单独成文。

第一章只是个Get Started,USACO给出的指导文章主要内容有 暴搜 DFS BFS 贪心算法 位运算,其中位运算我没有用上。实际上这些题目中有不少可以用位运算优化的情况(比如Checker Chanllenge可以用位运算秒过,详情参阅 Matrix67位运算讲解系列文章)。

Category: USACO | Tags: usaco
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
1

深度优先搜索: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
3

怕超时?哈希一下: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

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