1
16
2013
1

USACO 5.2

1.Snail Trail

DFS,Snail的移动路线可以分为一个个线段,每个线段成为DFS的一个阶段,当Snail在一个方向上运动受阻时枚举转向的方向并进入下一阶段。开始时由于我重复搜索运动受阻时的点导致无限重复“撞墙”结果爆栈了,看来在写递归函数时还有很多细节需要注意。

/*
ID: huilong1
LANG: C++
TASK: snail
*/
#include<iostream>
#include<fstream>
#include<stdlib.h>
using namespace std;

ifstream fin;
ofstream fout;
int N,B;
char map[121][121];
int direct[4][2]={
	{0,1},{0,-1},{1,0},{-1,0}
};

int dfs(int x,int y){
	int maxlen=0;
	for(int k=0;k<4;k++){
		int len=0;
		int i,j;
		i=x;
		j=y;
		while(1){
			int nx,ny;
			nx=i+direct[k][0];
			ny=j+direct[k][1];
			if(nx>=N||nx<0||ny>=N||ny<0||map[nx][ny]=='#'){
				if(len==0)break;//防止重复“撞墙”造成的爆栈
				int futurlen=dfs(i,j);
				if(len+futurlen>maxlen)maxlen=futurlen+len;
				break;
			}
			if(map[nx][ny]=='-'){
				if(len>maxlen)maxlen=len;
				break;
			}
			i=nx;
			j=ny;
			map[i][j]='-';
			len++;
		}
		if(len==0)continue;//这句很重要,防止消除痕迹时形成死循环
		int ii=x+direct[k][0],jj=y+direct[k][1];
		//回溯,消除痕迹
		while(!(ii==i&&jj==j)){
			map[ii][jj]='.';
			ii+=direct[k][0];
			jj+=direct[k][1];
		}
		map[i][j]='.';
	}
	return maxlen;
}

int main(){
	fin.open("snail.in");
	fout.open("snail.out");
	fin>>N>>B;
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)map[i][j]='.';
	for(int i=0;i<B;i++){
		char x;
		int y;
		fin>>x>>y;
		map[(int)(x-'A')][y-1]='#';
	}
	map[0][0]='-';
	fout<<dfs(0,0)+1<<endl;
	return 0;
}

2.Electric Fences

题目对精度要求不高,可以把平面坐标扩大10倍,这样就只需搜索0=<x<=1000和0<=y<=1000范围内的整点,但是搜索所有点还是会超时。首先试验了一下模拟退火算法(Simulated annealing),结果由于对“温度”和随机变化的过程把握不好,导致得到次优解并且波动很大,最终放弃并试了一个不太严谨的方法:先按步长为10搜索所有整点,找到其中的最优点,然后在最优点x和y方向上+-10的范围内提高精度按步长1搜索最优解。

3.Visconsin Square

时限是5秒,简单的DFS就可以过。


模拟退火(Simulated annealing)算法:

以下内容出自heaad的博客

 

一. 爬山算法 ( Hill Climbing )
 
         介绍模拟退火前,先介绍爬山算法。爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。
 
         爬山算法实现很简单,其主要缺点是会陷入局部最优解,而不一定能搜索到全局最优解。如图1所示:假设C点为当前解,爬山算法搜索到A点这个局部最优解就会停止搜索,因为在A点无论向那个方向小幅度移动都不能得到更优的解。
 
