Feb
21
SGU190 解题手记
先把棋盘像国际象棋那样染成黑白相间，然后把需要挖掉的格子挖掉。将每个格子看作顶点，相邻的格子连一条边，这样就构成一个二分图了。在二分图上做匹配，复杂度O(N^4)，有点悬。
Submit 1: AC。事实证明，我的程序还是比较快的，排第13名(2008-2-21)。
Jan
30
SGU177 解题手记
这题跟USACO的Shaping Regions有相似之处，我曾写过一篇解题报告：http://www.studentblog.net/m/bslgh/archives/2006/usaco211.html。
采用倒序染色+封闭然过色的格子的办法。对每一行开一个链表，染色时将白色部分记入总和，染色过后将这个格子删去。由于每个格子只被染色一次，所以总复杂度能控制在O(n^2)级别。
……
阅读全文——共691字
Aug
01
SGU121 解题手记
周源的SGU表格已经叙述的非常详细了：（内容有字句上的修改）
给定一个无向图，要求给这个图上的边0、1染色，且保证每个度不小于2的点都至少能连出一条0边，也至少能连出一条1边。
可以知道，这个图上可能会出现很多连通块，而两个连通块之间是不会互相影响的，所以可以分别处理之。
……
阅读全文——共1415字
Jan
09
昨天跟TV老师说了一下这个问题，发现我们对染色问题的理解有一定距离。TV老师所说的“染色问题”要维护的是某一线段上颜色(由最大颜色数限制)的数目，而不是我所理解的某一线段上指定颜色的长度。不管怎么样，这也算是个线段树练习，抽空会写的。
Jan
07
这就是前面所谓“第一次用C++写程序”中写的程序——线段树维护线段染色。
/*
线段染色问题 线段树维护
……
阅读全文——共408字
Jan
06
昨天下午和今天上午连续缺考了2门课，第一次尝试用C++来写程序，写的线段树练习（线段染色）。从中发现了一项C++与Pascal不同的地方——数组定义。
在Pascal中，[]中的内容就是下标的范围。而在C++中，[]中的内容是数组的元素个数，数组的下标范围是0到（元素个数-1）。昨天没有注意这个问题，把[]中的内容当作了下标上限，结果用了2个小时去Debug，发现是下标越界导致赋值给了一个在数组后面定义的变量。
……
阅读全文——共255字
