1
7
2013
2

USACO 3.3


Section 3.3 DONE 2013.01.07 TEXT Eulerian Tours
DONE 2012.09.28 PROB Riding The Fences [ANALYSIS]
DONE 2012.09.28 PROB Shopping Offers [ANALYSIS]
DONE 2012.09.29 PROB Camelot [ANALYSIS]
DONE 2012.09.30 PROB Home on the Range [ANALYSIS]
DONE 2012.09.30 PROB A Game [ANALYSIS]
 
Riding The Fences
寻找欧拉路径或欧拉回路,用TEXT Eulerian Tours中的算法可以完美解决。
/*
ID: huilong1
LANG: C++
TASK: fence
*/
#include<stdio.h>
#include<stdlib.h>

int map[501][501];
int degree[501];
int tour[1025];
int tail;
int F;
FILE *fin,*fout;

void search(int s){
        if(degree[s]==0){
                tour[tail++]=s;
        }
        else{
                int i;
                for(i=1;i<=500;i++){
                        if(map[s][i]){
                                degree[s]--;
                                map[s][i]--;
                                map[i][s]--;
                                search(i);
                        }
                }
                tour[tail++]=s;
        }
}

int main(){
        fin=fopen("fence.in","r");
        fout=fopen("fence.out","w");
        fscanf(fin,"%d",&F);
        while(F){
                int u,v;
                fscanf(fin,"%d %d",&u,&v);
                map[u][v]++;
                map[v][u]++;
                degree[u]++;
                degree[v]++;
                F--;
        }
        int s=0,i;
        for(i=1;i<=500;i++){
                if(s==0&°ree[i]>0)s=i;
                if(degree[i]%2){
                        s=i;
                        break;
                }
        }
        search(s);
        for(i=tail-1;i>=0;i--)
                fprintf(fout,"%d\n",tour[i]);
        return 0;
}

以下出自usaco training:

Detecting whether a graph has an Eulerian tour or circuit is actually easy; two different rules apply.