图1
 
 
二. 模拟退火(SA,Simulated Annealing)思想
 
         爬山法是完完全全的贪心法,每次都鼠目寸光的选择一个当前最优解,因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法,但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。以图1为例,模拟退火算法在搜索到局部最优解A后,会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点,于是就跳出了局部最大值A。
 
         模拟退火算法描述:
 
         若J( Y(i+1) )>= J( Y(i) )  (即移动后得到更优解),则总是接受该移动
 
         若J( Y(i+1) )< J( Y(i) )  (即移动后的解比当前解要差),则以一定的概率接受移动,而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定)
 
  这里的“一定的概率”的计算参考了金属冶炼的退火过程,这也是模拟退火算法名称的由来。
 
  根据热力学的原理,在温度为T时,出现能量差为dE的降温的概率为P(dE),表示为:
 
    P(dE) = exp( dE/(kT) )
 
  其中k是一个常数,exp表示自然指数,且dE<0。这条公式说白了就是:温度越高,出现一次能量差为dE的降温的概率就越大;温度越低,则出现降温的概率就越小。又由于dE总是小于0(否则就不叫退火了),因此dE/kT < 0 ,所以P(dE)的函数取值范围是(0,1) 。
 
  随着温度T的降低,P(dE)会逐渐降低。
 
  我们将一次向较差解的移动看做一次温度跳变过程,我们以概率P(dE)来接受这样的移动。
 
  关于爬山算法与模拟退火,有一个有趣的比喻:
 
  爬山算法:兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法,它不能保证局部最优值就是全局最优值。
 
  模拟退火:兔子喝醉了。它随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,它渐渐清醒了并朝最高方向跳去。这就是模拟退火。
 
    下面给出模拟退火的伪代码表示。
/*
 *  J(y):在状态y时的评价函数值
 *  Y(i):表示当前状态
 *  Y(i+1):表示新的状态
 *  r: 用于控制降温的快慢
 *  T: 系统的温度,系统初始应该要处于一个高温的状态
 *  T_min :温度的下限,若温度T达到T_min,则停止搜索
*/
while( T > T_min )
{
  dE = J( Y(i+1) ) - J( Y(i) ) ;  

  if ( dE >= 0 )  //表达移动后得到更优解,则总是接受移动
        Y(i+1) = Y(i) ;  //接受从Y(i)到Y(i+1)的移动
  else
  {
    // 函数exp( dE/T )的取值范围是(0,1) ,dE/T越大,则exp( dE/T )也
        if ( exp( dE/T ) > random( 0 , 1 ) )
            Y(i+1) = Y(i) ;  //接受从Y(i)到Y(i+1)的移动
  }
  T = r * T ;  //降温退火 ,0<r<1 。r越大,降温越慢;r越小,降温越快
  /*
  * 若r过大,则搜索到全局最优解的可能会较高,但搜索的过程也就较长。若r过小,则搜索的过程会很快,但最终可能会达到一个局部最优值
  */
  i ++ ;
}

四. 使用模拟退火算法解决旅行商问题

 
  旅行商问题 ( TSP , Traveling Salesman Problem ) :有N个城市,要求从其中某个问题出发,唯一遍历所有城市,再回到出发的城市,求最短的路线。
 
  旅行商问题属于所谓的NP完全问题,精确的解决TSP只能通过穷举所有的路径组合,其时间复杂度是O(N!) 。
 
  使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。(使用遗传算法也是可以的,我将在下一篇文章中介绍)模拟退火解决TSP的思路:
 
    1. 产生一条新的遍历路径P(i+1),计算路径P(i+1)的长度L( P(i+1) )
 
    2. 若L(P(i+1)) < L(P(i)),则接受P(i+1)为新的路径,否则以模拟退火的那个概率接受P(i+1) ,然后降温
 
    3. 重复步骤1,2直到满足退出条件
 
  产生新的遍历路径的方法有很多,下面列举其中3种:
 
    1. 随机选择2个节点,交换路径中的这2个节点的顺序。
 
    2. 随机选择2个节点,将路径中这2个节点间的节点顺序逆转。
 
    3. 随机选择3个节点m,n,k,然后将节点m与n间的节点移位到节点k后面。
 
 
五. 算法评价
 
        模拟退火算法是一种随机算法,并不一定能找到全局的最优解,可以比较快的找到问题的近似最优解。 如果参数设置得当,模拟退火算法搜索效率比穷举法要高。
1
13
2013
1

USACO 5.1

1.Fencing the Cows

二维凸包(Convex Hulls)问题。

