XtestW's Blog

工程中，某些对象我们只需要一个，比如线程池，缓存，对话框等的对象，我们通常的做法是可以定一个全局静态变量，然后通过程序初始化的时候就实例化他们，然后直接调用这个全局变量，但是这样有个问题，如果我的这个对象消耗的资源很多，而有的时候，我的程序在运行过程中又没用到这个对象，岂不是浪费了很多资源。通常的做法就是定义全局静态变量的时候，不初始化他，而是在调用过程中实例化，这样的话，对于全局变量的实例化，我们就要判断这个变量是否已经实例化了，如果实例化了的吧，我们就不对它进行实例化，所以代码如下：

在面向对象的编程中，我们常常会用到new这个关键字，同时，面向对象可以实现多态，这样的话，我们常常就会用父类或者接口定义一个变量，在用到这个变量的时候，再new一个具体的对象，但是有的时候，这个new的对象不是确定的，可能是要根据不同的场景，new出不同的子类，这个很简单的就可以通过if 或者switch来判断实现，但是，这样子以来的话，如果在很多个地方都出现了这种情况，岂不是都要在这些个地方来写这些一样的代码？这样真的好么？

工厂模式就是用来解决这种对象的生成的办法。工厂模式主要分为3种：简单工厂，工厂方法，抽象工厂。

​ 这一章看完之后，我感觉，装饰者模式就是对类继承的一种递归调用式的组合应用，很好的是实现了开闭原则，可以有效的扩展应用程序。比如书中的例子，有几种饮料，每种饮料的价格已经知道了，但是我们又有很多种的调料，每种调料也有它的价格，我们现在需要是在饮料中加调料，那么这样一来，饮料的售价就会变化，如何来描述这种售价呢？如果通过对调料种类的组合来定义若干的类，肯定是非常愚蠢的行为。

​ 通过装饰者模式，就能很好的解决这个问题，我们将这些类分为装饰类（调料），待装饰类（饮料）两种，这两种类继承同一个父类，不同的是装饰类中的构造函数有一个父类引用的构造函数，这样子就可以递归调用构造函数来进行 装饰了。

1 2 3 4 5 6 7 8 9 10 11 12

public class A extends BaseClass{ public string who() { return "A"; } public int cost() { return 5; } }

我们定义一个待装饰类A，再定义几个装饰类：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

