分类 算法 下的文章

这是唯一一篇完全撕掉之前的文章,重新撰写的文章。

文章之前的标题是《不定时更新的 ACM 模板》

然鹅现在,完结啦!!!撒花!!!(???)

退役来,多的就不说了,模板打包成 PDF 保留。

比赛模板.pdf

以前一直以为栈是个很复杂的东西,今天第一次用这个东西写题居然一次AC,欣喜之余发篇文纪念一下 #(滑稽)

- 阅读剩余部分 -

碰到一个题目

题目描述

玛雅人有一种密码,如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串,(2=<N<=13)该字符串中只含有0,1,2三种数字,问这个字符串要移位几次才能解开密码,每次只能移动相邻的两个数字。例如02120经过一次移位,可以得到20120,01220,02210,02102,其中20120符合要求,因此输出为1.如果无论移位多少次都解不开密码,输出-1。

输入

第一行输入N,第二行输入N个数字,只包含0,1,2

输出

样例输入

5
02120

样例输出

1

虽然知道是bfs,但实现起来总觉得哪里不对,参考大佬们的博客后解决了几个难点:

  • 存储类型 虽然题目说是输入n个数,但是使用字符串存储会使后续的处理更方便,题目出处九度OJ_1482输入写的也是长度为n的字符串

- 阅读剩余部分 -

转载自ICS161,学英语,自娱自乐

Traversal of graphs and digraphs

To traverse(遍历) means to visit the vertices in some systematic order. You should be familiar with various traversal methods for trees:

preorder: visit each node before its children.
postorder: visit each node after its children.
inorder (for binary trees only): visit left subtree, node, right subtree.

We also saw another kind of traversal, topological ordering(拓扑排序), when I talked about shortest paths.

Today, we'll see two other traversals: breadth first search (BFS) and depth first search (DFS). Both of these construct spanning trees with certain properties useful in other graph algorithms. We'll start by describing them in undirected graphs, but they are both also very useful for directed graphs.



- 阅读剩余部分 -