主题：第76次编程比赛题目
mht@ [专家分：1260] 发布于 2008-11-03 18:33:00
一、过河问题
问题描述：
在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数（包括S,T）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。
题目给出独木桥的长度L，青蛙跳跃的距离范围S,T，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。
输入：
第一行有一个正整数L（1 <= L <=10^9），表示独木桥的长度。第二行有三个正整数S，T，M，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中1 <= S <= T <= 10，1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。
输出：
只包括一个整数，表示青蛙过河最少需要踩到的石子数。
样例输入：
10
2 3 5
2 3 5 6 7
样例输出：
2
二、南极冰山问题
传说中，南极有一片广阔的冰原，在冰原下藏有史前文明的遗址。整个冰原被横竖划分成了很多个大小相等的方格。在这个冰原上有N个大小不等的矩形冰山，这些巨大的冰山有着和南极一样古老的历史，每个矩形冰山至少占据一个方格，且其必定完整地占据方格。冰山和冰山之间不会重叠，也不会有边或点相连。
ACM探险队在经过多年准备之后决定在这个冰原上寻找遗址。根据他们掌握的资料，在这个冰原上一个大小为一格的深洞中，藏有一个由史前人类制作的开关。而唯一可以打开这个开关的是一个占据接近一格的可移动的小冰块。显然，在南极是不可能有这样小的独立冰块的，所以这块冰块也一定是史前文明的产物。他们在想办法把这个冰块推到洞里去，这样就可以打开一条通往冰原底部的通道，发掘史前文明的秘密。冰块的起始位置与深洞的位置均不和任何冰山相邻。
这个冰原上的冰面和冰山都是完全光滑的，轻轻的推动冰块就可以使这个冰块向前滑行，直到撞到一座冰山就在它的边上停下来。冰块可以穿过冰面上所有没有冰山的区域，也可以从两座冰山之间穿过。冰块只能沿网格方向推动。
输入
输入文件第一行为冰山的个数N (1<=N<=4000)，第二行为冰块开始所在的方格坐标X1,Y1，第三行为深洞所在的方格坐标X2,Y2，以下N行每行有四个数，分别是每个冰山所占的格子左上角和右下角坐标Xi1,Yi1,Xi2,Yi2 （坐标都在int 型范围内即 -2^31到2^31)
输出
输出文件仅包含一个整数，为最少推动冰块的次数。如果无法将冰块推入深洞中，则输出0。
样例输入
2
1 1
5 5
1 3 3 3
6 2 8 4
样例输出
3
时间：截止到本周日中午
最后更新于：2008-11-05 14:21:00
回复列表 （共19个回复）
沙发
mht@ [专家分：1260] 发布于 2008-11-03 18:36:00
占个位，顺便试试是否隐藏了
板凳
flushtime [专家分：200] 发布于 2008-11-05 11:56:00
呃~
[code=c]
#include<iostream>
#include<cstdlib>
using namespace std;
int const MAX = 100;
int main(){
int f[MAX+1];
int L,S,T,M,P;
cin>>L>>S>>T>>M;
memset(f,0,sizeof(f));
for(int i = 0;i < M;i ++){
cin>>P;
f[P] = 1;
}
for(int i = L;i >= 0;i --){
int det = MAX;
if(i+T>=L) det = 0;
else{
for(int j = i+S;j <=L&&j<=i+T;j ++)
if(det > f[j]) det = f[j];
}
f[i] += det;
}
cout<<f[0];
}
[/code]
4 楼
联想电脑二 [专家分：50] 发布于 2008-11-06 11:18:00
第一题 完全没思路
第二题 感觉是用图的dijkstra做
5 楼
fenix124 [专家分：70] 发布于 2008-11-07 16:31:00
/第二题，只是过了sample就提交了
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
#include <set>
#include <deque>
using namespace std;
struct rect
{
rect(int l = 0,int t = 0,int r = 0,int b = 0):left(l),top(t),right(r),buttom(b)
{
}
int left,top,right,buttom;
}rt[4005];
int rtsize;
struct linklist
{
int data;
linklist *next;
};
linklist currentlist;
struct node
{
int from,to;
linklist *head;
};
vector<node> directionX;
vector<node> directionY;
struct fororder
{
int data;
int flag;
int id;
}fo[8010];
int fosize;
struct position
{
position(int a = 0,int b = 0):x(a),y(b)
{
}
int x;
int y;
};
int cmp1(const position &lhs,const position &rhs)
{
if(lhs.x != rhs.x) return lhs.x < rhs.x;
return lhs.y < rhs.y;
}
bool operator<(const position &lhs,const position &rhs)
{
return cmp1(lhs,rhs);
}
set<position> existpos;
struct queuenode
{
int x,y;
int direction;
int step;
};
deque<queuenode> que;
int cmp(fororder &lhs,fororder &rhs)
{
return lhs.data < rhs.data;
}
void add(int x)
{
linklist *ll;
linklist *itr;
ll = new linklist;
ll->data = x;
//ll->next = NULL;
itr = ¤tlist;
while(itr->next != NULL && x > itr->next->data)
{
itr = itr->next;
}
ll->next = itr->next;
itr->next = ll;
}
void remove(int x)
{
linklist *ll;
linklist *itr;
itr = ¤tlist;
while(itr->next != NULL && x > itr->next->data)
{
itr = itr->next;
}
if(itr->next != NULL && x == itr->next->data)
{
ll = itr->next;
itr->next = ll->next;
delete ll;
}
}
int listempty()
{
return currentlist.next == NULL;
}
void copylist(linklist** ls)
{
linklist *itr;
linklist **pitr = ls;
linklist *ll;
itr = ¤tlist;
while(itr->next != NULL)
{
ll = new linklist;
ll->data = itr->next->data;
ll->next = NULL;
*pitr = ll;
pitr = &((*pitr)->next);
itr = itr->next;
}
}
6 楼
fenix124 [专家分：70] 发布于 2008-11-07 16:32:00
void processX()
{
int i,sx,ex;
node nd;
fosize = 0;
for(i = 0;i < rtsize;i++)
{
fo[fosize].data = rt[i].left;
fo[fosize].flag = 1;
fo[fosize].id = i;
fosize++;
fo[fosize].data = rt[i].right;
fo[fosize].flag = 0;
fo[fosize].id = i;
fosize++;
}
sort(fo,fo+fosize,cmp);
i = 0;
sx = fo[0].data;
while(i < fosize)
{
for(;fo[i].data == sx;i++)
{
if(fo[i].flag == 1)
{
add(rt[fo[i].id].buttom);
add(rt[fo[i].id].top);
}
else
{
remove(rt[fo[i].id].buttom);
remove(rt[fo[i].id].top);
}
}
ex = fo[i].data;
if(!listempty())
{
nd.from = sx;
nd.to = ex;
copylist(&nd.head);
directionX.push_back(nd);
}
sx = ex;
}
}
void processY()
{
int i,sx,ex;
node nd;
fosize = 0;
for(i = 0;i < rtsize;i++)
{
fo[fosize].data = rt[i].buttom;
fo[fosize].flag = 0;
fo[fosize].id = i;
fosize++;
fo[fosize].data = rt[i].top;
fo[fosize].flag = 1;
fo[fosize].id = i;
fosize++;
}
sort(fo,fo+fosize,cmp);
i = 0;
sx = fo[0].data;
while(i < fosize)
{
for(;fo[i].data == sx;i++)
{
if(fo[i].flag == 1)
{
add(rt[fo[i].id].left);
add(rt[fo[i].id].right);
}
else
{
remove(rt[fo[i].id].left);
remove(rt[fo[i].id].right);
}
}
ex = fo[i].data;
if(!listempty())
{
nd.from = sx;
nd.to = ex;
copylist(&nd.head);
directionY.push_back(nd);
}
sx = ex;
}
}
void printlist(linklist* ll)
{
cout <<"list = "<<endl;
while(ll != NULL)
{
cout<<ll->data<<endl;
ll = ll->next;
}
}
int getIndex(vector<node>& direction,int place)
{
int l,r,mid;
node nd;
l = 0;
r = direction.size()-1;
while(l <= r)
{
mid = (l+r)/2;
nd = direction[mid];
if(place <= nd.from) r = mid-1;
else if(place > nd.to) l = mid+1;
else return mid;
}
return -1;
}
void getBound(linklist* ll,int pos,int &s,int &e,int &flag)
{
int a,b;
flag = 0;
if(ll == NULL) return;
if(pos < ll->data)
{
flag = 2;
e = ll->data;
return;
}
ll = ll->next;
a = ll->data;
while(ll->next != NULL)
{
ll = ll->next;
b = ll->data;
if( pos > a && pos < b)
{
s = a+1;
e = b;
flag = 3;
return;
}
ll = ll->next;
a = ll->data;
}
if(pos > a)
{
flag = 1;
s = a+1;
}
}
7 楼
fenix124 [专家分：70] 发布于 2008-11-07 16:35:00
int bfs(int sx,int sy,int ex,int ey)
{
queuenode qn,qn1;
int i,s,e,flag;
if(sx == ex && sy == ey)
{
return -1;
}
qn.x = sx;
qn.y = sy;
qn.direction = 0;
qn.step = 0;
que.push_back(qn);
qn.direction = 1;
que.push_back(qn);
while(!que.empty())
{
qn = que.front();
que.pop_front();
if(qn.direction)
{
i = getIndex(directionY,qn.y);
if(i < 0 && qn.y == ey) return qn.step+1;
if(i >= 0)
{
flag = 0;
getBound(directionY[i].head,qn.y,s,e,flag);
if(flag&1 && existpos.find(position(s,qn.y)) == existpos.end())
{
existpos.insert(position(s,qn.y));
qn1.y = qn.y;
qn1.x = s;
qn1.direction = 0;
qn1.step = qn.step+1;
que.push_back(qn1);
}
if(flag&2 && existpos.find(position(e,qn.y)) == existpos.end())
{
existpos.insert(position(e,qn.y));
qn1.y = qn.y;
qn1.x = e;
qn1.direction = 0;
qn1.step = qn.step+1;
que.push_back(qn1);
}
if(qn.y == ey)
{
if(flag == 3 && ex >= s && ex <= e) return qn.step+1;
else if(flag == 2 && ex <= e) return qn.step+1;
else if(flag == 1 && ex >= s) return qn.step+1;
}
}
}
8 楼
fenix124 [专家分：70] 发布于 2008-11-07 16:36:00
else
{
i = getIndex(directionX,qn.x);
if(i < 0 && qn.x == ex) return qn.step+1;
if(i >= 0)
{
flag = 0;
getBound(directionX[i].head,qn.x,s,e,flag);
if(flag&1 && existpos.find(position(qn.x,s)) == existpos.end())
{
existpos.insert(position(qn.x,s));
qn1.y = s;
qn1.x = qn.x;
qn1.direction = 1;
qn1.step = qn.step+1;
que.push_back(qn1);
}
if(flag&2 && existpos.find(position(qn.x,e)) == existpos.end())
{
existpos.insert(position(qn.x,e));
qn1.y = e;
qn1.x = qn.x;
qn1.direction = 1;
qn1.step = qn.step+1;
que.push_back(qn1);
}
if(qn.x == ex)
{
if(flag == 3 && ey >= s && ey <= e) return qn.step+1;
else if(flag == 2 && ey <= e) return qn.step+1;
else if(flag == 1 && ey >= s) return qn.step+1;
}
}
}
}
return 0;
}
int main()
{
int sx,sy,ex,ey,l,t;
int i;
char ch;
cin>>rtsize;
cin>>sx>>sy>>ex>>ey;
for(i = 0;i < rtsize;i++)
{
cin>>l>>t>>rt[i].right>>rt[i].buttom;
rt[i].left = l-1;
rt[i].top = t-1;
}
processX();
processY();
cout<<bfs(sx,sy,ex,ey)<<endl;
cout<<"press an key to continue...";
cin>>ch;
return 0;
}
//代码提交了4个帖子，汗
//new了很多东西没有清理。反正只执行一次，用完就关的东西
//某处查找可以改成logn的，目前是线性的。
10 楼
Wincpp [专家分：0] 发布于 2008-11-08 10:13:00
/*--------------过河问题--------------------------
编程语言：C++
编程环境：Microsoft Visual C++ 6.0(SP6)
算法：
只要青蛙位置小于桥长，则循环执行下面代码：
往能力范围最远的没有石子的地方跳；若都有石子则跳到能力范围最远处，同时记下踩到一个石子。
--------------------------------------------------*/
#include <iostream>
using namespace std;
unsigned l,//桥长
m;//石子数
unsigned *stone;//动态数组，用来存放石子坐标
unsigned s,//最小步长
t;//最大步长
class FROG
{
private:
unsigned position;//青蛙当前位置
unsigned s; //最小步长
unsigned t; //最大步长
unsigned n; //踩石子数
public:
FROG(unsigned s1,unsigned t1)
{
position=0;
s=s1;
t=t1;
n=0;
}
unsigned ShowNum();//确定踩到的石子数 ok
unsigned CurrPosition();//返回当前位置 ok
bool IsStone(unsigned);//判断某处是否有石子 ok
unsigned BestSteps();//计算最佳的步数
void JumpTo(unsigned);//跳到指定位置 ok
};
int main()
{
cin>>l;
cin>>s>>t>>m;
FROG frog(s,t);
stone=new unsigned[m];
for(int i=0;i<m;i++)
cin>>stone[i];
//小青蛙开始跳
while(frog.CurrPosition()<l)
{
frog.JumpTo(frog.CurrPosition()+frog.BestSteps());
}
//跳跃结束，显示踩到的石子数目
cout<<frog.ShowNum()<<endl;
return 0;
}
unsigned FROG::CurrPosition()
{
return position;
}
unsigned FROG::ShowNum()
{
return n;
}
void FROG::JumpTo(unsigned here)
{
position=here;
}
bool FROG::IsStone(unsigned here)
{
for(int i=0;i<m;i++)
if(here==stone[i])
return true;
return false;
}
unsigned FROG::BestSteps()
{
for(int i=t;i>=s;i--)
if(!IsStone(position+i))
return i;
n++;
return t;
}
我来回复
您所在位置：