博文
acm之pku题目分类(2009-10-22 23:59:00)
摘要：
对ACM有兴趣的同学们可以看看
DP:
1011 NTA 简单题
1013 Great Equipment 简单题
1024 Calendar Game 简单题
1027 Human Gene Functions 简单题
1037 Gridland 简单题
1052 Algernon s Noxious Emissions 简单题
1409 Communication System 简单题，但是很容易看错~~~
1425 Crossed Matchings 简单题
1438 Asteroids! 简单题
1459 String Distance and Transform Process 简单题
1462 Team Them Up! 简单题
1556 Heroes Of Might And Magic 简单题，不过背景蛮有意思的……
1520 Duty Free Shop 简单题
ACM 进阶之路（转）(2009-10-22 21:12:00)
摘要：
一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.ACM主要是考算法的,主要时间是花在思考算法上，不是花在写程序与debug上。
下面给个计划你练练：
第一阶段：练经典常用算法，下面的每个算法给我打上十到二十遍，同时自己精简代码，
因为太常用，所以要练到写时不用想，10-15分钟内打完，甚至关掉显示器都可以把程序打
出来。
1.最短路(Floyd、Dijstra,BellmanFord)
2.最小生成树(先写个prim,kruscal要用并查集，不好写)
3.大数（高精度）加减乘除
4.二分查找. (代码可在五行以内)
5.叉乘、判线段相交、然后写个凸包.
6.BFS、DFS,同时熟练hash表(要熟，要灵活,代码要简)
7.数学上的有：辗转相除（两行内），线段交点、多角形面积公式.
8. 调用系统的qsort, 技巧很多，慢慢掌握.
9. 任意进制间的转换
第二阶段：练习复杂一点，但也较常用的算法。
如：
1. 二分图匹配（匈牙利），最小路径覆盖
2. 网络流，最小费用流。
3. 线段树.
4. 并查集。
5. 熟悉动态规划的各个典型：LCS、最长递增子串、三角剖分、记忆化dp
6.博弈类算法。博弈树，二进制法等。
7.最大团，最大独立集。
8.判断点在多边形内。
9. 差分约束系统.
10. 双向广度搜索、A*算法，最小耗散优先.
===========================================================
ACMer必备知识（任重而道远......）
图论
路径问题
0/1边权最短路径
BFS
非负边权最短路径（Dijkstra）
&nbs......
北大poj 1166 The Clocks解题报告源代码(2009-10-22 19:37:00)
摘要：
北大poj 1166 The Clocks解题报告源代码
作者：贾晔
The Clocks
9只钟表排成3*3的方阵，每只钟表只能指向上、下、左、右四个位置
9种作用方式，每种使一些钟表的指针右转90°
使用这9种作用，使得所有钟表都指向正上方 (记为状态0)
求使得总作用次数最少的策略
Sample
Input Data
3*3矩阵，元素为0，1，2或3，分别表示钟表指向上，右，下，左
钟表矩阵的有限性
由于矩阵结构及其元素取值范围相当有限，故可能出现的钟表矩阵也是很有限的，即4^9=262144种
由此有限性可以考虑搜索解法
广度优先搜索
从状态0开始搜索
搜索过程：标记可以通过一次作用达到此状态的所有状态为已搜索，然后搜索新标记的状态。搜索过程中保存使用的作用方式
每个状态用一个32位整数的低18位表示,可将结果存在长度为262144的数组中
启发
广度优先搜索的可行意味着作用次数的相当有限
注意到作用的结果与作用的顺序无关，则显然每种作用最多只需使用3次
于是，问题简化为求解同余方程组
同余方程组
把钟表和作用分别从1到9标号，则同余方程组可写为
[C(i) +∑E(i,j) * M (j)] mod 4= 0 (i=1..9)
其中C(i),M(j),E(i,j)分别表示第i个钟表的初始状态，第j种作用的次数，第j种作用是否拨动第i个钟表
写成矩阵的形式
( C + E M ) mod 4 = 0 (*)
我们所求为M的最小非负解M0=M mod 4
显然，当k足够大时，方程
C + E M’ = 4 * k
广度优先搜索(2009-10-22 18:44:00)
摘要：
广度优先搜索(Breadth-First Search, BFS, 台湾称“横向优先搜寻”)是最简单的图搜索算法之一。广度优先搜索的特点是总是沿已发现与未发现的边界，向外依次扩展。设起始节点为s，则广度优先搜索算法首先会发现与s距离为k的所有结点后，才会发现与s距离为k+1的结点。
广度优先搜索在运行过程中将结点标识为三种状态：
白色：未被发现的结点；
灰色：已被发现，但与其相连的结点尚未全部发现的结点（下一轮进行发现的结点，也是发现结点集的边界）；
黑色：已被发现，且与之相连的其他结点也已经发现。
广度优先搜索因为存在单一的起始结点s，因此整个发现过程可以看作是以s为根节点的一棵树，称为广度优先树，广度优先搜索的过程也是建立一棵以s为根的广度优先树的过程。
广度优先树中对每个结点u记录三种信息：
π[u]：广度优先树中u的父结点，意味着u第一次被发现时所通过的上一级结点；
d[u]：u与根节点s的距离，如果是无权图，也是s到u的最短距离；
color[u]：u结点的颜色。
设图G = (V, E)，V是顶点集，E是边集。s是起始节点。
则广度优先搜索(Breadth-First Search, BFS)算法如下：
view sourceprint?
01.// 初始化整个图（除去起始结点s）
02.foreach(Vertex u in V[G] - {s})
03.{
04. u.Color = BFSColor.WHITE;
05. u.D = int.MaxValue;
06. u.π = null;
07.}
08.
09.// 设置起始结点s
10.s.Color = BFSColor.GRAY;
11.s.D = 0;
12.s.π = null;
13.
14.// 初始化一个队列
15.Queue<Vertex> q = new Queue<Vertex>();
16.q.Enqueue......
深入理解abstract class和interface(2009-10-20 11:10:00)
摘要：
abstract class和interface是Java语言中对于抽象类定义进行支持的两种机制，正是由于这两种机制的存在，才赋予了Java强大的面向对象能力。abstract class和interface之间在对于抽象类定义的支持方面具有很大的相似性，甚至可以相互替换，因此很多开发者在进行抽象类定义时对于abstract class和interface的选择显得比较随意。其实，两者之间还是有很大的区别的，对于它们的选择甚至反映出对于问题领域本质的理解、对于设计意图的理解是否正确、合理。本文将对它们之间的区别进行一番剖析，试图给开发者提供一个在二者之间进行选择的依据。
理解抽象类
abstract class和interface在Java语言中都是用来进行抽象类（本文中的抽象类并非从abstract class翻译而来，它表示的是一个抽象体，而abstract class为Java语言中用于定义抽象类的一种方法，请读者注意区分）定义的，那么什么是抽象类，使用抽象类能为我们带来什么好处呢？
在面向对象的概念中，我们知道所有的对象都是通过类来描绘的，但是反过来却不是这样。并不是所有的类都是用来描绘对象的，如果一个类中没有包含足够的信息来描绘一个具体的对象，这样的类就是抽象类。抽象类往往用来表征我们在对问题领域进行分析、设计中得出的抽象概念，是对一系列看上去不同，但是本质上相同的具体概念的抽象。比如：如果我们进行一个图形编辑软件的开发，就会发现问题领域存在着圆、三角形这样一些具体概念，它们是不同的，但是它们又都属于形状这样一个概念，形状这个概念在问题领域是不存在的，它就是一个抽象概念。正是因为抽象的概念在问题领域没有对应的具体概念，所以用以表征抽象概念的抽象类是不能够实例化的。
在面向对象领域，抽象类主要用来进行类型隐藏。我们可以构造出一个固定的一组行为的抽象描述，但是这组行为却能够有任意个可能的具体实现方式。这个抽象描述就是抽象类，而这一组任意个可能的具体实现则表现为所有可能的派生类。模块可以操作一个抽象体。由于模块依赖于一个固定的抽象体，因此它可以是不允许修改的；同时，通过从这个抽......
sprintf用法解析(2009-10-19 22:23:00)
摘要：
版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://fogblog.blogbus.com/logs/1437347.html
sprintf用法解析
作者 ：晨星
1：
sprintf 最常见的应用之一莫过于把整数打印到字符串中，所以，spritnf
在大多数场合可以替代itoa。
这样，一个整数的16 进制字符串就很容易得到，但我们在打印16 进制内容
时，通常想要一种左边补0 的等宽格式，那该怎么做呢？很简单，在表示宽
度的数字前面加个0 就可以了。
sprintf(s, "%08X", 4567); //产生："000011D7"
上面以”%d”进行的10 进制打印同样也可以使用这种左边补0 的方式。
这里要注意一个符号扩展的问题：比如，假如我们想打印短整数（short）-1
的内存16 进制表示形式，在Win32 平台上，一个short 型占2 个字节，所
以我们自然希望用4 个16 进制数字来打印它：
short si = -1;
sprintf(s, "%04X", si);
产生“FFFFFFFF”，怎么回事？因为spritnf 是个变参函数，除了前面两个
参数之外，后面的参数都不是类型安全的，函数更没有办法仅仅通过一个
“%X”就能得知当初函数调用前参数压栈时被压进来的到底是个4 字节的整
数还是个2 字节的短整数，所以采取了统一4 字节的处理方式，导致参数压
栈时做了符号扩展，扩展成了32 位的整数-1，打印时4 个位置不够了，就
把32 位整数-1 的8 位16 进制都打印出来了。如果你想看si 的本来面目，
那么就应该让编译器做0 扩展而不是符号扩展（扩展时二进制左边补0 而不
是补符号位）：
sprintf(s, "%04X", (unsigned short)si);
就可以了。或者：
unsigned short si = -1;
sprintf(s, "%04X", si);
2：
浮点数的打印和格式控制是spri......
Visual C++中的图形特技(2009-10-19 22:09:00)
摘要：
Visual C++中的图形特技
Visual C++中的图形特技 随着计算机信息表示及实现的多媒体化，在许多学习软件、游戏软件，以及多媒体课件制作软件中，经常使用各种图形显示技巧，如图形的推拉、交错、雨滴状、百页窗、积木随机堆叠等显示模式。这样使画面变得更为生动活泼，更能吸引用户，也为更好地发挥软件的功能奠定了基础。本文就Visual C++ 6.0中实现图形的各种显示技巧的原理及具体方法做些探讨。
基本原理
在Visual C++6.0中，显示位图的方法及过程如下:
1. 显示程序资源中的位图(位图的所有数据均存在于可执行文件中)
(1)从资源中装入位图
● 定义位图对象数据成员CBitmap m_Bitmap;
● 调用CBitmap成员函数LoadBitmap()，如m_Bitmap.LoadBitmap(IDB_BITMAP1);
● 传入LoadBitmap的参数是位图在图形编辑器中生成或从位图文件中引入时赋予的识别符。
(2)生成与位图相联系的内存设备情境对象
CDC MemDC;
MemDC.CreateCompatibleDC(NULL);
MemDC.SelectObject(&m_Bitmap);
(3)显示位图
CClientDC ClientDC(this);
BITMAP BM;
m_Bitmap.GetObject(sizeof(BM)，&BM);
ClientDC.BitBlt
( X，Y, //目标设备逻辑横、纵坐标
BM.bmWidth, BM.bmHeight, //显示位图的像素宽、高度
&MemDC,
//待显示位图数据的设备情境对象
0，0, //源数据中的横、纵坐标
SRCCOPY); //位操作方式
这种方法显示位图速度快，但不是很灵活，而且会使可执行文件增大。
2. 显示独立文件方式的位图(位图的所有数据独立于可执行文件)
HBITMAP *hBitmap;......
简单绘图(2009-10-19 21:55:00)
摘要：
----------
题目1:怎样新建?
创建-->
新建一工程-->MFC AppWizard[exe](注:取名必须遵照Mymfc.即必须为英文且第一个字母必须为大写)
选择Single document后按Finish<--完成
题目2:按下鼠标左键怎样弹出对话框?
在CMyFirstMfcProjectView类(注:仅仅此类才可以显示出弹出的对话框)
-->右击选择Add Windows Message handler(可以选择其它不同的消息.如WM_CHAR,WM_PAINT等)
MessageBox("您按下了左键VIEW!","窗口标题栏",MB_OK);(注:当达到消息成功后,就会弹出此窗口)
题目3:怎样画一条线?
/*****************************************************/
在CMyFirstMfcProjectView类中添加一个成员变量.变量类型:CPoint(注:点类型).变量名:任意取
定义之后初始化--->打开构造函数CMyFirstMfcProjectView(),添加初始化代码
把所用消息的值赋给它--->打开所要响应的消息机制.把里面的point值赋给它.
起点已找到.终点要新建--->新建一个WM_LButtonUp(注:当鼠标左弹起来时.响应终点)
开始作图(画线)--->
(一)API的方法(用全局变量)
(1)首先获取HDC(注:所有作图都必须定义1个HDC):用::GetDc(m_hwnd(注:是CWnd的句柄,公开且默认)); 注:必须为全局变量
(2)其次获取称动时线的坐标可用MoveTo与MoveToEx,究竟用哪个?用MoveToEx
关于2者区别:MoveTo是Win16 API,MoveToEx是Win32 API.后者是前者的升级.
如何在MFC窗口界面中插入图片？(2009-10-18 15:29:00)
摘要：
首先在资源里边插入位图（给它一个易记得命名），然后到你要插入图片的地方放入一个图片控件，点击它属性，选择刚刚你插入的位图（名字）即可。
哈哈
试试吧。......
MFC版本的XO小游戏(2009-10-12 22:20:00)
摘要：//MFC_xoDLG.h
// MFC_xoDlg.h : 头文件
//
#pragma once
// CMFC_xoDlg 对话框
class CMFC_xoDlg : public CDialog
{
// 构造
public:
CMFC_xoDlg(CWnd* pParent = NULL); // 标准构造函数
// 对话框数据
enum { IDD = IDD_MFC_XO_DIALOG };
protected:
virtual void DoDataExchange(CDataExchange* pDX); // DDX/DDV 支持
// 实现
protected:
HICON m_hIcon;
// 生成的消息映射函数
virtual BOOL OnInitDialog();
afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
afx_msg void OnPaint();
afx_msg HCURSOR OnQueryDragIcon();
DECLARE_MESSAGE_MAP()
public:
afx_msg void OnBnClickedButton1();
afx_msg void OnBnClickedButton2();
afx_msg void OnBnClickedButton3();
afx_msg void OnBnClickedButton4();
afx_msg void OnBnClickedButton5();
afx_msg void OnBnClickedButton6();
afx_msg void OnBnClickedButton7();
afx_msg void OnBnClickedButton8();
&nb......