1
16
2013

### USACO 5.2

1.Snail Trail

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

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

ifstream fin;
ofstream fout;
int N,B;
char map;
int direct={
{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];
ny=j+direct[k];
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],jj=y+direct[k];
//回溯，消除痕迹
while(!(ii==i&&jj==j)){
map[ii][jj]='.';
ii+=direct[k];
jj+=direct[k];
}
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='-';
fout<<dfs(0,0)+1<<endl;
return 0;
}
```

2.Electric Fences

3.Visconsin Square

介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如图1所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。 爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图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

### USACO 5.1

1.Fencing the Cows

• 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】：

【注2】：

【注3】：

【注4】：

2.Starry Night

3.Musical Themes

dp[i]={

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

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

dp[i-1](if not)

}

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;

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

### USACO 4.4

1.Shuttle Puzzle

2.Pollutant Control

3.Frame Up

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

### USACO 4.3

dp[i]=max{dp[j]+1}(j<i and a[j]>a[i])

total[i]=∑total[j] (j<i and a[j]>a[j] and dp[j]+1==dp[i])

2. The Primes

3.Street Race

4.Letter Game

Category: USACO | Tags: usaco
1
10
2013

### USACO 4.2

1.Drainage Ditches

2.The Perfect Stall

```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 4.Cowcycles

```//用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

### USACO 4.1

Beef McNuggets

a1*x1+a2*x2+...+an*xn=c ( x1,x2,...,xn>=0 ) (方程A)

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

Fence Rails

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

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

Fence Loops

Cryptcowgraphy

（1）判断C O W字符之间的片段是否是明文的子串，不是就剪枝。
（2）判断第一个和最后一个加密用字符是不是分别为C和W，不是就剪枝。

Category: USACO | Tags: usaco
1
8
2013

### USACO 3.4

Closed Fences

```/*
ID: huilong1
LANG: C++
*/
#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;
Point obser;
Point corner;
Seg visible;
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;
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++
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
char in;
int hashin;
char pre;
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]=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 )
}

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

### 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

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

int map;
int degree;
int tour;
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;
}```

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++
*/
#include<stdio.h>
#include<stdlib.h>

#define IMPOSSIBLE (0x7fffffff)
FILE *fin,*fout;
int numoffer;
int offer;
int price;
int s,b;
int need;
int hash;
int memo;
int dp;

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]);
for(j=1;j<=memo[i];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]+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];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]){
numoffer--;
continue;
}
price[numoffer]=memo[i][2*memo[i]+1];
}
for(n=0;n<=numoffer;n++)
for(i=0;i<=need;i++)
for(j=0;j<=need;j++)
for(k=0;k<=need;k++)
for(l=0;l<=need;l++)
for(m=0;m<=need;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];
pj=j-offer[n];
pk=k-offer[n];
pl=l-offer[n];
pm=m-offer[n];
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][need][need][need][need][numoffer]);
return 0;
}```

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

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

void bfs(int s,int move,int distmemo){
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][s]=0;
done[s][s]=true;
queue=s;
queue=s;
queue=0;
for(i=0;i<8;i++){
int temp;
if(temp>=0&&temp<R&&temp>=0&&temp<=C){
if(!done[temp][temp]){
queue[tail]=temp;
queue[tail]=temp;
done[temp][temp]=true;
distmemo[temp][temp]=queue[tail];
tail=(tail+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=row-1;
king=col-'A';
while(fscanf(fin,"%c",&col)!=EOF){
if(col==' '||col=='\n')continue;
fscanf(fin,"%d",&row);
knight[numknight]=row-1;
knight[numknight]=col-'A';
numknight++;
}
int i;
bfs(king,moveking,distking);
for(i=0;i<8;i++){
int temp;
temp=king+moveking[i];
temp=king+moveking[i];
while(temp>=0&&temp<R&&temp>=0&&temp<C){
bfs(temp,moveknight,distride[numride++]);
temp=temp+moveking[i];
temp=temp+moveking[i];
}
}
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][king];
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;
temp=king+moveking[i];
temp=king+moveking[i];
countking=1;
while(temp>=0&&temp<R&&temp>=0&&temp<C){
d=distride[po][gr][gc];
d+=countking;
d+=dist[ride][temp][temp];
d+=total[gr][gc]-dist[ride][gr][gc];
if(d<min)min=d;
po++;
countking++;
temp=temp+moveking[i];
temp=temp+moveking[i];
}
}
}
}
fprintf(fout,"%d\n",min);
return 0;
}```

Home on the Range

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

FILE *fin,*fout;
int N;
int dp;
bool map;

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]=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++
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int N;
int board;
int dp;
int total;

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[N],total[N]-dp[N]);
return 0;
}```

Category: USACO | Tags: usaco 欧拉回路
9
27
2012

### 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

Stringsobits

Spinning Wheels

Feed Ratios

Magic Squares
BFS，为了记录某个状态有没有出现过可以维护一个有序数组存储这些状态对应的十进制数，具体实现是从小到大生成所有排列并存储，判重时进行二分查找。

Sweet Buter

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

#define INFI 0xfffffff
#define LENQUE 801
FILE *fin,*fout;
int N,P,C;
int cow;
typedef struct{
int tail;
int len;
int next;
}Edge;
Edge edge;
int dist;
int queue[LENQUE];
bool inque;
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=s;
inque[s]=true;
int hque=0,tque=1;
while(hque!=tque){
int v=queue[hque];
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].len=l;
edge[i].tail=v;
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;
}
``` SPFA

建立一个队列，初始时队列里只有起始点，再建立一个表格记录起始点到所有点的最短路径（该表格的初始值要赋为极大值，该点到他本身的路径赋为0）。然后执行松弛操作，用队列里有的点作为起始点去刷新到所有点的最短路，如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空。

如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）

期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。

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

3 5 7 4 1 2 9 6 8 展开为 98884。

9
24
2012

### 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

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

int N;
FILE *fin,*fout;
int map;
int dist;

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[i];
int res=0;
for(i=1;i<N;i++){
int min=0x7fffffff;
int pmin;
for(j=1;j<N;j++){
min=dist[j];
pmin=j;
}
}
res+=min;
for(j=1;j<N;j++){
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++
*/
#include<stdio.h>
#include<stdlib.h>

FILE *fin,*fout;
int dp;
int score;
int time;
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

Shaping Regions

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

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

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

Rect q;
int tail;
int sum;

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

Contact

Stamps

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

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

#define IMPOSSIBLE (201)

FILE *fin,*fout;
int N,K;
int value;
unsigned char dp;

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;
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