第七届北京师范大学程序设计竞赛热身赛第一场 解题报告

第七届北京师范大学程序设计竞赛热身赛第一场 解题报告

A.Primary Arithmetic
模拟题,求两个数相加过程中进位的个数.先把数分解成数字,然后模拟加法即可.注意输出时候单复数的处理.从提交情况看,有的同学忘记了数组清0.

B.Eeny Meeny Moo
约瑟夫问题.队列模拟即可.也有数学方法.

C.The Circumference of the Circle
几何计算.可以推出公式三角形外接圆半径r=abc/4S.

D.Code the Tree
字符串处理加模拟,按照题目描述处理字符串,然后建树,模拟删点就可以了.注意只有一个节点的时候要有一个空行输出.

E.Deli Deli
字符串处理.单词单数变复数,建立字典,字典中有的直接输出,没有的话按照规则分情况处理.

F.人工智能?
字符串处理.寻找U=xxx,I=xxx,P=xxx形式的字符,然后转换成实数,再做运算.

G.Error Correction
直接判断有多少行和列的和是奇数,如果恰好有1行和1列是奇数,修改行列交点即可,如果都是偶数直接OK,其余是不可能情况.

H.YC大牛的判题任务
多关键字排序.使用各种排序算法都可以.简单介绍一下C++ algorithm库里的快速排序sort.
复制内容到剪贴板
代码:
定义如下
库文件:
#include<iostream>
#include<algorithm>
using namespace std;

结构定义
struct node
{
        int t,n;
}p[3000];

比较函数
bool cmp(node a,node b)//a应该排在b之前的时候返回真,
{
        if(a.t!=b.t)return a.t<b.t;
        return a.n<b.n;
}

排序直接用
sort(p,p+m,cmp);//表示对指针在区间[p,p+m)内的元素排序

详细用法参考C++ STL.
I.Frogger
计算出任意两个石头的距离,建立图求出发点到目的点的"最短路径",使用Dijkstra算法.此处的路径长定义为路径上最长边的长度.

[ 本帖最后由 vw009 于 2009-4-5 01:59 编辑 ]

TOP

D居然一句话带过…………

TOP

贴个D的代码吧

复制内容到剪贴板
代码:
#include<iostream>
#include<cstring>

#define N 60

using namespace std;

int stack[N], top;
char str[1000];
bool g[N][N];
int deg[N], ans[N];
int n;

int main()
{
        int i, j, k;
        while (gets(str))
        {
                memset(deg, 0, sizeof(deg));
                memset(g, 0, sizeof(g));
                top = 0;
                n = 0;
                int num = 0;
                for (i = 0; str[i]; i++)
                {
                        if (str[i] >= '0' && str[i] <= '9') num = num * 10 + str[i] - '0';
                        else if (num != 0)
                        {
                                stack[top++] = num;
                                if (n < num) n = num;
                                num = 0;
                        }
                        if (str[i] == ')')
                        {
                                top--;
                                if (top != 0)
                                {
                                        g[stack[top]][stack[top - 1]] = g[stack[top - 1]][stack[top]] = 1;
                                        deg[stack[top]]++, deg[stack[top - 1]]++;
                                }
                        }
                }
                if (n > 1)
                {
                        for (k = 1; k < n; k++)
                        {
                                for (i = 1; i <= n; i++)
                                        if (deg[i] == 1)
                                        {
                                                for (j = 1; j <= n; j++)
                                                        if (g[i][j])
                                                        {
                                                                ans[k] = j;
                                                                g[i][j] = g[j][i] = 0;
                                                                deg[i]--, deg[j]--;
                                                                break;
                                                        }
                                                break;
                                        }
                        }
                        printf("%d", ans[1]);
                        for (i = 2; i < n; i++)
                                printf(" %d", ans[i]);
                        printf("\n");
                }
                else printf("\n");
        }
        return 0;
}
北师大ACM国际大学生程序设计竞赛欢迎你!
点击进入->: ACM竞赛 蛋蛋讨论区