以下是usaco training上的教程:

  • Find a point which will be within the convex hull:【注1】
  • Calculate the angle that each point makes with the x axis (within the range 0 to 360 degrees)【注2】
  • Sort the points based on this angle
  • Add the first two points
  • For every other point except the last point
  • Make it the next point in the convex hull
  • Check to see if the angle it forms with the previous two points is greater than 180 degrees. As long as the angle formed with the last two points is greater than 180 degrees, remove the previous point【注3】
  • To add the last point
  • Perform the deletion above,
  • Check to see if the angle the last point forms with the previous point and the first point is greater than 180 degrees or if the angle formed with the last point and the first two points is greater than 180 degrees.【注4】
  • If the first case is true, remove the last point, and continue checking with the next-to-last point.
  • If the second case is true, remove the first point and continue checking.
  • Stop when neither case is true.
  • The adding of the points is linear time, as is the calculation of the angles. Thus, the run-time is dominated by the time of the sort, so gift-wrapping runs in O(nlogn) time, which is provably optimal.

【注1】:

计算点集的中点(可以简单地取所有点在x和y方向上的均值)。此点必在凸包内。

【注2】:

计算各个点与中点的连线与x轴的夹角(在0到2pi之间),这个可以使用C语言math.h库函数中的atan2(double y,double x)来实现,不过注意atan2的值域是(-pi,pi],需要进一步将其映射到[0,2pi)区间内。此外注意atan2(0,0)==0,所以我们可以放心地将其应用到中点和点集中某点重合的情况。

【注3】:

检查逆时针连续的三点是否形成“右转”的角,如果“右转”就把“转角”的点删除,否则会出现一个凹多边形。注意删除一个“转角”之后还要要不断检查之前的点,直到该删除的点全部删除为止。

【注4】:

到此为止从第一个点逆时针转到最后一个点的所有“转角”都成为左转的角了,但是当我们把最后一个点和第一个点相连时,这两个点处的“转角”还可能是“右转”的。为了排除这种情况我们要不断检查第一个和最后一个点,如果“右转”就删除,直到它们全部“左转”为止。


怎样判断是否“右转”:

设有逆时针方向连续的三点(x1,y1),(x2,y2),(x3,y3),首先取两向量<x2-x1,y2-y1>(记为<p1,q1>)和<x3-x2,y3-y2>(记为<p2,q2>),当两向量的向量积的z分量小于0时(即p1q2-p2q1<0)就形成了所谓的“右转”关系。


2.Starry Night

可以简单地应用floodfill来找出所有星座。比较星座是否相同时有些麻烦,因为涉及到平移、旋转、翻转等操作,我是通过修改比对星座时的遍历顺序来实现的,这样最多一共需要比对八种遍历方式下两星座图是否重合。


3.Musical Themes

用一个时间复杂度是O(L*N2)的算法过了。其中N是音符的数量,L是需要比对的Themes的平均长度,由于这个L难以预料,所以多少有点侥幸。思路如下:

用dp[i]表示前i个音符中themes的最大长度,用note数组表示所有的音符,则有

dp[i]={

    dp[i-1]+1(if note[i-dp[i-1]]...note[i]这个序列或其变调形式

              可以在note[0]...note[i-dp[i-1]-1]范围内找到);

    dp[i-1](if not)

}

注意dp[i]比dp[i-1]大1当且仅当note[i]加入后可以与前dp[i-1]个音符形成一个新theme。


usaco的官方题解给出了一个O(N2)的算法,更充分地利用了每一步的计算结果:

Let theme(i,j) be the length of the longest theme which occurs starting at both note i and j. 

Note that if note[i+1]-note[i]==note[j+1]-note[j], than theme(i,j)=1+theme(i+1,j+1). Otherwise, theme(i,j)=1.

Thus, we order the search in such a way that theme(i,j) is tested immediately after theme(i+1,j+1), keeping track of the length of the current theme, as well as the length of the longest theme found so far.

#include <fstream.h>

int     n;
int     note[5000];

