2019北大计算机学科夏令营机试题目
2019北大计算机学科夏令营机试题目#
题目链接
密码依然是fighting！
百练上北大夏令营的机试题目，但是很多都找不到可以提交网站的地方，只看了几个能再Virtual Judge上的题目。感受就是题目很长，代码量也不少，题目也有一定难度，时间也很短。总之就是“南”，这些人太厉害了吧！
大概有三个较为简单的小模拟的题目。也没有找到可以提交的OJ。
1.Hopscotch##
题目大意：跳房子的游戏，求一个数字变到另外一个数字最少操作步数。操作H和操作O分别定义如下：
-
if the stone falls into a house (marked as H), we can jump from the current house i to the house 3*i;
-
if the stone falls outside the house (marked as O), we can jump from the current house i to house i/2.(round down).
题目保证操作步数再25步之内。
题解：上面的条件很重要，使得这个题不考虑贪心和DP，而是BFS最短路的问题，因为深度最多25步，而且这个题需要保存路径，输出字典序最小的操作方案。
代码是别人写的，找不到提交的地方。
#include <iostream>#include <string>#include <vector>#include <map>#include <queue>using namespace std;int n, m;struct node{int index;int step;vector<char> s; //记录路径};void BFS(){map<int, bool> mp;queue<node> q;node temp;temp.index = n;temp.step = 0;q.push(temp);while (!q.empty()){node top = q.front();q.pop();for (int i = 0; i < 2; i++){node temp = top;if (i == 0){temp.index = top.index * 3;temp.step = top.step + 1;if (!mp[temp.index]){temp.s.push_back(\'H\');q.push(temp);mp[temp.index] = true;}}else{temp.index = top.index / 2;temp.step = top.step + 1;if (!mp[temp.index]){temp.s.push_back(\'O\');q.push(temp);mp[temp.index] = true;}}if (temp.index == m){int len = temp.s.size();cout << len << endl;for (int i = 0; i < len; i++){cout << temp.s[i];}cout << endl;return;}}}}int main(){while (cin >> n >> m){if (n == 0 && m == 0){break;}BFS();}return 0;}
2. Falling Leaves##
题目大意：
一个二叉搜索树，不断删除树的叶子，给出叶子信息，求这个二叉搜索树的先序遍历。
题解：
逆向读取输入信息，也就是从顶向下构建这个二叉搜索树，建树之后先序遍历即可。建树操作还可以更加熟练一下。
#include <iostream>#include<stdio.h>#include<string>#include<algorithm>#include<cmath>#include<cstring>#include<vector>using namespace std;const int N=30;struct node{char c;node *l,*r;node(char c=\'a\',node *l=NULL,node *r=NULL):c(c),l(l),r(r){}};node tree[30];int id;node *insertTree(node *rt,char val){if(rt==NULL){tree[id].c=val;tree[id].l=NULL;tree[id].r=NULL;return &tree[id++];//这里的下标不重要，只需要保存全部结点}if(val<rt->c)rt->l=insertTree(rt->l,val);else rt->r=insertTree(rt->r,val);return rt;}void preOrder(node *rt){if(rt){putchar(rt->c);preOrder(rt->l);preOrder(rt->r);}}int main(){vector<char>ve;char ch;while(cin>>ch&&ch!=\'$\'){ve.clear();ve.push_back(ch);while(cin>>ch){if(ch==\'*\'||ch==\'$\')break;ve.push_back(ch);}node *root=NULL;id=0;for(int i=ve.size()-1;i>=0;i--){root=insertTree(root,ve[i]);}preOrder(root);puts("");}return 0;}
3.昂贵的聘礼##
题目大意：
交换物品，不同等级的人有不同的物品交换，交换中需要支付一定的钱。eg:物品A+100=物品B。
限制条件是，在全部交换过程中，最高等级的人和最低等级的人等级差不能超过M。
题解：
原本还以为是DP，结果是我傻了。最短路问题，加上枚举最低等级为minLevel的交换者，那么合法的交换者就是等级为minLevel到minLevel+M之间的人。交换建图，额外付出的钱为路径cost，注意方向性。时空复杂度可过，使用Dijkstra的朴素写法即可。
#include <iostream>#include<stdio.h>#include<string>#include<algorithm>#include<cmath>#include<cstring>using namespace std;int m,n;const int N=105;const int INF=0x3f3f3f3f;int price[N],level[N];int edge[N][N];int vis[N];int d[N];void init(){for(int i=0;i<n;i++){for(int j=0;j<n;j++){edge[i][j]=INF;}}for(int i=0;i<n;i++){cin>>price[i]>>level[i];level[i]--;//0开始int x;cin>>x;for(int j=0;j<x;j++){int v,p;cin>>v>>p;v--;edge[v][i]=p;//v到i的价格为p}}}int dijkstr(){for(int i=0;i<n;i++)d[i]=price[i];//把起点当作超级源点for(int i=0;i<n;i++){int temp=INF;int x;//最小点for(int j=0;j<n;j++)if(vis[j]&&d[j]<=temp)temp=d[x=j];vis[x]=0;//不再走for(int j=0;j<n;j++)if(d[x]+edge[x][j]<d[j]&&vis[j])d[j]=d[x]+edge[x][j];}return d[0];//0}int main(){cin>>m>>n;init();int ans=INF;for(int i=0;i<n;i++){int minLevel=level[i];//最小for(int j=0;j<n;j++){if(level[j]-minLevel>m||minLevel>level[j])vis[j]=0;//不可else vis[j]=1;}int cur=dijkstr();// cout<<cur<<endl;ans=min(ans,cur);}cout<<ans<<endl;return 0;}
原本还有两个题，一个题目太长了，看不下去了，一个大模拟的题，我就放弃了。。。