☉A graph has an Eulerian circuit if and only if it is connected (once you throw out all nodes of degree 0) and every node has `even degree'.
☉A graph has an Eulerian path if and only if it is connected and every node except two has even degree.
☉In the second case, one of the two nodes which has odd degree must be the start node, while the other is the end node.
 
The basic idea of the algorithm is to start at some node the graph and determine a circuit back to that same node. Now, as the circuit is added (in reverse order, as it turns out), the algorithm ensures that all the edges of all the nodes along that path have been used. If there is some node along that path which has an edge that has not been used, then the algorithm finds a circuit starting at that node which uses that edge and splices this new circuit into the current one. This continues until all the edges of every node in the original circuit have been used, which, since the graph is connected, implies that all the edges have been used, so the resulting circuit is Eulerian.
 
More formally, to determine a Eulerian circuit of a graph which has one, pick a starting node and recurse on it. At each recursive step:
 
Pick a starting node and recurse on that node. At each step:
If the node has no neighbors, then append the node to the circuit and return
If the node has a neighbor, then make a list of the neighbors and process them (which includes deleting them from the list of nodes on which to work) until the node has no more neighbors
To process a node, delete the edge between the current node and its neighbor, recurse on the neighbor, and postpend the current node to the circuit.
And here's the pseudocode:
# circuit is a global array
   find_euler_circuit
     circuitpos = 0
     find_circuit(node 1)

# nextnode and visited is a local array
# the path will be found in reverse order
  find_circuit(node i)

    if node i has no neighbors then
      circuit(circuitpos) = node i
      circuitpos = circuitpos + 1
    else
      while (node i has neighbors)
          pick a random neighbor node j of node i
          delete_edges (node j, node i)
          find_circuit (node j)
      circuit(circuitpos) = node i
      circuitpos = circuitpos + 1
To find an Eulerian tour, simply find one of the nodes which has odd degree and call find_circuit with it.
 
Both of these algorithms run in O(m + n) time, where m is the number of edges and n is the number of nodes, if you store the graph in adjacency list form. With larger graphs, there's a danger of overflowing the run-time stack, so you might have to use your own stack.
 
Multiple edges between nodes can be handled by the exact same algorithm.
 
Self-loops can be handled by the exact same algorithm as well, if self-loops are considered to add 2 (one in and one out) to the degree of a node.
 
A directed graph has a Eulerian circuit if it is strongly connected (except for nodes with both in-degree and out-degree of 0) and the indegree of each node equals its outdegree. The algorithm is exactly the same, except that because of the way this code finds the cycle, you must traverse arcs in reverse order.
 
Finding a Eulerian path in a directed graph is harder. Consult Sedgewick if you are interested.
 

Shopping Offers

五维的背包问题
/*
ID: huilong1
LANG: C++
TASK: shopping
*/
#include<stdio.h>
#include<stdlib.h>

#define IMPOSSIBLE (0x7fffffff)
FILE *fin,*fout;
int numoffer;
int offer[105][5];
int price[105];
int s,b;
int need[5];
int hash[5];
int memo[100][12];
int dp[6][6][6][6][6][100];

int gethash(int c){
	int i;
	for(i=0;i<b;i++)
		if(c==hash[i])
			return i;
	return -1;
}

int main(){
	fin=fopen("shopping.in","r");
	fout=fopen("shopping.out","w");
	fscanf(fin,"%d",&s);
	int i,j,k,l,m,n;
	for(i=0;i<s;i++){
		fscanf(fin,"%d",&memo[i][0]);
		for(j=1;j<=memo[i][0];j++){
			fscanf(fin,"%d %d",&memo[i][(j-1)*2+1],&memo[i][(j-1)*2+2]);
		}
		fscanf(fin,"%d",&memo[i][2*memo[i][0]+1]);
	}
	fscanf(fin,"%d",&b);
	for(i=0;i<b;i++){
		fscanf(fin,"%d %d %d",&hash[i],&need[i],&price[i+1]);
		offer[i+1][i]=1;
	}
	numoffer=b;
	for(i=0;i<s;i++){
		numoffer++;
		for(j=1;j<=memo[i][0];j++){
			int hashcode=gethash(memo[i][(j-1)*2+1]);
			if(hashcode==-1)break;
			offer[numoffer][hashcode]=memo[i][(j-1)*2+2];
		}
		if(j<=memo[i][0]){
			numoffer--;
			continue;
		}
		price[numoffer]=memo[i][2*memo[i][0]+1];
	}
	for(n=0;n<=numoffer;n++)
	for(i=0;i<=need[0];i++)
	for(j=0;j<=need[1];j++)
	for(k=0;k<=need[2];k++)
	for(l=0;l<=need[3];l++)
	for(m=0;m<=need[4];m++){
		if(i+j+k+l+m>0&&n==0)
			dp[i][j][k][l][m][n]=IMPOSSIBLE;
		if(n>0){
			dp[i][j][k][l][m][n]=dp[i][j][k][l][m][n-1];
			int pi,pj,pk,pl,pm;
			pi=i-offer[n][0];
			pj=j-offer[n][1];
			pk=k-offer[n][2];
			pl=l-offer[n][3];
			pm=m-offer[n][4];
			if(pi>=0&&pj>=0&&pk>=0&&pl>=0&&pm>=0){
				if(dp[pi][pj][pk][pl][pm][n]!=IMPOSSIBLE){
					if(dp[pi][pj][pk][pl][pm][n]+price[n]<dp[i][j][k][l][m][n])
						dp[i][j][k][l][m][n]=dp[pi][pj][pk][pl][pm][n]+price[n];
				}
			}
		}
	}
	fprintf(fout,"%d\n",dp[need[0]][need[1]][need[2]][need[3]][need[4]][numoffer]);
	return 0;
}
 
Camelot
 
需要细心的剪枝优化,可以做优化的地方主要在于骑士接王的位置。为了让骑士接到王,王可以做一些预先的移动,其中王通过两步像骑士一样走一个“日”字显然和骑士走两次“日”字步数相同,基于此可以对王的移动中包含,或者等效包含“日”字的情况剪枝。比如在8*8的棋盘上,王的位置用K表示,除了王的原位置之外,需要枚举的骑士接王的位置用*表示,其余点用0表示则有下图:
 
/*
ID: huilong1
LANG: C++
TASK: camelot
*/
#include<stdio.h>
#include<stdlib.h>

#define LENQUE 781
#define INFI 500
FILE *fin,*fout;
int R,C;
int dist[781][31][27];
int total[31][27];
int distking[31][27];
int distride[120][31][27];
int numride;
int king[2];
int numknight;
int knight[781][2];
int moveknight[8][2]={
	{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}
};
int moveking[8][2]={
	{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}
};
int queue[LENQUE][3];
bool done[31][27];

void bfs(int s[2],int move[8][2],int distmemo[31][27]){
	int i,j;
	for(i=0;i<R;i++)for(j=0;j<C;j++)done[i][j]=false;
	for(i=0;i<R;i++)for(j=0;j<C;j++)distmemo[i][j]=INFI;
	distmemo[s[0]][s[1]]=0;
	done[s[0]][s[1]]=true;
	int head=0,tail=1;
	queue[0][0]=s[0];
	queue[0][1]=s[1];
	queue[0][2]=0;
	while(head!=tail){
		for(i=0;i<8;i++){
			int temp[2];
			temp[0]=queue[head][0]+move[i][0];
			temp[1]=queue[head][1]+move[i][1];
			if(temp[0]>=0&&temp[0]<R&&temp[1]>=0&&temp[1]<=C){
				if(!done[temp[0]][temp[1]]){
					queue[tail][0]=temp[0];
					queue[tail][1]=temp[1];
					queue[tail][2]=queue[head][2]+1;
					done[temp[0]][temp[1]]=true;
					distmemo[temp[0]][temp[1]]=queue[tail][2];
					tail=(tail+1)%LENQUE;
				}
			}
		}
		head=(head+1)%LENQUE;
	}
}

int main(){
	fin=fopen("camelot.in","r");
	fout=fopen("camelot.out","w");
	fscanf(fin,"%d %d\n",&R,&C);
	char col;
	int row;
	fscanf(fin,"%c %d",&col,&row);
	king[0]=row-1;
	king[1]=col-'A';
	while(fscanf(fin,"%c",&col)!=EOF){
		if(col==' '||col=='\n')continue;
		fscanf(fin,"%d",&row);
		knight[numknight][0]=row-1;
		knight[numknight][1]=col-'A';
		numknight++;
	}
	int i;
	bfs(king,moveking,distking);
	for(i=0;i<8;i++){
		int temp[2];
		temp[0]=king[0]+moveking[i][0];
		temp[1]=king[1]+moveking[i][1];
		while(temp[0]>=0&&temp[0]<R&&temp[1]>=0&&temp[1]<C){
			bfs(temp,moveknight,distride[numride++]);
			temp[0]=temp[0]+moveking[i][0];
			temp[1]=temp[1]+moveking[i][1];
		}
	}
	bfs(king,moveknight,distride[numride++]);
	for(i=0;i<numknight;i++){
		bfs(knight[i],moveknight,dist[i]);
	}
	int min=0x7fffffff;
	int gr,gc,ride,d,move;
	for(gr=0;gr<R;gr++)for(gc=0;gc<C;gc++){
		for(i=0;i<numknight;i++){
			total[gr][gc]+=dist[i][gr][gc];
		}
	}
	for(gr=0;gr<R;gr++)for(gc=0;gc<C;gc++){
		d=distking[gr][gc]+total[gr][gc];
		if(d<min)min=d;
		for(ride=0;ride<numknight;ride++){
			d=distride[numride-1][gr][gc];
			d+=dist[ride][king[0]][king[1]];
			d+=total[gr][gc]-dist[ride][gr][gc];
			if(d<min)min=d;
			int po=0,countking=0;
			for(i=0;i<8;i++){
				int temp[2];
				temp[0]=king[0]+moveking[i][0];
				temp[1]=king[1]+moveking[i][1];
				countking=1;
				while(temp[0]>=0&&temp[0]<R&&temp[1]>=0&&temp[1]<C){
					d=distride[po][gr][gc];
					d+=countking;
					d+=dist[ride][temp[0]][temp[1]];
					d+=total[gr][gc]-dist[ride][gr][gc];
					if(d<min)min=d;
					po++;
					countking++;
					temp[0]=temp[0]+moveking[i][0];
					temp[1]=temp[1]+moveking[i][1];
				}
			}
		}
	}
	fprintf(fout,"%d\n",min);
	return 0;
}
 
Home on the Range
 
动态规划,用dp[i][j][n]表示以点(i,j)为右下角,有没有一个边长为n的正方形区域。
则dp[i][j][n]=dp[i-1][j][n-1]&&dp[i][j-1][n-1]&&dp[i-1][j-1][n-1]&&dp[i][j][1]
/*
ID: huilong1
LANG: C++
TASK: range
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int N;
int dp[251][251];
bool map[251][251];

int main(){
	fin=fopen("range.in","r");
	fout=fopen("range.out","w");
	fscanf(fin,"%d\n",&N);
	int i,j,n;
	for(i=1;i<=N;i++)for(j=1;j<=N;j++){
		char c;
		fscanf(fin,"%c",&c);
		if(c=='\n')
			fscanf(fin,"%c",&c);
		if(c=='1')map[i][j]=true;
		else map[i][j]=false;
	}
	
	for(n=2;n<=N;n++){
		for(i=N;i>=n;i--)for(j=N;j>=n;j--){
			map[i][j]=map[i-1][j-1]&&map[i-1][j]&&map[i][j-1]&&map[i][j];
		}
		for(i=0;i<=N;i++)dp[i][n-1]=0;
		for(j=0;j<=N;j++)dp[n-1][j]=0;
		for(i=n;i<=N;i++)for(j=n;j<=N;j++){
			dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+map[i][j];
		}
		if(dp[N][N])fprintf(fout,"%d %d\n",n,dp[N][N]);
	}
	return 0;
}
 
A Game
 
动态规划,用dp[i][j]表示对于从第i到第j的一个整数序列,先手的最优分数,total[i][j]表示从第i到第j的一个整数序列的总分数(即所有整数的和),board[i]表示第i个整数的值,则有
dp[i][j]=max{
             board[i]+(total[i+1][j]-dp[i+1][j]),
             board[j]+(total[i][j-1]-dp[i][j-1])
         }
/*
ID: huilong1
LANG: C++
TASK: game1
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int N;
int board[101];
int dp[101][101];
int total[101];

int main(){
	fin=fopen("game1.in","r");
	fout=fopen("game1.out","w");
	fscanf(fin,"%d",&N);
	int i,j,l;
	for(i=1;i<=N;i++){
		fscanf(fin,"%d",&board[i]);
		dp[i][i]=board[i];
		total[i]=total[i-1]+board[i];
	}
	for(l=2;l<=N;l++){
		for(i=1;i+l-1<=N;i++){
			j=i+l-1;
			dp[i][j]=board[i]+(total[j]-total[i]-dp[i+1][j]);
			int t=board[j]+(total[j-1]-total[i-1]-dp[i][j-1]);
			if(t>dp[i][j])dp[i][j]=t;
		}
	}
	fprintf(fout,"%d %d\n",dp[1][N],total[N]-dp[1][N]);
	return 0;
}

 

Category: USACO | Tags: usaco 欧拉回路
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

 

9
24
2012
7

USACO 3.1

 

Section 3.1 DONE 2012.09.20 TEXT Minimal Spanning Trees
DONE 2012.09.20 PROB Agri-Net [ANALYSIS]
DONE 2012.09.21 PROB Score Inflation [ANALYSIS]
DONE 2012.09.23 PROB Humble Numbers [ANALYSIS]
DONE 2012.09.23 PROB Shaping Regions [ANALYSIS]
DONE 2012.09.23 PROB Contact [ANALYSIS]
DONE 2012.09.20 PROB Stamps [ANALYSIS]

Agri-Net

最小生成树问题。应用Prim算法或Kruskal算法。

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

int N;
FILE *fin,*fout;
int map[100][100];
int dist[100];
bool had[100];

int main(){
	fin=fopen("agrinet.in","r");
	fout=fopen("agrinet.out","w");
	fscanf(fin,"%d",&N);
	int i,j;
	for(i=0;i<N;i++)
		for(j=0;j<N;j++)
			fscanf(fin,"%d",&map[i][j]);
	for(i=0;i<N;i++)dist[i]=map[0][i];
	had[0]=true;
	int res=0;
	for(i=1;i<N;i++){
		int min=0x7fffffff;
		int pmin;
		for(j=1;j<N;j++){
			if(!had[j]&&min>dist[j]){
				min=dist[j];
				pmin=j;
			}
		}
		res+=min;
		had[pmin]=true;
		for(j=1;j<N;j++){
			if(had[j])continue;
			if(map[pmin][j]<dist[j])
				dist[j]=map[pmin][j];
		}
	}
	fprintf(fout,"%d\n",res);
	//system("pause");
	return 0;
}

 

Score Inflation

动态规划,完全背包问题(参见《背包九讲》)。状态转移方程:

dp[n][m]=max{dp[n][m-time(n)]+score(n); dp[n-1][m]}

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

FILE *fin,*fout;
int dp[10001];
int score[10001];
int time[10001];
int N,M;

int main(){
	int i,j;
	fin=fopen("inflate.in","r");
	fout=fopen("inflate.out","w");
	fscanf(fin,"%d %d",&M,&N);
	for(i=1;i<=N;i++)
		fscanf(fin,"%d %d",&score[i],&time[i]);
	for(j=0;j<=M;j++)dp[j]=0;
	for(i=1;i<=N;i++)
		for(j=1;j<=M;j++){
			if(j-time[i]>=0&&dp[j-time[i]]+score[i]>dp[j])
				dp[j]=dp[j-time[i]]+score[i];
		}
	fprintf(fout,"%d\n",dp[M]);
	//system("pause");
	return 0;
}

 

Humble Numbers

策略是按顺序生成所有Humble Numbers。因为一个humble number必定可由另一个较小humble number乘以S集合中的某素数来生成,我们求第n个humble number时只须用素数试乘然后找出比第n-1个humble number大的那些结果中最小的。参考关键词:二分查找,记录位置。

 

Shaping Regions

矩形切割问题。

 

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

FILE *fin,*fout;
int A,B,N;

typedef struct{
	int ll[2];
	int ur[2];
	int c;
	bool exist;
}Rect;

Rect q[100000];
int tail;
int sum[2501];

int main(){
	fin=fopen("rect1.in","r");
	fout=fopen("rect1.out","w");
	fscanf(fin,"%d %d %d",&A,&B,&N);
	tail=0;
	q[0].c=1;
	q[0].ll[0]=0;
	q[0].ll[1]=0;
	q[0].ur[0]=A;
	q[0].ur[1]=B;
	q[0].exist=true;
	int i,j;
	int ll[2],ur[2],c;
	for(i=0;i<N;i++){
		fscanf(fin,"%d %d %d %d %d",
			&ll[0],&ll[1],&ur[0],&ur[1],&c);
		int newtail=tail;
		for(j=0;j<=tail;j++){
			if(!q[j].exist)continue;
			if(ll[0]>q[j].ur[0]||q[j].ll[0]>ur[0])continue;
			if(ll[1]>q[j].ur[1]||q[j].ll[1]>ur[1])continue;
			int x1,x2;
			int y1,y2;
			x1=ll[0]>q[j].ll[0]?ll[0]:q[j].ll[0];
			x2=ur[0]<q[j].ur[0]?ur[0]:q[j].ur[0];
			y1=ll[1]>q[j].ll[1]?ll[1]:q[j].ll[1];
			y2=ur[1]<q[j].ur[1]?ur[1]:q[j].ur[1];
			if(q[j].ll[0]<x1){
				newtail++;
				q[newtail].exist=true;
				q[newtail].c=q[j].c;
				q[newtail].ll[0]=q[j].ll[0];
				q[newtail].ll[1]=q[j].ll[1];
				q[newtail].ur[0]=x1;
				q[newtail].ur[1]=q[j].ur[1];
			}
			if(q[j].ur[0]>x2){
				newtail++;
				q[newtail].exist=true;
				q[newtail].c=q[j].c;
				q[newtail].ll[0]=x2;
				q[newtail].ll[1]=q[j].ll[1];
				q[newtail].ur[0]=q[j].ur[0];
				q[newtail].ur[1]=q[j].ur[1];
			}
			if(q[j].ll[1]<y1){
				newtail++;
				q[newtail].exist=true;
				q[newtail].c=q[j].c;
				q[newtail].ll[0]=x1;
				q[newtail].ll[1]=q[j].ll[1];
				q[newtail].ur[0]=x2;
				q[newtail].ur[1]=y1;
			}
			if(q[j].ur[1]>y2){
				newtail++;
				q[newtail].exist=true;
				q[newtail].c=q[j].c;
				q[newtail].ll[0]=x1;
				q[newtail].ll[1]=y2;
				q[newtail].ur[0]=x2;
				q[newtail].ur[1]=q[j].ur[1];
			}
			q[j].exist=false;
		}
		newtail++;
		q[newtail].exist=true;
		q[newtail].c=c;
		q[newtail].ll[0]=ll[0];
		q[newtail].ll[1]=ll[1];
		q[newtail].ur[0]=ur[0];
		q[newtail].ur[1]=ur[1];
		tail=newtail;
	}
	for(i=0;i<=tail;i++)
		if(q[i].exist)
			sum[q[i].c]+=(q[i].ur[0]-q[i].ll[0])*(q[i].ur[1]-q[i].ll[1]);
	for(i=1;i<=2500;i++)
		if(sum[i]>0)
			fprintf(fout,"%d %d\n",i,sum[i]);
	return 0;
}

Contact

从01序列中抓取每种长度的片段按二进制求值,哈希到一个数组进行统计。

 

Stamps

类似完全背包问题,但是对物品总数量有限制。

用dp[n][x]表示前n个面值的邮票凑成x最少要用多少张。

状态转移方程:

dp[n][x]=min{dp[n][x-value(n)]+1; dp[n-1][x]}

 

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

#define IMPOSSIBLE (201)

FILE *fin,*fout;
int N,K;
int value[51];
unsigned char dp[2000001];

int main(){
	fin=fopen("stamps.in","r");
	fout=fopen("stamps.out","w");
	fscanf(fin,"%d %d",&K,&N);
	int i;
	for(i=1;i<=N;i++)fscanf(fin,"%d",&value[i]);
	dp[0]=0;
	for(i=1;i<=2000000;i++)dp[i]=IMPOSSIBLE;
	int j;
	for(i=1;i<=N;i++)
		for(j=1;j<=2000000;j++)
			if(j-value[i]>=0&&dp[j-value[i]]!=IMPOSSIBLE)
				if(dp[j-value[i]]+1<dp[j]){
					dp[j]=dp[j-value[i]]+1;
					if(dp[j]>K)dp[j]=IMPOSSIBLE;
				}
	for(i=1;i<=2000000;i++)
		if(dp[i]==IMPOSSIBLE)break;
	fprintf(fout,"%d\n",i-1);
	//system("pause");
	return 0;
}

矩形切割

以下出自薛矛神牛的讲义:

 

 

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

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
9
10
2012
8

正则序和应用序

练习1.5

Ben 发明了一种检测方法来确定Lisp的解释器采用应用序(Applicative Order)还是正则序(Normal Order)来求值。

他定义了下面两个过程并进行检测:

;过程定义
(define (p) (p))
(define (test x y)
        (if (= x 0) 0 y))
;检测
(test 0 (p))

问解释器使用应用序和正则序时分别输出什么结果?


解释器怎么解释这段程序呢?

如果是按正则序的话,解释器会“完全展开而后规约”,所以求值流程如下:

(test 0 (p))
;展开test 得到以下程序
(if (= 0 (p)) 0 (p))
;对谓词(= )进行求值
(if (#t) 0 (p))
;谓词等于真 返回0
0

这个if语句的行为很重要,实际上if发现(p)并没有被求值的必要。

如果是按应用序的话,解释器会“先对参数求值而后应用”,所以流程如下:

(test 0 (p))
;对参数(p)求值,根据(p)的定义,解释器又得到了(p)
(test 0 (p))
;程序将不会产生有意义的输出
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
1

种子染色法: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
2

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

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