ACM笔记-并查集

以POJ 1611 为例

Description

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.

In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).

阅读全文

2.我们怎么翻墙

目前翻墙技术按费用来说共分为两种:收费的和免费的(额,估计以后也是这样)

按照技术来分大致有ssh,vpn,在线代理,修改dns,修改hosts,gae,代理软件(某门,tor等)

本着实用至上的原则,我在此并不会按照技术分类一种一种介绍,而是按照GFW的不同封锁等级介绍与之对应的解决方法

阅读全文

Manhattan距离和Chebyshev距离

以HDU 4311和HDU 4312为例

img

如图所示,Manhattan距离是指 1-2,2-4,3-4,4-1之间距离都为1,而对角线路线不可达状态下的两点距离

Chebyshev距离是指除曼哈顿距离外,对角线路线可达且距离为1的情况下(即 1-4,2-3之间距离为1),两点之间的距离

平面上两点间的 Manhattan 距离为 |x1-x2| + |y1-y2|,平面上两点间的 Chebyshev距离为 max(|x1-x2|, |y1-y2|)。

阅读全文

ACM笔记-动态规划求Levenshtein distance

以HDU 4323为例

首先介绍一下什么叫做Levenshtein distance

编辑距离,又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字>符替换成另一个字符,插入一个字符,删除一个字符。
sitten (k→s)

sittin (e→i)

sitting (→g)

俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。

from Wikipedia


阅读全文

ACM笔记-DFS

DFS是最基本的算法之一了

以POJ 3009为例

Curling 2.0

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 7176 Accepted: 3003

Description

On Planet MM-21, after their Olympic games this year, curling is getting popular. But the rules are somewhat different from ours. The game is played on an ice game board on which a square mesh is marked. They use only a single stone. The purpose of the game is to lead the stone from the start to the goal with the minimum number of moves.

阅读全文