int 
main () {
    ifstream filein ("theme.in");
    filein >> n;
    for (int i = 0; i < n; ++i) 
	filein >> note[i];
    filein.close ();

    int     longest = 1;

    for (int i = 1; i < n; ++i) {
	int     length = 1;
	for (int j = n - i - 1 - 1; j >= 0; --j) {
	    if (note[j] - note[j + 1] == note[j + i] - note[j + i + 1]) {
		++length;
		if (length > i) 
		    length = i;
		if (longest < length)
		    longest = length;
	    }
	    else {
		length = 1;
	    }
	}
    }

    ofstream fileout ("theme.out");
    fileout << ((longest >= 5) ? longest : 0) << endl;
    fileout.close ();

    exit (0);
}
Category: USACO | Tags: usaco 凸包 convex hulls
1
10
2013
1

USACO 4.4

 1.Shuttle Puzzle
本来以为是个什么神搜索,原来是个找规律构造题。本来枚举量不算大,不过我没想到判重的好方法,不判重又怕超时,所以还是copy了题解的规律。就这样水过了。

2.Pollutant Control
求边数最少的最小割,如果有多个方案,输出边的输入顺序最小的那个。把每个边的容量Ci修改为Ci*1001+1,因为边数最大为1000,这样求出最大流tot之后tot/1001就是原图的最小割,tot mod 1001就是最小割的边数,这样同时保证了最小割有最小边数。然后按输入顺序枚举每条边,如果移除这条边(Ci)后求得的最大流totnew满足tot-totnew=Ci,则输出这条边,然后在此基础上继续枚举删边求最大流的过程。

3.Frame Up
全拓扑排序。

allTopSort(G){
    if(图G为空){
        输出缓存
        return
    }
    for(G中每个入度为零结点v){
        将v放入缓存
        从G中删除v及其出边,更新相连的结点的入度
        allTopSort(G)
        恢复v及其出边
    }
}
Category: USACO | Tags: usaco
1
10
2013
0

USACO 4.3

1.Buy Low, Buy Lower
动态规划
求最长下降子序列的长度和个数。
设序列为a[0]...a[n]
用dp[i]表示以a[i]为结尾的最长下降子序列的长度,则
dp[i]=max{dp[j]+1}(j<i and a[j]>a[i])
用total[i]表示以a[i]结尾的互不相同的最长下降子序列的个数,则
total[i]=∑total[j] (j<i and a[j]>a[j] and dp[j]+1==dp[i]) 
注意去重,如果有多个符合条件的j对应相同的a[j]我们只加入最大的j对应的total[j],
这是因为如果u>v且a[u]==a[v],以a[v]为结尾的所有序列都包含于以a[u]为结尾的序列集合。
 
2. The Primes
搜索+剪枝
对五位且数位和一定的素数打表。
先放对角线上的两个素数,注意左上角数字是确定的,左下角是一个素数的结尾所以必须为奇数。
然后顺序枚举第1、2、3行上的素数,之后第4、5行可以算出来,记录可行解。
排序输出。
由于每列都是素数,可以打表记录下一些素数“特征”是否存在,用于剪枝,比如有素数为11351,就记 head[1]=head[11]=head[113]=head[1135]=true,如果枚举过程中出现了一些“特征”不存在(对应的head值为 false)就剪枝。另外一定要充分利用已经放置的数的信息进行提前剪枝,比如枚举到第三行素数,可以得到第二列和第四列的前四位数,即可比对这些“特 征”是否存在。
 
3.Street Race
枚举去掉的路口,如果去掉后从起点floodfill不能到达终点,则此路口unavoidable。
如果从一个unavoidable的路口出发不能回到起点可达的路口,则此路口是splitting point。
 
4.Letter Game
首先注意到由于目标词长度最大为7,那么最多只有两个字母组合,且只有长度为3或4的单词可以组合在一起。
对长度3或4的单词单独打表,加上一些简单的剪枝,枚举两单词组合的情况不会超时。

 

Category: USACO | Tags: usaco
1
10
2013
0

USACO 4.2