public class decorator1 extends BaseClass{ BaseClass baseClass; public decorator1(BaseClass t） { this.baseClass = t; } public string who() { return baseClass.who()+",decoratro1"; } public int cost() { return baseClass.cost()+10; } } public class decorator2 extends BaseClass{ BaseClass baseClass; public decorator2(BaseClass t） { this.baseClass = t; } public string who() { return baseClass.who()+",decoratro2"; } public int cost() { return baseClass.cost()+20; } }

然后我们在用decorator1 和decorator2 来装饰A的时候，就有了很犀利的调用方法：

1 2 3 4 5

A a; a=new decorator1(a); a=new deocorator2(a); system.out.println(a.who()); system.out.println(a.cost());

这样子 输出就是

1 2	A,decorator1,decorator2 35

实际的调用过程就是一个递归的过程。

装饰者模式的定义：

1	装饰者模式：动态地将责任附加到对象上，若要扩展功能，装饰者提供了比继承更具有弹性的替代方案

其中用到的设计原则：

1	开闭原则：对扩展开放，对修改关闭

在项目设计阶段，处理一对多的依赖关系类的时候，我们需要降低代码的耦合性从而增强可扩展性，比如一个班级，班主任老师和学生的关系，对于学校的通知，必定不会是学生没事的时候就问一下班主任”学校有通知没啊？”（铁定会把班主任搞毛的），明智的做法则是等着班主任在班级里面通知（对于学校的通知，班主任不会不通知学生的）,在这个关系里，班主任就是所谓的被观察者，而学生则是观察者，也就是所谓的观察者模式：

观察者模式：定义了对象之间的一对多的依赖，这样一来，当一个对象改变状态的时候，他的所有依赖都会收到通知并自动更新

​ 在实际开发过程中，经常会发生这样的一件事，我们需要实现一系列的功能，这些功能在逻辑上是可以抽象成一样的方法，不同的实现，也就是多态，有一种解决方法是，设计一个基类，然后我们定义一些方法，然后继承这个类，设计不同的子类，不同的实现，这样子我们就可以定义基类来调用子类的方法，实现多态，这种方法一定程度上是实现了代码复用。

​ 但是会有一个问题，假设，基类BaseClass具有一个方法，他们的子类都具有两个方法A和B，其中方法A的实现，所有的子类都一样，很明显A的实现方法是放在基类中实现的，如果B的方法每个子类的实现都不是一样的，那么毫无疑问的是我们会在每个子类中重写B的实现。这些都是显而易见的，但是某一天需求变了，BaseClass的子类childClass1，childClass2的B方法的实现是完全一样的，childClass3，childClass4的B方法的实现也是一样的，如果我们再在每个子类中实现这个方法，很明显，代码复用很不完美。也许我们会这样子解决这个问题:

1.下载安装GridCtrl===>http://www.codeproject.com/Articles/8/MFC-Grid-control

​ 在对应项目里面添加GridCtrl的所有.h和cpp的文件(GridCtrl_src和NewCellTypes两个文件夹下的文件)

​ 在vs2010中可能会出现CMemDC重定义的错误，只要将CMemDC这个重命名为CGridMemDC（或者其他你想要的名字，同时将这个库中的其他引用CMemDC这个类的地方的名称一起改过来）

2.在对话框中添加GridCtrl的成员变量

​ 定义:

1

CGridCtrl* m_pGrid;

​ 构造函数中初始化:

1

m_pGrid=NULL;

​ 析构函数中销毁

1
2
3
4
5

if (m_pGrid)
{
    delete m_pGrid;
    m_pGrid=NULL;
}

3.在对话框中画出m_pGrid控件

1
2
3
4
5

CRect rect;
this->GetWindowRect(rect);
GetClientRect(rect);
m_pGrid=new CGridCtrl();
m_pGrid->Create(CRect(rect.TopLeft().x,rect.BottomRight().y-100,rect.Width(),rect.BottomRight().y),this,1000);

其中Create的第一个参数是这个控件在对话框中的位置（我这里是在对话框底部高为100的区域），第二个参数是父窗口句柄，第三个是你分配给他的ID。

这个创建过程，可以根据需求在不同的函数中实现。

这一过程结束之后我们就有了一个空白的GridCtrl控件显示在对话框中了。

母函数的具体介绍见博客：http://www.wutianqi.com/?p=596

其中第二类的说明中，对于为什么第一个表达式是(1+x^1+x^2+x^3….+x^n)，第二个表达式是(1+x^2+x^4+x^6)，没有解释清楚，我自己想了一下，做了hdu1389(http://acm.hdu.edu.cn/showproblem.php?pid=1398)这道题，才彻底明白，第一个表达式，指的是，只用价值为1的硬币组成的价值，第二个表达式是只用价值为2的硬币能获得的价值，那么第一个和第二个表达式相乘，就可以获得只有价值为1和2两种硬币组成的价值的情况，且系数表示种类。这样子也就不难理解1389对模板的改变了。

hdu 1389，可兼做模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

/*
 * Author:  xtestw
 * Created Time:  2014/7/8 7:32:31
 * File Name: 1289.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
using namespace std;
const int maxint = -1u>>1;
int c1[400],c2[400];
int main() {
#ifndef ONLINE_JUDGE
   freopen("f:/in.txt","r",stdin);
#endif
   int n;
   while (scanf("%d",&n) && n)
    {
        for(int i=0;i<=n;i++)
        {
            c1[i]=1;
            c2[i]=0;
        }
        for(int i=2;i*i<=n;i++)//i*i表示的就是第i个表达式是由价值为i*i的硬币的情况
        {
            for(int j=0;j<=n;j++)
            {
                for(int k=0;k+j<=n;k+=i*i)
                {
                    c2[j+k]+=c1[j];
                }
            }

for(int j=0;j<=n;j++)
            {
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        cout<<c1[n]<<endl;
    }
   return 0;
}

hdu 1171利用母函数求解的代码：

参见博客：http://blog.csdn.net/dark_scope/article/details/8880547，非常给力的说法 关于二分图匹配，常用的结论如下：

1. 二分图的最小顶点覆盖 最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。 knoig定理:二分图的最小顶点覆盖数 = 二分图的最大匹配数（m）。

2. DAG图的最小路径覆盖 用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。 结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）

3. 二分图的最大独立集 结论：二分图的最大独立集数 = 节点数（n）— 最大匹配数（m）

匈牙利算法模板:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/*
 * Author:  xtestw
 * Created Time:  2014/7/6 21:55:04
 * File Name: hungry.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
using namespace std;
const int maxint = -1u>>1;
int g[1000][1001];
int vis[1010];
int pre[1010];
int m,n1,n2;
void init(){
    memset(g,0,sizeof(g));
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    scanf("%d",&m);
    if (m==0) return;
    scanf("%d%d",&n1,&n2);
    for(int i = 0; i < m ; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        g[a][b]=1;
    }

}
int find(int x){
    for(int i=1;i<=n2;i++)
    {
        if (g[x][i] && !vis[i]){
            vis[i]=1;
            if (pre[i]<0 || find(pre[i]))
            {
                pre[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int hungry(){
    int ret=0;
    for(int i=1;i<=n1;i++)
    {
        memset(vis,0,sizeof(vis));
        if (find(i)){
            ret++;
        }
    }
    return ret;
}
int main() {
#ifndef ONLINE_JUDGE
  // freopen("f:/in.txt","r",stdin);
#endif
    while (true){
         init();
         if (m==0) break;
        cout<<hungry()<<endl;
    }
    return 0;
}

AC 自动机主要有3个步骤：

1. 构造trie树
2. 在trie树的基础上，添加失败指针，其添加方法就是一句话：由父亲节点开始，沿着失败指针向上找，一直找到一个节点p的next[i]不为空或者到根节点，把当前节点的next[i]的失败指针指向p的next[i]
3. 进行模式串的匹配

hdu 2222 代码，可兼作模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

/* * Author: xtestw 
	* Created Time: 2014/7/7 8:54:30 
	* File Name: 2222.cpp **/ 
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <iostream>
using namespace std;
const int maxint = -1u >> 1;
string image;
string strs[10010];
struct Node
{
    Node *next[26];
    Node *fail;
    int count;
    Node()
    {
        fail = NULL;
        memset(next, NULL, sizeof(next));
        count = 0;
    }
} q[500010];
Node *root;
void insert(string str, Node *root)
{
    Node *p = root;
    int i = 0, index;
    while (str[i])
    {
        index = str[i] - 'a';
        if (p->next[index] == NULL)
            p->next[index] = new Node();
        p = p->next[index];
        i++;
    }
    p->count++;
}
void buildfail(Node *root)
{
    int i;
    root->fail = NULL;
    int head, tail;
    head = tail = 0;
    q[head++] = root;
    while (head != tail)
    {
        Node *tmp = q[tail++];
        Node *p = NULL;
        for (int i = 0; i < 26; i++)
        {
            if (tmp->next[i] != NULL)
            {
                if (tmp == root)
                    tmp->next[i]->fail = root;
                else
                {
                    p = tmp->fail;
                    while (p != NULL)
                    {
                        if (p->next[i] != NULL)
                        {
                            tmp->next[i]->fail = p->next[i];
                            break;
                        }
                        p = p->fail;
                    }
                    if (p == NULL)
                        tmp->next[i]->fail = root;
                }
                q[head++] = tmp->next[i];
            }
        }
    }
}
int query(Node *root)
{
    int i = 0, cnt = 0, index, len = image.size();
    Node *p = root;
    while (image[i])
    {
        index = image[i] - 'a';
        while (p->next[index] == NULL && p != root)
            p = p->fail;
        p = p->next[index];
        p = (p == NULL) ? root : p;
        Node *tmp = p;
        while (tmp != root && tmp->count != -1)
        {
            cnt += tmp->count;
            tmp->count = -1;
            tmp = tmp->fail;
        }
        i++;
    }
    return cnt;
}
int main()
{
#ifndef ONLINE_JUDGE freopen("f:/in.txt", "r", stdin);
#endif ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--)
    {
        root = new Node();
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> strs[i];
        cin >> image;
        for (int i = 0; i < n; i++)
        {
            insert(strs[i], root);
        }
        buildfail(root);
        cout << query(root) << endl;
    }
    return 0;
}

详细的参看：http://www.cppblog.com/mythit/archive/2009/04/21/80633.html

使用Invalidate（true），即使在OnDraw中使用了双缓冲，也会出现闪屏问题，下面的解决方案转载自：http://blog.sina.com.cn/s/blog_60fa20600100igh6.html

在使用**Invalidate(TRUE)**进行窗口重绘时，总是会遇到闪屏的问题。

​ 一开始以为是绘图速度过慢照成的，但在对绘图时间做了一个测试之后发现，即使整个绘图过程只持续了几个毫秒，还是会看见很明显的闪烁****，所以时间并不是造成闪烁的决定性因素。

​ 那到底是什么原因呢？现在来看看Invalidate(TRUE)都干了些什么。其实，它只是间接向消息队列添加了WM_ERASEBKGND和WM_PAINT两个消息。但是，如果使用Invalidate(FALSE)的话，则只有WM_PAINT消息产生，这时是不会有任何闪烁的。

​ 现在看来，闪烁似乎是由WM_ERASEBKGND消息产生的，事实上，的确与它有关。那WM_ERASEBKGND有干了什么呢？WM_ERASEBKGND消息由OnEraseBkgnd()消息处理函数响应，它的作用就是重绘客户区背景。我们可以通过向工程里添加WM_ERASEBKGND这个消息，然后在重写的消息处理函数中将返回语句修改为return TRUE来屏蔽这一功能，这样做的好处是这时不会重绘背景了，坏处是这时背景也不会被擦出来。