0%

背景

近来都在刷CCF的题,准备认证考试。最近几天开始刷其中的第四题,一般而言,CCF的第四题都是图论题。对于我这样之前没怎么刷题的人来说,图论题看上去就感觉很难,主要是感觉到很陌生,因为在实际的开发过程中比较少用到图这样的数据结构,都是线性的数据结构,连树都比较少用。

但是在刷得比较多的图论题后,发现其实图论题好像也就那么回事,也不是说简单,主要感觉来来去去都是考那几个东西,如果是没有接触过或者不会做的话,可能有点难,但是只要接触过相似的,直接套板子修改就行了(当然也有可能是我还接触的不够多 XD),另外,就是感觉没有什么题是 DFS/BFS 不能破,只是会不会超时,能拿多少的分的问题(对于 CCF 认证只想拿 300 分而言,有几十分就够了),其实很多算法的核心也就是 DFS 与 BFS。

所以在今晚刷完了 CCF 往年所有的第四题后,总结一下最近接触的图论问题及解法。

阅读全文 »

Problem

问题描述

  给定一个公司的网络,由 n 台交换机和 m 台终端电脑组成,交换机与交换机、交换机与电脑之间使用网络连接。交换机按层级设置,编号为 1 的交换机为根交换机,层级为 1。其他的交换机都连接到一台比自己上一层的交换机上,其层级为对应交换机的层级加 1。所有的终端电脑都直接连接到交换机上。
  当信息在电脑、交换机之间传递时,每一步只能通过自己传递到自己所连接的另一台电脑或交换机。请问,电脑与电脑之间传递消息、或者电脑与交换机之间传递消息、或者交换机与交换机之间传递消息最多需要多少步。

阅读全文 »

Problem

问题描述

  给定一段文字,已知单词a1, a2, …, an出现的频率分别t1, t2, …, tn。可以用01串给这些单词编码,即将每个单词与一个01串对应,使得任何一个单词的编码(对应的01串)不是另一个单词编码的前缀,这种编码称为前缀码。
  使用前缀码编码一段文字是指将这段文字中的每个单词依次对应到其编码。一段文字经过前缀编码后的长度为:
  L=a1的编码长度×t1+a2的编码长度×t2+…+ an的编码长度×tn
  定义一个前缀编码为字典序编码,指对于1 ≤ i < nai的编码(对应的01串)的字典序在ai+1编码之前,即a1, a2, …, an的编码是按字典序升序排列的。
  例如,文字E A E C D E B C C E C B D B E中, 5个单词A、B、C、D、E出现的频率分别为1, 3, 4, 2, 5,则一种可行的编码方案是A:000, B:001, C:01, D:10, E:11,对应的编码后的01串为1100011011011001010111010011000111,对应的长度L为3×1+3×3+2×4+2×2+2×5=34。
  在这个例子中,如果使用哈夫曼(Huffman)编码,对应的编码方案是A:000, B:01, C:10, D:001, E:11,虽然最终文字编码后的总长度只有33,但是这个编码不满足字典序编码的性质,比如C的编码的字典序不在D的编码之前。
  在这个例子中,有些人可能会想的另一个字典序编码是A:000, B:001, C:010, D:011, E:1,编码后的文字长度为35。
  请找出一个字典序编码,使得文字经过编码后的长度L最小。在输出时,你只需要输出最小的长度L,而不需要输出具体的方案。在上面的例子中,最小的长度L为34。

阅读全文 »

Problem

问题描述

某股票交易所请你编写一个程序,根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。
该程序的输入由很多行构成,每一行为一条记录,记录可能有以下几种:
1. buy p s 表示一个购买股票的买单,每手出价为p,购买股数为s。 2. sell p s 表示一个出售股票的卖单,每手出价为p,出售股数为s。 3. cancel i表示撤销第i行的记录。

如果开盘价为p0,则系统可以将所有出价至少为p0的买单和所有出价至多为p0的卖单进行匹配。因此,此时的开盘成交量为出价至少为p0的买单的总股数和所有出价至多为p0的卖单的总股数之间的较小值。    你的程序需要确定一个开盘价,使得开盘成交量尽可能地大。如果有多个符合条件的开盘价,你的程序应当输出最高的那一个。

阅读全文 »

Problem

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?'and '*'.

1
2
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

阅读全文 »

Problem

问题描述

  俄罗斯方块是俄罗斯人阿列克谢·帕基特诺夫发明的一款休闲游戏。
  游戏在一个15行10列的方格图上进行,方格图上的每一个格子可能已经放置了方块,或者没有放置方块。每一轮,都会有一个新的由4个小方块组成的板块从方格图的上方落下,玩家可以操作板块左右移动放到合适的位置,当板块中某一个方块的下边缘与方格图上的方块上边缘重合或者达到下边界时,板块不再移动,如果此时方格图的某一行全放满了方块,则该行被消除并得分。
  在这个问题中,你需要写一个程序来模拟板块下落,你不需要处理玩家的操作,也不需要处理消行和得分。
  具体的,给定一个初始的方格图,以及一个板块的形状和它下落的初始位置,你要给出最终的方格图。

阅读全文 »

引言

在准备做Windows程序设计的大作业时,需要用到 Mysql。打开了 Mysql WorkBench 连接本地数据库时,提示要输入 root 密码,试了几个常用密码无果后,发现自己再次忘记了 Mysql 的 root 密码。但是没有关系,本人已经习惯忘记各种不太常用的账号密码了,驾轻就熟地打开百度搜索相关方法,却发现来来去去都是那同一个方法,而且还因为版本问题与实际情况有些差异,最终还是花费了不少的时间,有点难受,遂写一文记录一下。

阅读全文 »

Problem

Given a string array words, find the maximum value of length(words[i]) * length(words[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

1
2
3
Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
阅读全文 »

背景

在上周的时候,打算在Ubuntu下查看在Windows下QQ接受到的项目代码,然后顺便就整理了一下目录,新建了一个文件夹,将实验室相关的文件剪切复制到该文件夹。后切换回Windows,发现文件夹没有建成功,而刚才剪切的文件不见了。

无独有偶,本周一上课纪录模式识别笔记时,顺手归档了一下这门课文件夹下的作业,课件,笔记(在Windows下的Ntfs分区中),然后周二上课打开Windows系统后,发现文件丢失,新建的归档文件夹也不见了,然后昨天修改的markdown笔记也损坏无法打开。

阅读全文 »