匈牙利算法

概念

交错路

交错路:设P是图G的一条路,如果P的任意两条相邻的边一定是一条属于M而另一条不属于M,就称P是一条交错路。

通俗点来说,就是把一个图中的路径染成红黑两种。然后找出一条路,使这条路红黑交错

注:交错路是无向图,图中的箭头只是为了便于观察。

例如下图中的:(3) -> (2) -> (1)

图1

从端点扩张交错路

假设我们已经有一个红黑交错路P,其端点为AB,其路径被标记为黑红。此时,我们向P中的一个端点(假设为A)加入一条边T

此时我们有边T + 交错路P(黑红)。当我们将边T标记为黑色时,我们就扩展了交错路P。 如果我们要保持红黑交错路的性质。则我们必须将边T …

more ...

Codeforces 3C - Tic-tac-toe

啥?

Tic-tac-toe是我很久之前在CF上做的一道题。非常考细心的模拟题。

最近有同学和我讨论过类似的问题。于是拿出来重新做一遍。练练手。

原题做法

没有任何“算法”成分。纯模拟。

又由于数据量实在是太小(3 × 3的矩阵),所以只要是思路正确。代码怎么写都能过。

于是在这里就不赘述。手快的众位10分钟切此题无压力。

What's new?

如果我们扩展一下这个问题。如果让你设计一个Tic-tac-toe的对战系统(人机对战、人人对战等),你将如何设计?

the STATE pattern

我们可以看出,这个对战系统其实可以用一个状态机来表示。

http://wizmann-tk-pic.u.qiniudn.com/blog-tick-tac-toe.png

于是我们的对战系统也可以写成一个状态机的模式。

show me the CODE

首先我们声明一个State接口类型。

由于Tic-tac-toe游戏只有两种操作类型:P1 moveP2 move

所以我们的接口就很简单。

class State {
public:
    State …
more ...

How to "Rotate Image"?

啥?

原题戳我

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:

Could you do this in-place?

示意图如下:

rotate-image

当然,矩阵中的数字不一定是规律的。

为什么要提出这个问题

自觉是一个不聪明的人(双低。。。<(=@_@;=)?>)。

别人一下子就想明白的事,在我这里要计算好几个来回。

所以努力想找到一个思维方法去弥补这个不足。

就以这题为例,如何使用简单、直接的方法,迅速正确的找出变化的映射规律。

初步思路 …

more ...

Codeforces Round #221 (Div. 2)不完全不正确题解

A. Lever

水题,杠杆原理。

^把字符串分割开。然后分别计算两边的重量即可。

#Result: Dec 24, 2013 6:04:41 PM    Wizmann  A - Lever   Python 2   Accepted     312 ms  4200 KB
def calc(ss):
    res = 0
    p = 1
    for item in ss:
        if item != '=':
            t = int(item)
            res += t * p
        p += 1
    return res

s = raw_input …
more ...

Codeforces Round #218 (Div. 2)不完全不正确题解

A. K-Periodic Array

将Array切片,然后按位统计某一位上1的个数C(1)和2的个数C(2)。然后在这一位上的操作数就为M = min(C(1), C(2))。

简单题

B. Fox Dividing Cheese

傻逼才错的题,不幸中枪。

不想多说了,直接看代码吧。手贱不是病,贱起来要人命。

C. Hamburgers

模拟 + 二分。

和CJL还讨论过这题的纯模拟做法,看了半天代码没找到问题。于是刚才用Python自己实现了一个,在代码正确的情况下,没有WA,但是T在了22组上。

所以这题最好使用二分,如果用模拟的话,需要考虑各种情况。代码见下,细节上注意就好。

D. Vessels

这题得好好讲一下~比赛时做出来了好得意~

Vessels

题意是给出一组层层叠的容器,每一个容器都有自己的容量。然后我们向某些容器里灌水,如果水的体积超过了某个容器的容量,则剩余的水溢出到下一个容器中。最后一个容器溢出的水会落到地面上 …

more ...

Codeforces Round #215 (Div. 2)不完全不正确题解

A. Sereja and Coat Rack

傻逼才错的题。不幸中枪。

没什么可说的。直接看代码就好。

B. Sereja and Suffixes

关键思想在于统计A[i...n-1]中有多少互不相同的数。

使用离线思想,把查询按greater<int>排序,然后使用Hash表进行统计,简单题。

C. Sereja and Algorithm

思路题。

我们容易想到如果可以交换相邻两个字母的位置,我们就可以获得这个字符串所有的排列。

所以我们只需要统计出A[i...j]中x, y, z的个数。

然后进行排列。

我们可以推出,稳定的排列(即可以使算法停下来的排列)只有如下几种情况。

zy[xzy][xzy]...
xz[yxz][yxz]...
yx[zyx …
more ...