BalonFan-CSDN博客

原创挑战编程程序设计竞赛训练手册（Programming Challenges）

前一阵子到手这本书，一翻开就合不上了，发现书的内容编排非常紧凑，讲解清晰。每一章内容不多，可以一口气读完，每章后面的习题又是从UVa Online Judge上精心挑选的8个题目，自己可以写程序提交验证。可以说是非常适合自学的一本书，强烈推荐！这本是一本小册子，但看这本书一定要“把书看厚”。每一章的知识点其实都是很大一堆内容。从这一本小书出发，可以引出算法、数据结构、图论、数论

2010-01-04 17:12:00 4556 2

原创 UVa online judge 题目解答汇总

一直在做 UVa Online Judge 的题目，硬盘上有上百个题solution了，但从来没有把自己当时的思路记录下来。有些题还是很难的，过后再看，已经看不懂当时的程序了。所以决定重新整理，把每一道题的解法和思路一一记录，给自己留个记录，也给各位苦攻 UVa Online Judge 题目的同学一个帮助。注意！这些都是题透！请认真考虑过，真的需要再打开看，由此造成解题乐趣的丧失概不在

2010-01-02 23:22:00 5785

原创 Be careful of static field when unit testing!

<br />Basically, the value of static field will remain across test cases. So either you don't use static field, or remember to reset its value to default value in setUp(). Be careful, or you will get the most tricky bug promisingly.

2010-07-01 15:46:00 1121

原创 EasyMock: missing behavior definition for the preceeding method call

<br />If a method of a class which will be mocked by EasyMock did return some value, you should specify the return value explicitly before you use the mock object in your unit test case. Or else EasyMock will complain:<br /> <br />java.lang.IllegalStateExc

2010-07-01 14:13:00 3092

原创 EasyMock "m machers expected, n recorded" problem

