【2018SCUACM FurtherTraining 19 模拟习题】

题目来源

A:UVA215

B:UVA439

C:UVA806

D:UVA699

解题报告

A:大模拟……通过\(DFS\)来获取每个单元格的值(如果是数,返回;如果是表达式,继续\(DFS\)求值),同时判断是否有环。注意输入如果开头是\(-\)或者开头是数字都代表这个格子是个数字,否则才是读表达式。计算表达式可用栈来实现,不熟悉的可以看看:栈的应用:表达式求值 由于只有\(+\)和\(-\),实际上会简化很多,就是注意细节就行了。

B:骑士游历问题,国际象棋棋盘走日字,简单\(BFS\)求最短路。

C:四分树图像和序列互相转换。路径描述为五进制数,这个数从右往左数第\(k\)位表示四分树第\(k\)层走的是哪个结点。图像转换序列时直接把图像分为四块,\(DFS\)建树,最后遍历一遍树并记录各黑点的路径即可。给出序列时,先将\(10\)进制数转为\(5\)进制数得到路径,再根据路径跑一遍四分树(直接在图里跑就行)。最开始整个图全白,读入一个黑点染黑一部分。注意特判全黑和全白的情况,一个比较注重细节的大模拟。另外,注意输出序列时一行只能输出\(12\)个数字。

D:考查二叉树的前序遍历知识。我们按照给出的谦虚遍历跑\(DFS\)同时记录每个宽度编号的落叶数量就行,把根节点的宽度编号设置为\(1000\),避免往左走的时候编号减到负数从而出现数组下标越界的问题。走一步读一个数据就行,如果是\(-1\)就返回上一层,否则继续。

 

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*