1.Drainage Ditches
基础的最大流问题,基本步骤是找增广路径,更新残余网络,直到搜索不到增广路径。

2.The Perfect Stall
最大二分匹配,可以使用hungary算法

bool find(int c){
    for(int j=0;j<M;j++){
        if(!graph[c][j]||inpath[j])continue;//如果没有边相连或者j被搜索过则略过
        inpath[j]=true;//把j放到增广路径上,true表示j已经被搜索过
        if(pair[j]==-1||find(pair[j])){
            pair[j]=c;//更新匹配关系
            return true;
        }
        //inpath[j]=false; 加上这句会超时,其实这里并不用回溯
        //因为inpath标识了从j出发能否找到增广路径
    }
    return false;
}
void hungary(){
    for(int i=0;i<N;i++){
        //i必定还没有被匹配
        for(int j=0;j<M;j++)inpath[j]=false;
        if(find(i))match++;
    }
}

3.Job Processing
各种借鉴。
用贪心算法分别求出A机器集合和B机器集合单阶段各自的最优解。为求得整体最优解,把A机器处理的工件的时间线和B机器处理的工件的时间线相接。
此图来自usaco官方题解:


4.Cowcycles
枚举量看似很大,实际上可以水过,注意防止重复计算。
算方差可以用公式D[X]=E[X^2]-E[X]^2
枚举代码有些臃肿:

//用pick(F1,F2,R1,R2,F,R)表示在[F1,F2]区间选取F个数,在[R1,R2]区间选取R个数
void pick(int f1,int f2,int r1,int r2,int f,int r){
    int i,j;
    if(f==0&&r==0){
        calcul();
        return;
    }
    if(f*r!=0){
        for(i=f1;i<=f2-f+1;i++){
            for(j=r1;j<=r2-r+1;j++){
                seqf[F-f]=i;
                seqr[R-r]=j;
                pick(i+1,f2,j+1,r2,f-1,r-1);
            }
        }
    }
    else if(f==0){
        for(j=r1;j<=r2-r+1;j++){
            seqr[R-r]=j;
            pick(f1,f2,j+1,r2,f,r-1);
        }
    }
    else if(r==0){
        for(i=f1;i<=f2-f+1;i++){
            seqf[F-f]=i;
            pick(i+1,f2,r1,r2,f-1,r);
        }
    }
    return;
}
Category: USACO | Tags: usaco
1
10
2013
0

USACO 4.1

Beef McNuggets
数论,动态规划。

确定一个数c能否由a1,a2,a3...,an线性组合而成等效于求一次不定方程
a1*x1+a2*x2+...+an*xn=c ( x1,x2,...,xn>=0 ) (方程A)
是否有解。

裴蜀定理:裴蜀等式ax+by=m(a,b>0)有解当且仅当m是a b的最大公约数gcd(a,b)的倍数。

若gcd(a,b)>1 则方程对于无限个m无解。

若gcd(a,b)=1。当a,b>1时,如果要求x y非负数,m取某些值时无解,比如m=1时。那么是否只有有限个m无解呢?答案是肯定的:
设a,b互质,x0,y0是此方程的特解。其通解可以表示为x=x0+[b/gcd(a,b)]*t , y=y0+[a/gcd(a,b)]*t (t为任意整数)。
令x>=0且y>=0,得-x0/b<=t<=y/a,显然y0/a+x0/b>1时存在t满足此不等式,也即方程有解。令y0/a+x0/b>1,有a*x0+b*y0=m>ab。
可见当m大于ab时方程必有解。

把此结论推广到方程A可知:当gcd(a1,a2,...,an)=1时,有有限个c无解,也就是说我们可以求出一个最大的不能被表示的c;否则有无限个c无解。

确定一个数能否被表示出来可以简单地应用动态规划,如果连续出现256个数字可以被表示出来,那么之后所有数字均可以被表示出来,此时可以停止动态规划。

