【题目自解】北京大学2016计算机学科夏令营上机考试
A:分段函数（NOI 1.4编程基础之逻辑表达式与条件分支）
解题思路
这题就像逗我玩似的，这连简单题都算不上。
AC代码
#include<cstdio> using namespace std; int main() { double x, y; scanf("%lf", &x); if (x >= 0 && x < 5)y = 2.5 - x; else if (x >= 5 && x < 10)y = 2 - 1.5*(x - 3)*(x - 3); else if (x >= 10 && x < 20)y = x / 2 - 1.5; printf("%.3lf", y); return 0; }
B:单词翻转（NOI 1.7编程基础之字符串）
解题思路
简单题，读取一整行用C的gets()函数，VS2017没有这个函数，Dev和OJ可以过。
AC代码
#include<cstdio> #include<cstring> using namespace std; int main() { char s[505]; gets(s); int len = strlen(s); for (int i = 0; i < len; i++) { if (s[i] == ' ')printf(" "); if (s[i] == '_')continue; else { int wlen = 0; int tmp = i; while (s[tmp] != ' ') { wlen++; tmp++; if (tmp >= len) break; } for (int j = i + wlen - 1; j >= i; j--) { printf("%c", s[j]); s[j] = '_'; } } } return 0; }
C:反反复复（NOI 1.8编程基础之多维数组）
解题思路
简单题，最基础的二维数组。
AC代码
#include<cstdio> #include<cstring> int N[205][205]; int main() { int m, n;//列和行 char s[205]; scanf("%d", &m); scanf("%s", s); int len = strlen(s); n = len / m; int cnt = 1; for (int i = 0; i < n; i++)//按行读入 { if (cnt % 2)//奇数行正向读入 { for (int j = 0; j < m; j++)N[i][j] = s[i*m + j]; cnt++; } else//偶数行反向读入 { for (int j = m - 1; j >= 0; j--)N[i][m - 1 - j] = s[i*m + j]; cnt++; } } for (int j = 0; j < m; j++)//按列输出 { for (int i = 0; i < n; i++)printf("%c", N[i][j]); } return 0; }
G:重建二叉树
解题思路
详细讲解见二叉树专题。核心思想其实很简单，用数组就可以直接做，无非就是根据前序遍历的结果对中序遍历左右子串分别递归，最后后序打印根节点的值。
AC代码
#include<cstdio> #include<cstring> char s1[10000];//存储前序 char s2[10000];//存储中序 void f(int l, int l2, int r2)//总是需要前序遍历的起点和中序遍历的两端，以确定根结点和左右子树 { if (l2 == r2)return;//没有元素了 char r = s1[l];//根结点 int loc = l2; while (s2[loc] != r)loc++;//找到根结点在中序遍历中的位置 f(l + 1, l2, loc); f(l + loc + 1 - l2, loc + 1, r2);//画一画情况就知道了 printf("%c", r); } int main() { while (scanf("%s%s", s1, s2) != EOF) { int len = strlen(s1); f(0, 0, len); printf(" "); } return 0; }
H:丛林中的路
解题思路
中等题，最小生成树的模板题。
AC代码
#include<cstdio> #include<algorithm> using namespace std; const int N = 30; int p[N];//父结点,A代表编号0 int n, ans;//村落数目,最小开销 struct Edge { int a, b; int cost; }edge[80]; bool cmp(Edge a, Edge b) { return a.cost < b.cost; } void init() { for (int i = 0; i < n; i++)p[i] = i; ans = 0; } int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); } void Union(int i) { int a = find(edge[i].a); int b = find(edge[i].b); if (a == b)return; else { p[b] = a; ans += edge[i].cost; } } int main() { int k, c, cnt;//与当前结点相连的村落数，和道路开销,以及总道路数目 char a[5], b[5];//两结点名称 while (scanf("%d", &n) != EOF && n != 0) { cnt = 0; for (int i = 0; i < n - 1; i++) { scanf("%s%d", a, &k); for (int j = 0; j < k; j++) { scanf("%s%d", b, &c); edge[cnt].cost = c; edge[cnt].a = a[0] - 'A'; edge[cnt].b = b[0] - 'A'; cnt++; } } sort(edge, edge + cnt, cmp); init(); for (int i = 0; i < cnt; i++) Union(i); printf("%d ", ans); } return 0; }
F:Dungeon Master
解题思路
三维地图广搜，算是广搜的模板题了。写出来就AC了，没有什么注意点。
AC代码
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int l, r, c; char a[31][31][31];//存储地图 int vis[31][31][31];//访问标记 int dx[6] = { 0,0,1,-1,0,0 }; int dy[6] = { 1,-1,0,0,0,0 }; int dz[6] = { 0,0,0,0,1,-1 }; struct Node { int z, x, y;//坐标 int t;//计时 Node() :z(-1), x(-1), y(-1),t(0){} Node(int zz, int xx,int yy):z(zz), x(xx),y(yy),t(0){} }; Node s, e;//起点和终点 bool noWay(int z,int x, int y) { if (z < 0 || z >= l || x < 0 || x >= r || y < 0 || y >= c)return true; if (vis[z][x][y])return true; if (a[z][x][y] == '#')return true; return false; } void bfs() { queue<Node> q; memset(vis, 0, sizeof(vis)); q.push(s);//起点入队 vis[s.z][s.x][s.y] = 1; while (!q.empty())//开始广搜 { Node cur = q.front(); if (cur.x == e.x&&cur.y == e.y&&cur.z == e.z) { printf("Escaped in %d minute(s). ", cur.t); return; } q.pop(); for (int i = 0; i < 6; i++) { int nz = cur.z + dz[i]; int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if (noWay(nz, nx, ny))continue; Node next(nz, nx, ny); vis[nz][nx][ny] = 1; next.t = cur.t + 1; q.push(next);//入队 } } printf("Trapped! "); } int main() { while (scanf("%d%d%d", &l, &r, &c) != EOF && !(l == 0 && r == 0 && c == 0)) { for (int k = 0; k < l; k++) { getchar(); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { scanf("%c", &a[k][i][j]); if (a[k][i][j] == 'S') { s.z = k; s.x = i; s.y = j; } if (a[k][i][j] == 'E') { e.z = k; e.x = i; e.y = j; } } getchar();//换行符 } } bfs(); } return 0; }
D:文件结构“图”
解题思路
之前的一道程设作业题，确实挺麻烦的，自己第一次做就WA了，大佬AC代码如下。
AC代码
#define TAB "| " #include<stdio.h> #include<string.h> #include<string> #include<algorithm> using namespace std; int cases=1; char str[35]; bool isFinish=false; void deal(int tab_num) { string file_name[35]; int file_num=0; scanf("%s",str); if (tab_num==0 && str[0]!='#') { if (cases>1) printf(" "); printf("DATA SET %d: ",cases); printf("ROOT "); } while (true) { if (str[0]=='*' || str[0]==']') break; else if (str[0]=='#') { isFinish=true; return; } else if (str[0]=='f') file_name[file_num++]=str; else if (str[0]=='d') { for (int i=0;i<tab_num+1;i++) printf("%s",TAB); printf("%s ",str); deal(tab_num+1); } scanf("%s",str); } sort(file_name,file_name+file_num); for (int i=0;i<file_num;i++) { for (int j=0;j<tab_num;j++) printf("%s",TAB); printf("%s ",file_name[i].c_str()); } return; } int main() { //freopen("output.txt","w",stdout); while (!isFinish) { deal(0); cases++; } return 0; }