在使用EasyMock时，如果在你的expectation中提供的参数中，有一个是使用了IArgumentMacher提供的，则所有的参数都要使用IArgumentMacher。否则，EasyMock会在这里报错： java.lang.IllegalStateException: M matchers expected, N recorded.比如在下面的场景中：我有一个interface StatusObserver:public interface RunStatusObserver { publ

2010-07-01 13:21:00 1301

原创 106 - Fermat vs. Pythagoras

此题实际上是求本原勾股数组（Primitive Pythagorean Triple, PPT）。稍用一点数论的经典知识就可以得到非常高效的解法。我的程序排名18，头一次进第一页：）返回 Volume I 索引返回总索引 //////////////////////////////////////////////////////////////////////////

2010-01-19 21:41:00 1558

原创 105 - The Skyline Problem

此题比较简单，直接扫描线法处理就可以了。先把每个楼的三元组 (left, height, right) 转化为两个事件：left 转化为进入事件，right 转化为离开事件。然后对所有的事件进行排序后从左向右进行扫描处理：一个楼进入扫描线：加入到“活动楼列表”，如果其 height > currentSkylineHeight，则修改 currentSkylineHeight 为 heig

2010-01-05 14:53:00 3729

原创 10033 - Interpreter

简单模拟题，主要就是“地址”，“地址的地址”，“地址里的数据”这几个概念别搞乱脑子就好。C/C++老手应该闭着眼睛也能写出正确的程序来：）返回 Volume C 索引返回总索引 //////////////////////////////////////////////////////////////////////////// 10033 - Interpreter

2010-01-05 00:21:00 1615

原创 10267 - Graphical Editor

此题其实是一个简单的模拟题，但经过多次WA后，我终于写对了其中的floodfill算法，要写一个正确的floodFill算法要非常小心。 Floodfill 一般过程就是：将起始点染色，并压入队尾从队列中取出一点 p:(x,y)检测 p 周围4点（或是8点，取决于题目要求是八向还是四向），并将那些可以到达的点染色，并压入队尾循环2~3直到队空我在实现时，出现了几

2010-01-04 23:49:00 2061

原创 UVa Online Judge - Volume CII 题目和解答索引

UVa Online Judge - Volume CII 题目和解答索引。前面为原题链接，后面为我的解答链接。返回总目录 10267 - Graphical EditorSimulation, FloodfillSolution

2010-01-04 23:48:00 2120

原创 104 - Arbitrage

这道题费了我相当的时间。题目要求找到一个profit > 1.01的套汇序列，但有多个的情况时，要求输出序列最短的一条。开始觉得很像Floyd-Warshall 算法，但试着开写了才发现，对于怎么控制得到最短序列非常有玄机。最后还是在UVa的论坛里找到了一个好帖，给出了一个 O(n4) 的算法，并给了非常详细的解释。原帖在这里，请看 gits 的回帖。用 profit(i,

2010-01-04 23:20:00 1763

原创 706 - LCD-Display

简单模拟题，设计一个好的数据结构来方便的表达每个数字的输出方式。我的不是最好的，后来还看到 Kaipeng Liu 的方法，写起来更利索一些;) 返回 Volume VII 索引返回总索引下面是我的代码 //////////////////////////////////////////////////////////////////////////// 70

2010-01-04 16:44:00 1544

原创 UVa Online Judge - Volume VII 题目和解答索引

UVa Online Judge - Volume VII 题目和解答索引。前面为原题链接，后面为我的解答链接。返回总目录 706 - LCD-DisplayStringSolution

2010-01-04 16:38:00 1673

原创 10137 - The Trip

此题涉及浮点数运算，所以要格外小心。题目大意是要求出最小的匀钱方案，精确到分。因此，求出平均数后，用多的减平均数得到的值，和用平均数减少的得到的值可能会有不同。取其中较小的就可以了。特殊情况在于算出的较小的值可能是0，那么就得用较大的值了。更新：之前对于用C++输出定长浮点数格式控制记不太清了，研究了一下做了修改，现在的科学一些了：cout 返回 Vo

2010-01-04 16:18:00 1936 1

原创 10189 - Minesweeper

2010-01-04 15:52:00 1586

原创 UVa Online Judge - Volume C 题目和解答索引

UVa Online Judge - Volume C 题目和解答索引。前面为原题链接，后面为我的解答链接。返回总目录 10003 - Cutting SticksDynamic ProgrammingSolution10004 - BicoloringGraph: BFSSolution10006 - Car

2010-01-03 20:38:00 1890

原创 UVa Online Judge - Volume CI 题目和解答索引

UVa Online Judge - Volume CI 题目和解答索引。前面为原题链接，后面为我的解答链接。返回总目录 10104 - Euclid ProblemNumber TheorySolution10110 - Light, more lightNumber TheorySolution10137

2010-01-03 20:28:00 1923

原创 103 - Stacking Boxes

这个题可以转化为一个有向无环图，在其上寻找一条最长路径。每一个box作为DAG上的一个顶点。如果box1可以嵌套到box2中，则在DAG中有一条有向边从box1指向box2 返回 Volume I 索引返回总索引 //////////////////////////////////////////////////////////////////////////// 10

2010-01-03 20:10:00 1231

原创 102 - Ecological Bin Packing

此题本身不难，因为对于输入，只有6种可能的组合。直接用暴力法枚举所有可能就可以了。主要的问题在于保证输出所有最优解中字典序最少的一个。返回 Volume I 索引返回总索引 // 102_Ecological_Bin_Packing.cpp : Defines the entry point for the console application.//#i

2010-01-03 00:15:00 1547

原创 101 - The Blocks Problem

模拟题，根据题目描述的内容直接写程序就可以。需要注意的是非法输入的情况：对于a==b或是a和b在同一堆的输入命令直接忽略。返回 Volume I 索引返回总索引 // 101_The_Blocks_Problem.cpp : Defines the entry point for the console application.//#include #

2010-01-03 00:10:00 1596

原创 UVa Online Judge - Volume I 题目和解答索引

UVa Online Judge - Volume I 题目和解答索引。前面为原题链接，后面为我的解答链接。返回总目录 100 - The 3n + 1 problemAd hocSolution101 - The Blocks ProblemSimulationSolution102 - Ecological

2010-01-02 23:47:00 4546

原创 100 - The 3n + 1 problem

简单题，直接按照题目要求进行模拟就可以。注意可以保存中间结果，可以让运行时间提高一个数量级。更快的方法应该是有的，只是对于本题给出的规模，这个算法已经可以很快的得到结果了。返回 Volume I 索引返回总索引 // 100_3n_plus_1.cpp : Defines the entry point for the console application.//

2010-01-02 22:54:00 3041 2

原创 GDI+中创建离屏缓冲位图的性能问题

在GDI+中，使用Bitmap创建一个离屏缓冲，必须要使用以下构造函数版本：Bitmap::Bitmap(INT width, INT height, Graphics* target)而不要使用以下构造函数版本：Bitmap::Bitmap(INT width, INT height, PixelFormat format)否则，在调用Graphics::DrawImage

2009-08-23 17:06:00 1593

原创《领域驱动设计》看完留念

花了两三周，每天10点半到家后，花上两小时看上一部分，这周3终于看完了。这本书比《对象设计》结构整齐一些，更容易跟上作者的思路。前面部分写了领域驱动设计的一些基础方面，包括如何交流，如何调整结构，哪些是领域构造块等等。后面用部分开始跳出细节，从一个很高的视角看待前面的所有内容在整个体系中的位置及作用，并把前面的内容放在一起来演示了大比例结构上的应用。看完后，突然觉得，其实一些方法论，在不同

2009-07-11 15:48:00 854

原创团队效率模式（二）

续前《团队效率模式（一）》团队效率模式邮件确认问题游戏运营中经常使用需要运维同事对线上环境进行调整，运维同事在完成后，会用邮件回复说“已经做完，请验收”。但往往就没有人去验收了。原因找来找去，发现是：功能的发起是产品同事，方案确定是策划同事，提供配置是开发同事，负责测试是测试同事。大家都会收到“请验收”的邮件，但每个人都以为其他人会验收吧，所以不差我一个，没事的。

2009-05-28 00:56:00 1594 1

原创团队效率模式（一）

团队效率很大程度上受团队管理者的影响：1. 团队管理者的能力决定了团队成员的能力提升水平的上限。2. 团队管理者的管理方法决定了团队整体运作的效率。在互联网、游戏公司，更是这样。这样的公司和传统的软件公司相比，产品周期更短、变化更多、更新更快、团队更小，但是在软件质量上相应的要求会低一些。因此在管理上更是要求在保证质量的前提下，尽可能的提高效率。

2009-05-24 23:55:00 2320

原创今天这个BUG再次证明了，凡事有果必有因

我们的程序用到Flash控件进行互操作以提供更友好的界面。为了屏蔽右键菜单，直接子类化了Flash窗口，用自己的窗口函数，在右键时不发送给Flash控件，自己处理。测试中发现，一些情况下（主要是点击后开IE），关闭窗口销毁控件会导致崩溃。 1. 发现在ShellExecute这个API中会有消息循环，导致WM_CLOSE会在ShellExecute返回之前被处理2. 改成异步S

2009-05-22 01:37:00 1552

原创鼠标光标的一个“看起来”很神奇的问题

Windows里最让人抓狂的问题，莫过于鼠标相关的BUG了（估计所有GUI程序都一样）。鼠标的BUG往往还不能直接打断点调试，只能结合日志信息，加上自己的经验一起来查，这就更是难上加难了。最近遇到一个问题，虽然很快解决了，但解决过程自觉还是很典型的。问题是这样的：我们的程序主窗口上有一些区域鼠标移上要变手形光标，移开恢复箭头光标。原来一直是正常的，但一个新版本开发了一周后合出来

2009-05-07 16:33:00 2034

原创条件断点引发的血案

今天在调试打条件断点时，想起一出调试往事。同样也是条件断点，难倒了我们这所有程序员。为了以后总能记得这事，把这事写到偶博客里。当时我们服务器的光哥在Linux下用gdb调试一段代码，发现执行到一个地方时有一个变量的值是一个与预期不符的值，于是顺手打了一个条件断点：当执行到这一行，这个变量的值为那个有问题的值时就断下来，以确定是什么情况下出问题。结果，问题就来了… 跑过几

2009-05-05 10:49:00 1366 2

原创 ATL字符串转码的陷阱

在代码中经常使用UTF8与Wide Char的转换，每次手工调用WideCharToMultiByte转换很是麻烦，于是参考ATL的W2A、A2W这样的宏，自己写了两个宏：UTF82W、W2UTF8。我写的UTF82W、W2UTF8与ATL的W2A、A2W一样，都是使用_alloca在栈上开辟临时空间存放转换结果的。后来，由于在使用中出现了一个函数中转换的次数过多导致栈溢出的问题。于是想改进这

2009-04-24 20:54:00 4012

原创运行期显示多态指针的类型名

使用C++的RTTI，可以在运行期显示多态指针的类型名 typeid(p).name()是多态指针的当前类型typeid(*p).name()是多态指针的most derived类型后面这个特性在Observer模式中查错时特别有用：有时候一个observer注册到subject后，在自己实例被销毁前忘记反注册，就会在后面subject通知时，引发对无效指针的操作，而这时

2009-04-24 20:43:00 1092

原创小心Windows消息的限制

Windows提供的消息机制实在是一个好东西：1. 消息队列是Per-Thread的，向一个消息队列投递消息，只有此消息队列对应的线程可以进行处理。2. 消息队列是线程安全的，并发的访问会进行序列化。3. 窗口有线程关联的，向窗口投递消息，将投递到创建这个窗口的线程对应的消息队列。4. Windows为那些将窗口用作线程间数据传递的应

2009-03-22 23:07:00 2214 2

原创 C++中实现静态初始化代码段

C++中，我们经常会用到静态变量，但对于这些静态变量的初始化，我们只能对其进行赋初值，不能像C#或是Java中那样，有一个静态初始化段来进行一些复杂的初始化工作。举例来说，我有一个类，其成员变量会在多个线程中并发访问，所以我需要一个锁来保护数据一致性。于是有了这样的代码： class MyClass { public: void

2008-09-30 20:40:00 6369

翻译依赖注入（Dependency Injection）

1 A code illustration using Java 1 Java代码示例2 Forms of Dependency Injection 2 依赖注入的几种形式3 Existing frameworks 3 现有框架4 See also 4 参见5 External links 5 外部链接Type 1 or int

2008-09-30 20:35:00 2839

原创在Windows下编译 Boost 1.35、Lua 5.1和LuaBind 0.7

编译boost工具bjam:1. 使用Visual Studio 2005 Command Prompt环境运行/tools/jam/src/build.bat2. 生成的目标文件在/tools/jam/src/bin.ntx86/bjam.exe编译boost 1.35:1. 将bjam.exe拷贝到目录2. 编译多线程dll、Debu

2008-07-30 12:24:00 2829

原创 DayDayUp - CUDA、GPGPU，GPU通用计算技术

利用GPU的大量并行计算单元进行并行计算，辅助CPU进行计算密集任务 CUDA英文首页http://www.nvidia.com/object/cuda_home.html CUDA中文首页http://cuda.csdn.net/ GPGPU相关http://en.wikipedia.org/wiki/GPGPU 新版Adobe C

2008-07-09 18:12:00 1254

原创 Balon白话MSDN：从普通DLL中导出C++类（2） – 细看导出C++类的底层机制

Balon白话MSDN：从普通DLL中导出C++类（2） – 细看导出C++类的底层机制上一篇文章中，我们介绍了怎么从一个DLL中导出C++类，及选择性导出C++类的成员的方法。那么，整个系统的底层机制是怎么样的？是通过什么途径，使得我们可以在另一个程序中使用一个DLL中导出的类的呢？我们知道，要使用一个C++类，必要的条件是在编译期能得到这个类的头文件，并在链接期可以找到对应的符号

2007-05-10 23:56:00 7697 2

原创 Balon白话MSDN：从普通DLL中导出C++类（1） – dllexport和dllimport的使用方法（中英对照、附注解）

Balon白话MSDN：从普通DLL中导出C++类（1） – dllexport和dllimport的使用方法（中英对照、附注解）这几天写几个小程序练手，在准备将一个类导出时，发现还真不知道如果不用MFC的扩展DLL，是怎么导出的。但我知道dllexport可以导出函数和变量，而且MFC扩展DLL就算是使用了MFC的功能，但能否导出类应该也不是必须用MFC才能够做到，一定是有相应的机制可

2007-05-09 20:46:00 8692

原创分久必合 - Vista、Visual Studio Orcas、SilverLight、Expression Studio、WPF、XAML 给我们带来的开发趋势

最近工作之余留出了点时间，关注了一下近来出现的新技术（有些可能已经不算新技术了，只是我很久没看，暂且以为是了）。微软看的比较多，其它的也看了一些。首先是Visual Studio.NET Codename “Orcas” Beta1发布。在我们还在考虑到底是不是应当一步到位的从VC6切换到VS2005时，微软已经在Visual Studio上跑的很远了。新的Orcas几乎在开发

2007-05-05 19:20:00 4511 1

翻译 LockWindowUpdate系列5：关于LockWindowUpdate的最终评论

现在大家了解了LockWindowUpdate的设计意图，我现在将要告诉大家你们为什么不应当使用这个函数，甚至不是因为其设计意图的缘因。这需要回到LockWindowUpdate被创造出来的历史环境。回到16位Windows（特别是Windows 3.1）的时代。在那时，内存还是很昂贵的，显示驱动功能也很有限。还没有DirectX，没有AlphaBlend函数。你所拥有的一切就是一

2007-05-05 14:07:00 4135

luabind 0.7 modified for lua 5.1

空空如也