叉姐的魔法训练（第四课）

叉姐的魔法训练（第四课）

挖坑...

----------------------

一 十字计数

POJ 3467 Cross Counting

由于颜色的总数<=100，所以我们可以O(N^3)预处理刚开始每种颜色的答案。
当某个元素(i,j)发生改变时，只影响i行或j列为中心的cross，因此只需逐个考虑每个中心的cross的变化，每次只需更改2*N的元素的cross数目。

----------------------

二 完美匹配

POJ 3375 Network Connection

有N个电脑，M个端口，M>=N，每一个电脑和端口的座标已知，现在要求把N个电脑分别连到N个端口上，一个端口最多连一台电脑，一台电脑要连一个端口。电脑与端口连接的代价是他们的座标值之差，问最小代价是多少。

这个问题初看是一个完美匹配问题，但是由于点数比较多，无法用最小费用最大流解决

----------------------

三 论文RMQ

.html

题目大意：论文题，查询一段区间内数字不重复的最长子串。
解题报告：RMQ论文题。利用一段区间的起始位置的单调性。二分一个最左边的点她的最长子串完全属于当前查询区间。然后RMQ右边这一段，左边的一段直接取最长的。

----------------------

----------------------

----------------------