首届全国高校BBS联合程序开发大赛

算法组

选手 A1003    bestivan.bbs@bbs.sjtu.edu.cn

来自 SJTUBBS 饮水思源站

提交题目

A.02

/* * 首届全国高校BBS联合程序开发大赛 * 算法组 题号:A2.跳房子游戏 * 选手 A1003 bestivan.bbs@bbs.sjtu.edu.cn * 来自 SJTUBBS 饮水思源站 */ /* * 算法说明： * 本题的算法为动态规划 * 将(0,0)加入活动队列，设置step(0,0) = gold(0,0) * 从活动队列中取出第一个格子，找到从这个格子开始所有可以跳到的格子 * 计算从这个格子跳过去所能拿到的钱数，与目标格子中的累计最大钱数step(x,y)比较 * 如果超过step(x,y)则更新step(x,y)的值，如果目标格子没有被加入活动区域则将这个 * 格子加入活动区域队列，并且按照格子中的钱币值升序排列 * * 直到队列中已经没有任何格子为止，找到step[][]的最大值输出即可 * * Tips: * 由于数据量很大，需要开一个足够长的队列来存放临时变量 */ #include <iostream.h> //全局变量说明 int arrayx[10000], arrayy[10000]; /*用来存放活动区域， *活动区域是可以被跳到并且尚未计算出最大钱数的格子 *用队列表示，并且严格按照格子中的钱数升序排列 arrayx表示x坐标，arrayy表示y坐标*/ unsigned int data[100][100]; //钱的量，用二维数组存放 unsigned int step[100][100]; //记录跳到某一格时所能拿到的最大的钱数，用二位数组表示 int pt,top; //队列的指针以及队列的顶 /* * 插入队列 * Input:格子的位置x,y * Output:void * 使用方法：程序将获得坐标为(x,y)的格子的钱数，并且以按照钱数升序插入队列中 * 在其之后的元素顺序后移 */ void insert(int x, int y) { int i; for (i = pt; i <top; i++) { if (arrayx[i] == x && arrayy[i] ==y) return; } for (i = top; i > pt && data[arrayx[i-1]][arrayy[i-1]] > data[x][y]; i--) { arrayx[i] = arrayx[i-1]; arrayy[i] = arrayy[i-1]; } arrayx[i] = x; arrayy[i] = y; top++; } void main() { int n,k; int i,j; unsigned int tmp; while (cin>>n>>k) { for (i = 0; i < n; i++) for (j = 0; j < n; j++){ step[i][j] = 0; cin>>data[i][j]; } //initialize pt = 0;top = 1; arrayx[pt] = arrayy[pt] = 0; step[0][0] = data[0][0]; while (pt < top) { for (i = arrayx[pt] - k < 0?0:arrayx[pt] - k; i < (arrayx[pt] + k + 1 > n?n:arrayx[pt] + k + 1); i++) { if (data[i][arrayy[pt]] > data[arrayx[pt]][arrayy[pt]] && step[arrayx[pt]][arrayy[pt]]+data[i][arrayy[pt]]>step[i][arrayy[pt]]) { //insert insert(i, arrayy[pt]); step[i][arrayy[pt]] = step[arrayx[pt]][arrayy[pt]]+data[i][arrayy[pt]]; } } for (i = arrayy[pt] - k < 0?0:arrayy[pt] - k; i < (arrayy[pt] + k + 1 > n?n:arrayy[pt] + k + 1); i++) { if (data[arrayx[pt]][i] > data[arrayx[pt]][arrayy[pt]] && step[arrayx[pt]][arrayy[pt]]+data[arrayx[pt]][i]>step[arrayx[pt]][i]) { //insert insert(arrayx[pt], i); step[arrayx[pt]][i] = step[arrayx[pt]][arrayy[pt]]+data[arrayx[pt]][i]; } } pt++; } tmp = 0; for (i = 0; i < n; i++) for (j = 0; j < n; j++){ if (tmp < step[i][j]) tmp = step[i][j]; } cout<<tmp<<endl<<endl; } }

A.03

