XtestW's Blog

设计模式-观察者模式

发表于 2014-08-30 更新于 2025-01-01 分类于 Design Pattern 阅读次数：

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

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

阅读全文 »

设计模式-策略模式

发表于 2014-08-29 更新于 2025-01-01 分类于 Design Pattern 阅读次数：

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

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

阅读全文 »

MFC 对话框动态创建简单的GridCtrl控件

发表于 2014-08-27 更新于 2025-01-01 分类于 C++ 阅读次数：

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;

析构函数中销毁

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

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

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控件显示在对话框中了。

阅读全文 »

母函数

发表于 2014-07-08 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

母函数的具体介绍见博客：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，可兼做模板：

/*
 * 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利用母函数求解的代码：

阅读全文 »

匈牙利算法

发表于 2014-07-07 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

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

二分图的最小顶点覆盖最小顶点覆盖要求用最少的点（X或Y中都行），让每条边都至少和其中一个点关联。 knoig定理:二分图的最小顶点覆盖数 = 二分图的最大匹配数（m）。
DAG图的最小路径覆盖用尽量少的不相交简单路径覆盖有向无环图(DAG)G的所有顶点，这就是DAG图的最小路径覆盖问题。结论：DAG图的最小路径覆盖数 = 节点数（n）- 最大匹配数（m）

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

匈牙利算法模板:

/*
 * 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 自动机

发表于 2014-07-07 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

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

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

hdu 2222 代码，可兼作模板：

/* * 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

MFC Invalidate闪屏问题

发表于 2014-06-22 更新于 2025-01-01 分类于 C++ 阅读次数：

使用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来屏蔽这一功能，这样做的好处是这时不会重绘背景了，坏处是这时背景也不会被擦出来。

阅读全文 »

Millar_rabin和Pollard_Rho

发表于 2014-06-09 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

1.Millar_rabin 素数判定

基于以下两个基础：

　　1.如果p是素数，且(a,p)=1,那么(a^(p-1))%p=1(费马小定理)

2.对于0<x<p，(x^2)%p=1 => x=1 或者 x=p-1

处理：

把p-1写成u*(2^t)，则a^(p-1)=(a^u)^2^2^2…..t次平方操作

过程：

随机产生一个数a，cur=a^u %p,对cur做t次平方操作，即cur=cur*cur %p，每次操作结束后，如果cur=1那么上一次的cur必须为1或者p-1否则为合数（上面的基础2），最终的cur必须为1（基础1）。

　注意：

long long 在计算乘法的时候要防止溢出，用2进制模拟乘法。

2.Pollard_rho，因数分解

用某种方法生成a,b.计算p=gcd(a-b,n)，则p是n的一个因数，如果p=n或者p=1，则迭代的生成a,b，知道p不是n或者1，或者a,b出现循环。（通常b=(a*a+c)%p，在执行之前用Millar_rabin进行素数判定保证n不为素数).

过程：

func get_facts(n)

      if (n是素数){fac[tot++]=n; return;}

　　　　  		p=n

     while (p>=n) p=Pollard_rho(n,rand()%(p-1)+1)

      get_facts(p)

      get_facts(n/p)

   end func

图论入门算法理解

发表于 2014-06-09 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

1.Dijsktra 算法

Dijsktra算法是基于贪心的，从源点开始扩展，将当前已经是最短路的点加入集合中。dist[i]表示源点s到i的距离，那么初始的时候，找距离源点最近的一个点t0,那么dist[t0]必定是s到t0最短的距离，因为不可能通过其他的点转到t0再让t0最短了（这也是为什么Dijsktra不能处理负权边的原因），同理，扩展第二点的时候也是一样，因为在扩展第二个点的时候，已经用第一个点优化了所有其他的点，那么最近的那个点，一定无法通过剩余的其他的那个点来优化自己的距离了，也就是说这个点dist[t1]必定是s到t1的最短路径。

2.floyd：

　　每个点而言，剩余的点的两两最短路，要么经过这个点，要么不经过这个点，只要看经过它是否能更短。从另一个角度来理解的话,c[i][j][k]表示i,j经过的中间节点最大的点的标号不超过k的最短路，那么dp的转移方程就是c[i][j][k]=min(c[i][k][k-1]+c[k][j][k-1],c[i][j][k]).

阅读全文 »

几种简单的传统加密算法概述

发表于 2013-11-10 更新于 2021-01-17 分类于 Theory 阅读次数：

本文只是概述几种简单的传统加密算法，没有DES,没有RSA，没有想象中的高端大气上档次的东东。。。但是都是很传统很经典的一些算法首先，提到加密，比如加密一段文字，让其不可读，一般人首先会想到的是将其中的各个字符用其他一些特定的字符代替，比如，讲所有的A用C来表示，所有的C用E表示等等…其中早的代替算法就是由Julius Caesar发明的Caesar，它是用字母表中每个字母的之后的第三个字母来代替其本身的（C=E(3，p)=（p+3) mod 26)，但是，这种加密方式，很容易可以用穷举算法来破解，毕竟只有25种可能的情况.. 为了改进上诉算法，增加其破解的难度，我们不用简单的有序的替代方式，我们让替代无序化，用其中字母表的一个置换（置换：有限元素的集合S的置换就是S的所有元素的有序排列，且每个元素就出现一次，如S={a,b}其置换就只有两种:ab,ba），这样的话，就有26！种方式，大大的增加了破解的难度，但是这个世界聪明人太多，虽然26！很多，但是语言本身有一定的特性，每个字母在语言中出现的相对频率可以统计出来的，这样子，只要密文有了一定数量，就可以从统计学的角度，得到准确的字母匹配了。上面的算法我们称之为单表代替，其实单表代替密码之所以较容易被攻破，因为它带有原始字母使用频率的一些统计学特征。有两种主要的方法可以减少代替密码里明文结构在密文中的残留度，一种是对明文中的多个字母一起加密，另一种是采用多表代替密码。先说多字母代替吧，最著名的就是playfair密码，它把明文中的双字母音节作为一个单元并将其转换成密文的双字母音节，它是一个基于由密钥词构成的55的字母矩阵中的，一个例子，如密钥为monarchy，将其从左往右从上往下填入后，将剩余的字母依次填入剩下的空格，其中I/J填入同一个空格: 对明文加密规则如下： 1 若p1 p2在同一行，对应密文c1 c2分别是紧靠p1 p2 右端的字母。其中第一列被看做是最后一列的右方。 2 若p1 p2在同一列，对应密文c1 c2分别是紧靠p1 p2 下方的字母。其中第一行被看做是最后一行的下方。 3 若p1 p2不在同一行，不在同一列，则c1 c2是由p1 p2确定的矩形的其他两角的字母，并且c1和p1， c2和p2同行。 4 若p1 p2相同，则插入一个事先约定的字母，比如Q 。 5 若明文字母数为奇数时，则在明文的末端添加某个事先约定的字母作为填充。虽然相对简单加密，安全性有所提高，但是还是保留了明文语言的大部分结构特征，依旧可以破解出来，另一个有意思的多表代替密码是Hill密码，由数学家Lester Hill提出来的，其实就是利用了线性代数中的可逆矩阵，一个矩阵乘以它的逆矩阵得到单位矩阵，那么假设我们对密文每m个字母进行加密，那么将这m个字母在字母表中的序号写成矩阵形式设为P（如abc，[1,2,3])，密钥就是一个m阶的矩阵K，则C=PK mod26，，解密的时候只要将密文乘上K的逆矩阵模26就可以了。该方法大大的增加了安全性。上面的算法主要是多字母代替，现在再说说另一种多表代替的加密算法吧，其中最著名最简单的是vigenere密码，它的主要思想是对明文每m个字母进行加密，将每个字母加密，和Caesar算法一样，每个字母用后面的第k个字母来代替，只不过是m个字母中，每一个字母的k值不同，简单的说就是C=C0C1C2C3…=E(K,P)=(p0+k0）mod26,(p1+k1)mod26,(p2+k2)mod26…..但是这样的算法也是比较容易破解的，可以对相同字母的组合（如都是KATB）间隔数（存在偶然性，可以进行取舍），取公约数，那么m就是这个约数的某个因子，之后通过观察，如果长度为m，其实就是m个单表，进行分离就是m个单表分离，然后就很容易的破解了。。另外一种加密手段，是选择一个与明文无关的，且与他长度一致的密钥，进行异或，解密的时候再一次异或就OK了，这也是基于两次异或同一个值，值不变的结论，大家可以尝试一下的~ 上面主要说的是替换技术，其实传统加密算法除了替换的技术，还有一种就是置换的技术了，简单的说就是将明文的序列打乱，比如栅栏技术，就是按照对角线的顺序写出明文，而按行的顺序读出作为密文。当然这种技术太简单了，更复杂一点的就是将消息一行行的写成矩阵块，然后按列读出，但是把列的次序打乱的，为了增加安全性，还可以多次置换来着。传统加密高端一点的就是转轮机和隐写术了，转轮机是一种多重加密的技术，其主要的意义就是为DES加密提供了方向…隐写术是个神奇的东西，比如我们经常在电视剧中看到的隐形药水啥的…这些东西，就问度娘吧…..