Baudelaire is Programmer

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。

   （以上出自http://blog.csdn.net/kg_second/article/details/789429）

 

 

    可见SPFA是Bellman-Ford算法的队列实现，减少了不必要的松弛操作。

---

康拓展开