USACO题解中第二种方法认为数据中必有两个数字互质,所以可以只搜索256*256-2*256以内的数字能否被表示(因为“Given two relatively prime numbers N and M, the largest number that you cannot make is NM - M - N”)。

这个方法对于USACO的数据是正确的,因为这些数据只要有一个大于零的解,都有其中两个数字互质的情况出现。但是显然某些情况下n个数互质,但是两两不互质,比如21 35 15。所以我认为这个方法是有漏洞的。


Fence Rails

搜索,需要精心剪枝。

迭代加深搜索(IDDFS: Iterative deepening depth-first search):控制搜索层数的DFS,即首先允许深度优先搜索K层搜索树,若没有发现可行解,再加大搜索层数(如K+1)重复搜索。

“一般来说,如果目标结点离根结点远,需要遍历整棵树,可以考虑使用深度优先搜索;如果目标离根结点近,或求最小步数,则考虑广度优先搜索或迭代加深搜索;若广度优先搜索存在空间不够的问题,则考虑使用迭代加深搜索。”(本段来源于:http://wenku.baidu.com/view/ce41b54669eae009581bec4a.html)

首先对rails从小到大进行排序,确定所给的boards能否切出n个rails实际上等效于确定所给的boards能否切出排序后的前n个rails。为此我们使用IDDFS,先确定一个搜索深度(即上述的n),再深搜每个rail对应的board,搜索到第一个可行的切割方式时就返回。

搜索时先搜索较大的rail,这样可以让搜索树比较“瘦”(相对于先搜索较小的rail),也就是说树基部的分支较少。

显然这时搜索的时间很大程度上取决于搜到可行解之前我们探索了多少失败的方式,如果能剪掉这些“失败树枝”就好了。所以我们需要提前预知必然的失败并且果断停止在这些“失败树枝”上继续搜索。设boards总长度是B,rails总长度是R,搜索过程中的边角料(不能再切出其他rail)的总长度为W,当B-R<W时可以剪枝。

board最大长度是128,但是rail总数会达到1023之多,可见长度重复的rails有很多,要避免因此产生的重复搜索,比如rail1=rail2=5,那么搜索rail2时只需从rail1对应的board开始。


Fence Loops
水搜索,简单地使用dfs就可以秒杀所有数据。实际上求图中最小环的正统方法是枚举环上的一条边然后求最短路径,不过输入数据是边的邻接信息,而最短路径算法是基于结点的邻接矩阵或者邻接表的,需要重构一下。构造邻接矩阵时可以保留所有篱笆的端点(即使它们会重合),这样最多200个结点,发现两结点重合就将距离置为0。


Cryptcowgraphy
搜索加剪枝。
两个剪枝:
(1)判断C O W字符之间的片段是否是明文的子串,不是就剪枝。
(2)判断第一个和最后一个加密用字符是不是分别为C和W,不是就剪枝。
防止重复搜索相同状态:
如果搜索到的C O W,它的CO或者OW区间内包含上次使用的C O W,就剪枝;比如本次搜索到的COW用红色表示,上次使用的COW用黑色表示,以下情况需要剪枝:CCOWOWCOCOWW 。这是因为先应用黑色COW和先应用红色COW效果相同。
使用以上剪枝还不够,为了配合第2个剪枝,我将搜索顺序设定为先搜索跨度较大的COW再搜索跨度较小的COW。至此AC。
 

Category: USACO | Tags: usaco
1
8
2013
0

USACO 3.4

 

Closed Fences
计算几何,借鉴了很多,写的很辛苦,因为需要考虑不少特殊情况。用二分法分割篱笆来探索每个篱笆能不能被看到,注意要设置一个分段长度的下限。在判断线段是否相交时有一些技巧。借鉴了一下混合积的方法,发现不能处理两个线段共线的情况。我判断共线和共线情况下线段是否相交的方法如下:设坐标系oxyz中两个线段ab和cd处于oxy平面上,若ab×ac与ab×ad的z分量都为0则abcd共线。共线的情况下,若ac*ad>0且bc*bd>0,则两线段不相交,否则相交。
/*
ID: huilong1
LANG: C++
TASK: fence4
*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

#define ESP 1e-4
FILE *fin,*fout;

typedef struct{
	double x;
	double y;
}Point;

typedef struct{
	Point a;
	Point b;
}Seg;

typedef struct{
	double x;
	double y;
	double z;
}Vector;

int N;
Seg fence[201];
Point obser;
Point corner[201];
Seg visible[201];
int numsee;

//判断是否是相邻的篱笆 
bool neighbor(int i,int j){
	if(i==0&&j==N-1||i==N-1&&j==0)return true;
	int abs=i-j;
	if(abs<0)abs=-abs;
	if(abs==1)return true;
	return false;
}

//获得中点
Point getmiddle(Point a,Point b){
	Point m;
	m.x=(a.x+b.x)/2;
	m.y=(a.y+b.y)/2;
	return m;
}

//算点积
double dotpro(Vector a,Vector b){
	return a.x*b.x+a.y*b.y+a.z*b.z;
}

//算叉积
Vector crosspro(Vector a,Vector b){
	Vector t;
	t.x=a.y*b.z-a.z*b.y;
	t.y=a.z*b.x-a.x*b.z;
	t.z=a.x*b.y-a.y*b.x;
	return t;
} 

//获得两点决定的向量
Vector getvector(Point a,Point b){
	Vector t;
	t.x=b.x-a.x;
	t.y=b.y-a.y;
	t.z=0;
	return t;
} 

//判断线段是否交叉
bool cross(Seg p,Seg q){
	Vector pv=getvector(p.a,p.b);
	Vector qv=getvector(q.a,q.b);
	Vector paqa=getvector(p.a,q.a);
	Vector paqb=getvector(p.a,q.b);
	Vector pbqa=getvector(p.b,q.a);
	Vector pbqb=getvector(p.b,q.b);
	Vector qapa=getvector(q.a,p.a);
	Vector qapb=getvector(q.a,p.b);
	//判断两线段是否共线
	Vector v1=crosspro(pv,paqa);
	Vector v2=crosspro(pv,paqb);
	if(v1.z==v2.z&&v1.z==0){//共线 
		if(dotpro(paqa,paqb)>0&&dotpro(pbqa,pbqb)>0)return false;
		else return true;
	}
	//不共线 
	if(dotpro(v1,v2)>0)return false;
	if(dotpro(crosspro(qv,qapa),crosspro(qv,qapb))>0)return false;
	return true;
} 

//判断是否能看到点
int seepoint(Point p,int ind){
	Seg view;
	view.a=obser;
	view.b=p;
	for(int i=0;i<N;i++){
		if(i==ind)continue;
		if(cross(view,fence[i]))return i;
	}
	return -1;
} 

//判断线段是否收缩为一个点 
bool ispoint(Seg s){
	Point a=s.a;
	Point b=s.b;
	if((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)<ESP)return true;
	return false;
}

//判断是否可见 
bool cansee(Seg s,int ind){
	if(ispoint(s))return false;
	Point a=s.a;
	Point b=s.b;
	Point mid=getmiddle(a,b);
	int sta,stb,stmid;
	sta=seepoint(a,ind);
	stb=seepoint(b,ind);
	stmid=seepoint(mid,ind);
	if(sta==stb&&sta>=0)return false;
	if(sta<0||stb<0||stmid<0)return true;
	Seg t;
	t.a=a,t.b=mid;
	if(cansee(t,ind))return true;
	t.a=mid,t.b=b;
	if(cansee(t,ind))return true;
	return false;
} 

int main(){
	fin=fopen("fence4.in","r");
	fout=fopen("fence4.out","w");
	fscanf(fin,"%d",&N);
	fscanf(fin,"%lf %lf",&obser.x,&obser.y);
	for(int i=0;i<N;i++){
		fscanf(fin,"%lf %lf",&corner[i].x,&corner[i].y);
	}
	
	//按顺序生成篱笆 
	for(int i=0;i<=N-2;i++){
		fence[i].a=corner[i];
		fence[i].b=corner[i+1];
	}
	fence[N-1].a=corner[0];
	fence[N-1].b=corner[N-1];
	
	//判断篱笆合法性 (不相邻的不能相交) 
	for(int i=0;i<N;i++){
		for(int j=0;j<i-1;j++){
			if(!neighbor(i,j)&&cross(fence[i],fence[j])){
				//printf("%d %d\n",i,j);
				//system("pause");
				fprintf(fout,"NOFENCE\n");
				return 0;
			}
		}
	}
	
	//为了按顺序输出 调整篱笆顺序 
	Seg t=fence[N-1];
	fence[N-1]=fence[N-2];
	fence[N-2]=t;
	
	for(int i=0;i<N;i++){
		if(cansee(fence[i],i)){
			visible[numsee]=fence[i];
			numsee++;
		}
	}
	fprintf(fout,"%d\n",numsee);
	for(int i=0;i<numsee;i++){
		fprintf(fout,"%.0lf %.0lf %.0lf %.0lf\n",visible[i].a.x,visible[i].a.y,visible[i].b.x,visible[i].b.y);
	}
	//system("pause");
	return 0;
}
 
American Heritage
给一个二叉树的前序遍历和中序遍历,求后序遍历。设计一个递归式,不用重构整个二叉树。
/*
ID: huilong1
LANG: C++
TASK: heritage
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
char in[26];
int hashin[26];
char pre[26];
int num;

void showpost(int prebeg,int preend,int inbeg,int inend){
	if(prebeg>preend)return;
	showpost(prebeg+1,
	         prebeg+hashin[pre[prebeg]-'A']-inbeg,
			 inbeg,
			 hashin[pre[prebeg]-'A']-1);
	showpost(prebeg+hashin[pre[prebeg]-'A']-inbeg+1,
             prebeg+hashin[pre[prebeg]-'A']-inbeg+inend-hashin[pre[prebeg]-'A'],
			 hashin[pre[prebeg]-'A']+1,
			 inend);
	fprintf(fout,"%c",pre[prebeg]);
	return;
}

int main(){
	fin=fopen("heritage.in","r");
	fout=fopen("heritage.out","w");
	while(fscanf(fin,"%c",&in[num])&&in[num]!='\n'){
		hashin[in[num]-'A']=num;
		num++;
	}
	int i;
	for(i=0;i<num;i++)fscanf(fin,"%c",&pre[i]);
	showpost(0,num-1,0,num-1);
	fprintf(fout,"\n");
	//system("pause");
	return 0;
}
 
Electric Fence
用解析法解决了,后来发现可以简单地使用皮克公式。
 
Raucous Rockers
背包问题的变形,我加了一维用来表示唱片的数量。用dp[m][t][n]表示前m张唱片,最后一张唱片剩下t分钟,从前n首歌中选歌时可以选的最大歌曲数。则有:
dp[m][t][n]=max{ dp[m][t][n-1],
                 dp[m][t-time(n)][n-1]+1 ( if time(n)<=t ),
                 dp[m-1][T-time(n)][n-1]+1 ( if time(n)>t )
            }

皮克公式(Pick's theorem)

给定顶点座标均是整点(或正方形格点)的简单多边形,皮克定理说明了其面积A和内部格点数目i、边上格点数目b的关系:A = i + b/2 - 1。

 

观察线段的二分法

以下出自(http://www.cppblog.com/jericho/archive/2011/01/19/138837.html)

设观察点为O,取线段AB,及AB中点C,连结AO、BO、CO;
1. 枚举所有线段,若AO、BO与同一条线段相交,则AB看不到。
2. 若A、B很近,则AB可以看成质点,AB看不到。
3. 枚举所有线段,分别与AO、BO、CO求是否相交,循环结束后判断是否有一条线段(AO、BO、CO)没有相交,如果有,则AB可以看见。
4. 二分AB, 对AC、BC进行上述过程。
Category: USACO | Tags: usaco
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

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