寫了algorithm頭文件中的2個算法：
find.h
#ifndef FIND_H
#define FIND_H
template <typename ITER , typename T>
ITER find(ITER begin, ITER end, T value)
{
ITER it;
for(it = begin; it != end; ++it)
if(*it == value)
break;
return it;
}
#endif
count.h
#ifndef COUNT_H
#define COUNT_H
template <typename ITER , typename T>
int count(ITER begin, ITER end, T value)
{
int sum = 0;
for(ITER it = begin; it != end; ++it)
{
if(*it == value)
++sum;
}
return sum;
}
#endif
以后接著寫。
posted @
2006-09-20 23:54 beyonlin 閱讀(390) |
評論 (3) |
編輯 收藏
參考文章：
http://m.shnenglu.com/qywyh/archive/2006/08/16/11301.htmlhttp://www.programfan.com/blog/article.asp?id=16879
#ifndef UFSET_H
#define UFSET_H
class UFset
{
public:
UFset(int);
void Union(int ,int);
int Find(int);
int & operator [] (int i){return parent[i];}
int size(){return length;}
private:
int length;//集合的個數
int * parent;
};
UFset::UFset(int len)
{
length = len;
parent = new int [length + 1];
for(int k = 1; k <= length; k++)
parent[k] = -1;
}
int UFset::Find(int x)
{
int i;
for(i = x; parent[i] >= 0; i = parent[i]);//搜索根節點
while(i!=x)//路徑壓縮
{
int tmp = parent[x];
parent[x] = i;
x = tmp;
}
return i;
}
void UFset::Union(int x,int y)//合并
{
int pX = Find(x);
int pY = Find(y);
if(pX != pY)
{
int tmp = parent[pX] + parent[pY];
if(parent[pX] > parent[pY])
{
parent[pX] = pY;
parent[pY] = tmp;
}
else
{
parent[pY] = pX;
parent[pX] = tmp;
}
length--;
}
}
#endif
posted @
2006-08-30 00:27 beyonlin 閱讀(511) |
評論 (0) |
編輯 收藏
動態規劃即是一個重點，又是一個難點。
今天終于做出了一題像樣的動態規劃題。
Problem Id:1163??User Id:beyonlin_SCUT
Memory:100K??Time:0MS
Language:C++??Result:Accepted
http://acm.pku.edu.cn/JudgeOnline/problem?id=1163
The Triangle
Time Limit:1000MS? Memory Limit:10000K
Total Submit:3415 Accepted:1988
Description
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
(Figure 1)
Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
Input
Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99.
Output
Your program is to write to standard output. The highest sum is written as an integer.
Sample Input
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Sample Output
30
分析：
題意簡化為：
從第一行開始走到最后一行，每步可以向下走或右下走。
所求即為從第一行走到最后一行經過的數總和的最大值。
令p[][]存儲input。
5
7
3 8
8 1 0
2 7 4 4
|?????\ |? \
4 5 2 6 5
如上圖，令i為行，j為列,
d[i][j]為從第一行走到第i行第j列的最大值。
對于(i,j)這個點，它可以從不同方向走來，如圖' | '代表從上方走來，' \ '代表從左上方走來。
則動態規則方程為：
???????????????? ?{?????d[i-1][1]+p[i][1]???(j=1)
d[i][j]=Max{???? Max( d[i-1][j-1] , d[i-1][j] ) + p[i][j]???(1<j<i)
????????????????? {???? d[i-1][i-1]+p[i][i]???(j=i)
結果為Max(d[n][j]) , (1<=j<=n)
代碼如下：#include<cstdio>
int p[100][100];
int d[100][100];
int Max(int a,int b)
{return a>b?a:b;}
int main()
{
int i,n;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
int j;
for(j=1;j<=i;j++)
scanf("%d",p[i]+j);
}
d[1][1]=p[1][1];
for(i=2;i<=n;i++)
{
int j;
d[i][1]=d[i-1][1]+p[i][1];
for(j=2;j<=i;j++)
d[i][j]=Max(d[i-1][j-1],d[i-1][j])+p[i][j];
d[i][i]=d[i-1][i-1]+p[i][i];
}
int max=0;
for(i=1;i<=n;i++)
{
if(d[n][i]>max)
max=d[n][i];
}
printf("%d\n",max);
return 0;
}
posted @
2006-08-28 10:31 beyonlin 閱讀(608) |
評論 (2) |
編輯 收藏
今天做出了第一題深度優先搜索題。
至此對廣度和深度有了一個基本的了解。
學ACM總算學到了一點非暴力解決問題的方法。
Problem Id:1154??User Id:beyonlin_SCUT
Memory:32K??Time:155MS
Language:C++??Result:Accepted
http://acm.pku.edu.cn/JudgeOnline/problem?id=1154
LETTERS
Time Limit:1000MS? Memory Limit:10000K
Total Submit:694 Accepted:334
Description
A single-player game is played on a rectangular board divided in R rows and C columns. There is a single uppercase
letter (A-Z) written in every position in the board.
Before the begging of the game there is a figure in the upper-left corner of the board (first row, first column). In every move, a player can move the figure to the one of the adjacent positions (up, down,left or right). Only constraint is that
a figure cannot visit a position marked with the same letter twice.
The goal of the game is to play as many moves as possible.
Write a program that will calculate the maximal number of positions in the board the figure can visit in a single game.
Input
The first line of the input contains two integers R and C, separated by a single blank character, 1 <= R, S <= 20.
The following R lines contain S characters each. Each line represents one row in the board.
Output
The first and only line of the output should contain the maximal number of position in the board the figure can visit.
Sample Input
3 6
HFDFFB
AJHGDH
DGAGEH
Sample Output
6
我的程序：
#include<cstdio>
#include<stack>
using namespace std;
struct node
{
int row;
int col;
int dire;
};
char p[30][30];
char flag[30];
int incr[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int main()
{
int i,row,col;
scanf("%d%d",&row,&col);
getchar();
char ch[30];
for(i=1;i<=row;i++)
{
gets(ch);
int j;
for(j=1;j<=col;j++)
p[i][j]=ch[j-1];
}
//初始化，外加一層
for(i=0;i<=col+1;i++)
{
p[0][i]='0';
p[row+1][i]='0';
}
for(i=0;i<=row+1;i++)
{
p[i][0]='0';
p[i][col+1]='0';
}
int Maxmove=0;//最大步數
stack<node>path;
????????//棧初始化
int r=1,c=1,dire=0,f=0,move=1;
node in;
in.row=r;
in.col=c;
in.dire=dire;
path.push(in);
flag[f++]=p[r][c];
while(!path.empty())
{
if(dire<4)
{
int r2=r+incr[dire][0];
int c2=c+incr[dire][1];
bool b=true;
for(int k=0;k<f;k++)//搜索是否已訪問或路不通
{
if(flag[k]==p[r2][c2] || p[r2][c2]=='0')
{
dire++;
b=false;
break;
}
}
if(b)//路通
{
node in;
in.row=r2;
in.col=c2;
in.dire=dire;
path.push(in);//進棧
move++;
flag[f++]=p[r2][c2];//標志已訪問
r=r2;
c=c2;
dire=0;
}
}
else//找到一個解
{
if(move>Maxmove)
Maxmove=move;
move--;
dire=path.top().dire+1; //回溯，去除訪問標志
path.pop();
flag[--f]='\0';
if(!path.empty())
{
r=path.top().row;
c=path.top().col;
}
}
}
printf("%d\n",Maxmove);
return 0;
}
posted @
2006-08-28 01:23 beyonlin 閱讀(863) |
評論 (0) |
編輯 收藏今天在PKU上做了我第一題廣度優先搜索題：
Problem Id:2627??User Id:beyonlin_SCUT
Memory:64K??Time:575MS
Language:C++??Result:Accepted
個人認為算法復雜度應該為O(n^2)或更小。不知是不是這樣。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2627
Gopher and hawks
Time Limit:1000MS? Memory Limit:65536K
Total Submit:900 Accepted:328
Description
A gopher sits in a hole located at (xs, ys) and wants to get to a hole located at (xt, yt). The gopher can run at a constant speed of v m/sec. However, if the gopher is outside of a hole for more than a m minutes he will become a supper to hawks flying over the holes. Can the gopher make it?
Input
The first line of input contains two positive integer numbers: v -- gopher's speed in meters per second and m -- the time after which the gopher becomes prey to hawks if he stays outside a hole. The second line of input contains two floating point numbers: the (xs,ys) coordinates of the gopher starting hole. The third line contains the (xt, yt) coordinates of the target hole. Each Subsequent line of input contains two floating point numbers: the (x,y) coordinates of a gopher hole. All distances are in metres, to the nearest mm.
Output
If the gopher can make it to the target hole, the output line should read "Yes, visiting n other holes.", where n is the minimal number of intermediate holes the gopher has to visit. If the gopher cannot make it the output line should read "No." There are not more than 1000 gopher holes and all coordinates are between -10000 and +10000.
Sample Input
3 1
0.000 0.000
500.000 0.000
179.000 0.000
358.000 0.000
Sample Output
Yes, visiting 2 other holes.
Hint
Sample input 2
5 1
0.000 0.000
0.000 550.000
179.000 0.000
0.000 301.000
Output for sample input 2
No.
我的程序：
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
struct node
{
int point;
int step;
};
double x[1100],y[1100];
bool flag[1100]={false};
int main()
{
int i,v,t;
scanf("%d%d",&v,&t);
t*=60;
double beginX,beginY,endX,endY;
scanf("%lf%lf%lf%lf",&beginX,&beginY,&endX,&endY);
int n=1;
while(scanf("%lf%lf",x+n,y+n)!=EOF)
n++;
x[0]=beginX;
y[0]=beginY;
x[n]=endX;
y[n]=endY;
node n1;//隊列初始化
n1.point=0;
n1.step=0;
queue<node> que;
que.push(n1);
int steps=0;
while(true)
{
if(que.empty())
break;
node tmp=que.front();
que.pop();//出隊列
for(i=1;i<=n;i++)
{
if(!flag[i])//標志是否進過隊列
{
double time=sqrt(pow(x[i]-x[tmp.point],2.0)+pow(y[i]-y[tmp.point],2.0))/v;
if(time<t)
{
if(i==n)
{
steps=tmp.step;
goto next;
}
else
{
node in;
in.point=i;
in.step=tmp.step+1;
que.push(in);//進隊列
flag[i]=true;
}
}
}
}
}
next:
if(steps!=0)
printf("Yes, visiting %d other holes.\n",steps);
else
printf("No.\n");
return 0;
}
posted @
2006-08-24 10:25 beyonlin 閱讀(602) |
評論 (0) |
編輯 收藏