TOP

回复 沙发 的帖子

字符串处理,的确没有什么好说的,而且很多时候字符串处理又很恶心。。。。

TOP

能详细点吗:L :L :L

TOP

好呀

强大 ~~~~~~~~~~~~~~~~~~·

TOP

有参考程序吗?我很想借鉴一下。

TOP

Frogger 这题挺迷惘的,解题报告上说的用dijkstra求最短路径

你看第二组数据如果按你提示的思想,找最短路径的话,从第一个点到第二个点明最短路径明是 1 -> 2 那青蛙距离 应该是2..

但是按照青蛙距离的定义确实应该是 1->3->2 这条路径时的 1.414 ,但是这时路径长度是 2.828 并不是从 1 到 2 的最短路径

难道我题目理解错了?
带电、含毒、有辐射、勿抚摸!

TOP

要找不不是1到2的最短路径,而是题目说的minmax distance

TOP

回复 8楼 的帖子

对不起,写解题报告时候没有注意,已经修改好了

TOP

一点质疑

楼主说Frogger是求单源最短路径,算法是Dijkstra算法,窃以为是求 图的最小生成树 (只要生成树中包含目的顶点时就可以结束) ,因为只要保证每步跳跃的路长最短即可,并不要求跳跃的总距离最短,这符合最小生成树的概念,求最小生成树算法是用Prime算法或 克鲁斯卡尔算法

下面我的代码,接触ACM时间不长,还请路过高手指点
复制内容到剪贴板
代码:

#include<stdio.h>
#include<limits.h>
#include<math.h>

