9
27
2012
0

USACO 3.2

 

Section 3.2 DONE 2012.09.24 TEXT Knapsack Problems
DONE 2012.09.24 PROB Factorials [ANALYSIS]
DONE 2012.09.24 PROB Stringsobits [ANALYSIS]
DONE 2012.09.26 PROB Spinning Wheels [ANALYSIS]
DONE 2012.09.26 PROB Feed Ratios [ANALYSIS]
DONE 2012.09.26 PROB Magic Squares [ANALYSIS]
DONE 2012.09.27 PROB Sweet Butter [ANALYSIS]

 

Factorials
当且仅当n!中有因子2和因子5相乘时会产生一个尾数0,所以我们可以删除所有成对的因子2和5,计算过程中仅仅维护最后一位。
 
Stringsobits
动态规划,用dp[i][j]表示包含j个1的长度为i的比特序列的数量,则有dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
然后从高位到低位逐一生成所求的序列。
 
Spinning Wheels
模拟,360秒后回到原状态。
 
Feed Ratios
暴力枚举,注意比例中有0的情况。
 
Magic Squares
BFS,为了记录某个状态有没有出现过可以维护一个有序数组存储这些状态对应的十进制数,具体实现是从小到大生成所有排列并存储,判重时进行二分查找。
据说也可以使用康托展开来进行映射。
康托展开是一个全排列到一个自然数的双射,常用于构建哈希表时的空间压缩。(来自wikipedia)
 
Sweet Buter
稀疏图,采用SPFA算法,用链式前向星来存储邻接表,速度飞快。
/*
ID: huilong1
LANG: C++
TASK: butter
*/
#include<stdio.h>
#include<stdlib.h>

#define INFI 0xfffffff
#define LENQUE 801
FILE *fin,*fout;
int N,P,C;
int cow[500];
typedef struct{
	int tail;
	int len;
	int next;
}Edge;
Edge edge[2901];
int head[801];
int dist[801];
int queue[LENQUE];
bool inque[801];
int min,mins;

void SPFA(int s){
	int i;
	for(i=1;i<=P;i++){
		inque[i]=false;
		dist[i]=INFI;
	}
	dist[s]=0;
	queue[0]=s;
	inque[s]=true;
	int hque=0,tque=1;
	while(hque!=tque){
		int v=queue[hque];
		int next=head[v];
		while(next!=0){
			int u=edge[next].tail;
			int l=edge[next].len;
			if(dist[v]+l<dist[u]){
				dist[u]=dist[v]+l;
				if(!inque[u]){
					inque[u]=true;
					queue[tque]=u;
					tque=(tque+1)%LENQUE;
				}
			}
			next=edge[next].next;
		}
		inque[v]=false;
		hque=(hque+1)%LENQUE;
	}
}

void test(int s){
	int i,count=0;
	for(i=0;i<N;i++)
		count+=dist[cow[i]];
	if(min>count){
		min=count;
		mins=s;
	}
}

int main(){
	fin=fopen("butter.in","r");
	fout=fopen("butter.out","w");
	fscanf(fin,"%d %d %d",&N,&P,&C);
	int i,j,k;
	for(i=0;i<N;i++)fscanf(fin,"%d",&cow[i]);
	for(i=1;i<=C;i++){
		int u,v,l;
		fscanf(fin,"%d %d %d",&u,&v,&l);
		edge[i].next=head[u];
		head[u]=i;
		edge[i].len=l;
		edge[i].tail=v;
		edge[i+C].next=head[v];
		head[v]=i+C;
		edge[i+C].len=l;
		edge[i+C].tail=u;
	}
	min=INFI;
	for(i=1;i<=P;i++){
		SPFA(i);
		test(i);
	}
	fprintf(fout,"%d\n",min);
	return 0;
}

链式前向星

数组模拟链表来存储一个图对应的邻接表。下图出自malash.me ,结构一目了然:


SPFA

    参见http://blog.csdn.net/kg_second/article/details/789429

 

    建立一个队列,初始时队列里只有起始点,再建立一个表格记录起始点到所有点的最短路径(该表格的初始值要赋为极大值,该点到他本身的路径赋为0)。然后执行松弛操作,用队列里有的点作为起始点去刷新到所有点的最短路,如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。
 
    如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)
 
    期望的时间复杂度O(ke), 其中k为所有顶点进队的平均次数,可以证明k一般小于等于2。
 
 
    可见SPFA是Bellman-Ford算法的队列实现,减少了不必要的松弛操作。

康拓展开

 

一个例子(出自Wikipedia):
 
3 5 7 4 1 2 9 6 8 展开为 98884。
因为X=2*8!+3*7!+4*6!+2*5!+0*4!+0*3!+2*2!+0*1!+0*0!=98884.
解释:
排列的第一位是3,比3小的数有两个,以这样的数开始的排列有8!个,因此第一项为2*8!
排列的第二位是5,比5小的数有1、2、3、4,由于3已经出现,因此共有3个比5小的数,这样的排列有7!个,因此第二项为3*7!
以此类推,直至0*0!
 
 
康托展开的逆运算:
 
如n=5,x=96时:
首先用96-1得到95,说明x之前有95个排列
用95去除4! 得到3余23,说明有3个数比第1位小,所以第一位是4
用23去除3! 得到3余5,说明有3个数比第2位小,所以是4,但是4已出现过,因此是5
用5去除2!得到2余1,类似地,这一位是3
用1去除1!得到1余0,这一位是2
最后一位只能是1
所以这个数是45321

 

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