/* * 首届全国高校BBS联合程序开发大赛 * 算法组 题号:A3.imcc---糟糕的向导 * 选手 A1003 bestivan.bbs@bbs.sjtu.edu.cn * 来自 SJTUBBS 饮水思源站 */ /* * 算法说明： * 本题的关键是寻找Articulation Points * 我们的算法是根据DSP(深度优先搜索)来找顶层祖先的方法确定关节点 * 这个算法的优点是速度极快，而且空间消耗非常低 * 具体算法请参见http://www.cclub.metu.edu.tr/~fagelgi/studies/olimp/implements/bicon/bicon.htm * ---- ALGORITHM for finding Articulation Points * * Tips: * 并不用真的构造DSP树，只需要记录其节点顺序即可 * 要考虑Root的问题，当且仅当root有两个以上子树时才被判定为关节点 */ #include <iostream.h> #include <string.h> //全局变量说明 char city[100][40]; //城市名称，允许100个城市，39个字节长 char map[100][100]; //邻接矩阵，用来存放道路信息 char searchlog[100]; //记录某个节点i是否已经被DSP过 char res[100]; //记录某个节点是否为关节点res[i]=1则说明是 int result; //记录最后的结果数 int id,root,branch; //临时变量，id存放了当前分配的节点编号，root存放了根节点的编号，branch存放了子树数 int count, route; //count表示城市数，route表示道路数 /* * DSP处理器 * Input:节点编号node * Output: 顶层祖先，即与node相连并且被分配的id最小的节点号 * 使用方法：参照算法说明，本函数为关键函数，如果判断子元素的最顶层祖先为自己则说明自己是关节点 * 因为这说明他们无法与子树以外的节点相连 */ int DSP(int node) { int i,min,m=0; ++id; searchlog[node]=id; min=id; for (i=0; i<count; ++i) if (map[node][i]) if (!searchlog[i]) { if (node==root) ++branch; m=DSP(i); if (m<min) min=m; else if (m==searchlog[node]) { //got it! if (!res[node]) { //这是新发现的 res[node] = 1; result++; } } } else min=(min>=searchlog[i]) ? searchlog[i] : min; return min; } /* * 由于地图中可能存在若干个分离图，所以每找到一个分离的图就要对它进行一次DSP * start函数用于初始化每次dsp所用的变量 * 并且负责判断root节点是否是根节点 */ void start(int node) { root = node; id = 0; branch = 0; DSP(node); if (branch>1) { if (!res[node]) { res[node] = 1; result++; } } else { if (res[node]) { result--; res[node] = 0; } } } int main() { int num=0; int i,j; int from, to; char tmp1[40], tmp2[40]; while (1) { cin>>count; if (!count) break; //输入城市，初始化map for (i = 0; i< count; i++ ) { cin>>city[i]; for (j = 0; j < count; j++) map[i][j]=0; } //重新排序城市，按照升序 for (i = 0; i < count; i++) for (j = i+1; j < count; j++) { if (strcmp(city[i],city[j])>0) { //该交换咯 strcpy(tmp1, city[i]); strcpy(city[i], city[j]); strcpy(city[j], tmp1); } } //输入城市道路信息 cin>>route; for (i = 0; i < route; i++) { cin>>tmp1>>tmp2; for (from = 0; from < count; from++) { if (!strcmp(tmp1,city[from])) break; } for (to = 0; to < count; to++) { if (!strcmp(tmp2,city[to])) break; } map[from][to] = map[to][from] = 1; } //清理临时变量 for (i = 0; i < count; i++) {searchlog[i] = 0; res[i] = 0;} result = 0; //DSP查找~~~ for (i = 0; i < count; i++) { if (!searchlog[i]) start(i); } //输出 if (num > 0) cout<<endl; cout<<"City map #"<<++num<<": "<<result<<" camera(s) found"<<endl; for (i = 0; i < count; i++) { if (res[i]) cout<<city[i]<<endl; } } return 0; }

A.04

/* * 首届全国高校BBS联合程序开发大赛 * 算法组 题号:A4.Buy the Ticket * 选手 A1003 bestivan.bbs@bbs.sjtu.edu.cn * 来自 SJTUBBS 饮水思源站 */ /* * 算法说明： * 这是一道数学题，排列数n = (C(m+n,n) - C(m+n,n-1))*m!*n! * 通过化简得：n = (m+n)!(m-n+1)/(m+1) * tips: * 由于200!远远超过UINT所能表示的数字，所以要使用高精度运算 * 为了避免使用高精度除法，要约去m+1项 * 当n!=0时，运算(m+n)阶乘的时候要少乘一个m+1 * n=0时，m-n+1=m+1,两个都不算 */ #include <iostream.h> //全局变量说明 int hd[1000]; //高精度寄存器 /* * 高精度乘法器 * Input:乘数n * Output:void * 使用方法：将n与hd[]寄存器内的高精度数相乘，结果写入hd[]中 */ void multi(int n) { int res=0, carry=0; int i; for (i = 0; i < 1000; i++) { res = hd[i] * n + carry; hd[i] = res % 10; carry = res / 10; } } int main() { unsigned long sum; int m,n; int i; int count=1; while (1) { cin>>m>>n; if (m==0 && n==0) return 0; if (n > m) { cout<<"Test #"<<count++<<":"<<endl; cout<<0<<endl; continue; } for (i = 0; i < 1000; i++) hd[i] = 0; hd[0] = 1; for (i = 1, sum = 1; i <= m+n; i++) if (i != m+1) multi(i); if (n != 0) multi(m-n+1); cout<<"Test #"<<count++<<":"<<endl; for (i = 999; i > 0 && hd[i] ==0; i--); for (;i>=0;i--) cout<<hd[i]; cout<<endl; } return 0; }