#define MAX_VERTEXT_NUM 200
typedef struct  
{
int x;
int y;
} Point;
typedef struct  
{
Point vertex[MAX_VERTEXT_NUM];
int verNum;
} AdjMatrix;
typedef struct {
int adjvex;
double lowcost;
}Edge;
Edge closedge[MAX_VERTEXT_NUM];
#define  INF INT_MAX
#define  END_VERTEX 1
int Minium(Edge closedge[] , int n)
{
double minValue = INF;
int minIndex = -1;
for(int i = 0 ; i < n; i++)
  if(closedge[i].lowcost < minValue)
  {
   minValue = closedge[i].lowcost;
   minIndex = i;
  }
return minIndex;
}
double Distance(const Point& p1,const Point& p2)
{
double dis = (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
return sqrt(dis);
}
double MiniSpanTree(const AdjMatrix* g,int startVer)
{
int i,e;
for(i = 0 ; i < g->verNum; i++)
{
  closedge[i].adjvex = startVer;
  closedge[i].lowcost = Distance(g->vertex[i] , g->vertex[startVer]);
}
//将初始点先归入另一个集合
closedge[startVer].lowcost = INF;

double maxDis = -INF;
//找最小生成树的n-1条边
for(e = 1; e < g->verNum ; e++)
{
  int k = Minium(closedge,g->verNum);
  if(closedge[k].lowcost > maxDis) maxDis = closedge[k].lowcost;
  if(k == END_VERTEX) break;
  closedge[k].lowcost = INF;
  for(i = 0 ; i < g->verNum; i++)
  {
   double dis = Distance(g->vertex[k],g->vertex[i]);
   if(dis < closedge[i].lowcost && closedge[i].lowcost != INF)
   {
    closedge[i].lowcost = dis;
    closedge[i].adjvex = k;
   }
  }
}
return maxDis;
}
int main()
{
AdjMatrix g;
int count = 0;
while(1)
{
  scanf("%d",&g.verNum);
  if(g.verNum == 0) break;
  for(int i = 0 ; i < g.verNum; i++)
   scanf("%d%d",&(g.vertex[i].x) , &(g.vertex[i].y));
  printf("Scenario #%d\n",++count);
  printf("Frog Distance = %.3lf\n\n",MiniSpanTree(&g,0));
}
return 0;
}
[ 本帖最后由 清蒸水皮 于 2009-4-8 14:19 编辑 ]

TOP

回复 11楼 的帖子

这个题目的并不是最短路径,但是它符合最短路径问题一类的最优子结构,所以我们可以使用Dijkstra算法来求,

或者可以把路径长的定义理解成路径上的最长边

这种变形在ACM中也是很多,比如也可以把路径长定义为边权之和等等.....

至于楼上用的这个,其实就是Dijkstra,

Prim和Dijkstra的思想是很接近的,在实现上差别是很小的

TOP

回复 11楼 的帖子

最小生成树定义本身是指的是边权总和最小,和这题题意关系不大,只是求解过程通常是从小到大加边,像您这样用这个思想来解这个题是可以的。但是严格来说这个模型既不是最短路也不是最小生成树,只是说求解的时候可以用类似的思想方法!
北师大ACM国际大学生程序设计竞赛欢迎你!
点击进入->: ACM竞赛 蛋蛋讨论区

TOP

可以把标程贴出来吗?我想看F题的代码..

TOP

回复 14楼 的帖子

F
复制内容到剪贴板
代码:
#include
using namespace std;
int main()
{
        int cases,t;
        int i;
        char line[2500];
        scanf("%d\n",&cases);
        for(t=1;t<=cases;++t)
        {
                double U=0,I=0,P=0;
                int pt;
                printf("Problem #%d\n",t);
                gets(line);
                for(i=0;line[i+1];++i)
                {
                        if(line[i]=='P'&&line[i+1]=='=')
                        {
                                i+=2;
                                pt=0;
                                while(line[i]!='k'&&line[i]!='M'&&line[i]!='m'&&line[i]!='W')
                                {
                                        pt*=10;
                                        if(line[i]=='.')pt=1;
                                        else        if(pt)
                                                P=(P*pt+line[i]-'0')/pt;
                                        else
                                                P=P*10+line[i]-'0';
                                        ++i;
                                }
                                if(line[i]=='k')P*=1000;
                                if(line[i]=='M')P*=1000000;
                                if(line[i]=='m')P/=1000;
                        //       
                        }
                        if(line[i]=='I'&&line[i+1]=='=')
                        {
                                i+=2;
                                pt=0;
                                while(line[i]!='k'&&line[i]!='M'&&line[i]!='m'&&line[i]!='A')
                                {
                                        pt*=10;
                                        if(line[i]=='.')pt=1;
                                        else        if(pt)
                                                I=(I*pt+line[i]-'0')/pt;
                                        else
                                                I=I*10+line[i]-'0';
                                        ++i;
                                }
                                if(line[i]=='k')I*=1000;
                                if(line[i]=='M')I*=1000000;
                                if(line[i]=='m')I/=1000;
                        //       
                        }
                        if(line[i]=='U'&&line[i+1]=='=')
                        {
                                i+=2;
                                pt=0;
                                while(line[i]!='k'&&line[i]!='M'&&line[i]!='m'&&line[i]!='V')
                                {
                                        pt*=10;
                                        if(line[i]=='.')pt=1;
                                        else if(pt)
                                                U=(U*pt+line[i]-'0')/pt;
                                        else
                                                U=U*10+line[i]-'0';
                                        ++i;
                                }
                                if(line[i]=='k')U*=1000;
                                if(line[i]=='M')U*=1000000;
                                if(line[i]=='m')U/=1000;
                        }
                }
                //printf("P=%lf\n",P);
                //printf("I=%lf\n",I);
                //printf("U=%lf\n",U);
                if(U==0)printf("U=%.2lfV\n\n",P/I);
                if(I==0)printf("I=%.2lfA\n\n",P/U);
                if(P==0)printf("P=%.2lfW\n\n",U*I);
        }
        return 0;
}

TOP