XtestW's Blog
0%

发表于 更新于 分类于 阅读次数：

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

4.构建简单的表格

1
2
3
4
5
6
m_pGrid->SetEditable(true);//默认就是可以编辑的
// m_pGrid->SetTextBkColor(RGB(0xFF, 0xFF, 0xE0));//设置表格内容是黄色背景
m_pGrid->SetRowCount(8); //初始为8行，包含表头
m_pGrid->SetColumnCount(8); //初始化为8列
m_pGrid->SetFixedRowCount(1); //表头为一行
m_pGrid->SetFixedColumnCount(1); //表头为一列

这一步结束之后就是一个8*8的表格，但是表格和表头都还没有内容是空白的

5.操作单元格

可以直接设置对应的单元格的内容

1
m_pGrid->SetItemText(row,col,content);

也可以通过下面方式来设置

1
2
3
4
5
6
GV_ITEM Item;
Item.mask = GVIF_TEXT;
Item.row = row;
Item.col = col;
Item.strText = “content";
m_Grid.SetItem(&Item);

其中mask表明的是能够访问的单元格的内容，比如我这个地方设置成了GVIF_IMAGE，那么运行结果出来之后在对应的单元格中是看不到content的，而且程序中通过GetItemText()的方法也访问不了(其实就是这个单元格的类型，通过虽然赋值没有报错，但是即便重新设置了mask的值为GVIF_IMAGE,也获取不到之前的赋值)。

mask的类型有下面几种：

1
2
3
4
5
6
7
8
9
10
GVIF_TEXT      // Cell text will be accessed
GVIF_IMAGE     // Cell image number will be accessed
GVIF_PARAM     // Cell user data (lParam) will be accessed
GVIF_STATE     // Cell state will be accessed
GVIF_BKCLR     // Cell background colour will be accessed
GVIF_FGCLR     // Cell foreground colour will be accessed
GVIF_FORMAT    // Cell format field will be accessed
GVIF_FONT      // Cell logical font will be accessed
GVIF_MARGIN    // Cell margin information will be accessed 
GVIF_ALL       // All information will be accessed

到此一个简单的GridCtrl的创建就完成了。

6.添加消息响应函数

以添加完成编辑触发的事件处理函数为例，首先在.h文件中声明消息处理函数:

1
afx_msg void OnGridEndEdit(NMHDR *pNotifyStruct, LRESULT* pResult);

然后到对应的cpp文件中BEGIN_MESSAGE_MAP和END_MESSAGE_MAP之间添加消息响应映射:

1
ON_NOTIFY(GVN_ENDLABELEDIT, IDC_GRID, OnGridEndEdit)

其中第一个参数是消息，第二个是GRID创建时候的ID，第三个参数就是对应的消息处理函数

最后在cpp中编写对应的响应函数:

1
2
3
4
5
void C3TranformerAttr::OnGridEndEdit(NMHDR *pNotifyStruct, LRESULT* pResult){
     NM_GRIDVIEW* pItem = (NM_GRIDVIEW*) pNotifyStruct;
     pItem->iColumn;
     pItem->iRow;
}

在这个函数中可以获得相应的行号和列号，从而进行各种操作。

发表于 更新于 分类于 阅读次数：

母函数的具体介绍见博客：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利用母函数求解的代码：

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
/*
 * Author:  xtestw
 * Created Time:  2014/7/8 8:47:03
 * File Name: 1171.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[300000];
int c2[300000];
int v[1000];
int w[1000];
int main() {
#ifndef ONLINE_JUDGE
   freopen("f:/in.txt","r",stdin);
#endif
   int n;
   while (scanf("%d",&n) && n>0)
    {
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&v[i],&w[i]);
            sum+=v[i]*w[i];
        }
        memset(c2,0,sizeof(c2));
        memset(c1,0,sizeof(c1));
        for(int i=0;i<=w[1];i++)
        {
            c1[v[1]*i]=1;
            c2[i]=0;
        }
        int max=0;
        for(int i=2;i<=n;i++)
        {
            for(int j=0;j<=sum;j++)
            {
                for(int k=0;k+j<=sum && k<=w[i]*v[i];k+=v[i])
                {
                    c2[j+k]+=c1[j];
                }
            }
            for(int j=0;j<sum;j++)
            {
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        for(int i=sum/2;i>=0;i--)
        {
            if (c1[i])
            {
                cout<<sum-i<<" "<<i<<endl;
                break;
            }
        }
    }
    return 0;
}

发表于 更新于 分类于 阅读次数：

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

​ 好像还没有说到真实原因，其实真正的原因就隐含在其中。现在来做一个实验，分别尝试一下快速的眨眼和慢速的眨眼，你会发现快速眨眼时我们会感觉眼前的黑色一闪而过，而慢速眨眼时，则会觉得整个过程是连续的，没有什么异样。其实闪烁也就是这么回事，即多张不连续图像的快速切换。这里有三个条件，多张和快速和不连续，而且需要同时具备才会发生闪烁。如果只是两张，只会感觉到突变，还谈不上闪烁；如果频率慢的话，也相当于两张图像的情况了；最后如果是连续图像的话，那就像是看电影，平稳的过渡也不会让人觉得不适。

​ 知道了这些，接下来就可以做决策了。

​ 解决方案：

​ 使用Invalidate(FALSE),添加WM_ERASEBKGND消息处理函数或者局部刷新三者选其一，都是可以解决问题的。它们的都是通过除去图像不连续这一因素来达到目的的。

​ 另外，要说的是GDI的BitBlt()函数是及其高效的，一次操作所需要的时间只有几到十几个微秒，所以我们可以放心的使用它，而不用担心任何效率问题。不过相对于BitBlt()来说StretchBlt()就要慢的多，大概是几十倍的差别。

​ 还有就是一般的绘图工作都是先绘制在一个缓冲区上，然后再一次拷贝到屏幕上。

​ 有时，当我们需要利用闪烁的效果的话，也是可以通过多张图像的快速切换来做到，在这里我们也将两张图像的重复切换理解为多张图像。

我自己则是通过下面代码进行解决的：

1
2
3
4
5
6
BOOL CDQView::OnEraseBkgnd(CDC* pDC)
{
    // TODO: 在此添加消息处理程序代码和/或调用默认值
    return false;
    //return CView::OnEraseBkgnd(pDC);
}

发表于 更新于 分类于 阅读次数：

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不为素数).

​ 过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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

发表于 更新于 分类于 阅读次数：

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]).

3.Bellman-ford

​ 进行n次按边松弛的操作，之所以是n次，因为每次松弛过程中，都能保证至少一个点获得了最短路，且每个点最多被经过1次，从DP角度来理解的话，d[k][v]=min(d[k-1][v]+e[u][v],d[k-1][v]),其中e[u][v]代表的是边，d[k][v]表示的是k次以内到达v的最短距离。

4.SPFA

　　最差的情况是n*(n-1)*e,每个点被松弛n-1次,dp[i]=min(dp[v]+mp[v][i],dp[i])

发表于 更新于 分类于 阅读次数：

本文只是概述几种简单的传统加密算法，没有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加密提供了方向…隐写术是个神奇的东西，比如我们经常在电视剧中看到的隐形药水啥的…这些东西，就问度娘吧…..

发表于 更新于 分类于 阅读次数：

两篇讲的比较好的文章: https://www.byvoid.com/blog/scc-tarjan/ https://www.byvoid.com/blog/biconnect/ 对于有向图和无向图，处理的大体方法一样的，不过概念不同 /*****************************************************************************/ tarjan在处理无向图的时候，遇到两点之间的有多条边的时候处理方法，和如何缩点，缩边代码：

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

void tarjan(int s,int pre)
{
    low[s]=dfn[s]=cnt++;
    vis[s]=true;
    int f=0;
    stk.push(s);
    //stk[stkCnt++]=s;
    for (int i=head[s];i!=-1;i=e[i].next)
    {
        int u=e[i].to;
        if (u==pre){f++; continue;}
        if (!dfn[u]){
            tarjan(u,s);
            low[s]=min(low[s],low[u]);
        }
        else if(vis[u])
            low[s]=min(low[s],dfn[u]);
    }
    if (f>=2) return;//这里用f处理了点与点之间如果遇到多条边的情况
    if (low[s]==dfn[s]){
            while (true)
            {
                //int t=stk[--stkCnt];//stk.pop();
                int t=stk.top();stk.pop();
                flag[t]=xx;
                vis[t]=false;
                if (t==s)
                {
                    break;
                }
            }
            xx++;
    }
}
vector *nMp;//[200010];
void build(int n)
{
   for (int i=0;i<n;i++)
   {//遍历所有的边，判断边的两边是不是在一个集合中的，不是就是割边
       int s,t;
       s=flag[e[i*2].from];
       t=flag[e[i*2].to];
       if (s!=t)
       {
           nMp[s].push_back(t);
           nMp[t].push_back(s);
       }
   }
}

  2013多校的第二场B题（hdu 4612） ac代码：

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <map>
using namespace std;
int n,m;
vector mp[200010];
struct edge
{
    int from;
    int to;
    int next;
};
edge e[2000020];
int head[200020];
stack stk;
//int stk[200010];
int stkCnt=0;
int flag[200010];
int xx;
int low[200010];
int dfn[200010];
bool vis[200010];
int cnt=0;
void tarjan(int s,int pre)
{
    low[s]=dfn[s]=cnt++;
    vis[s]=true;
    int f=0;
    stk.push(s);
    //stk[stkCnt++]=s;
    for (int i=head[s];i!=-1;i=e[i].next)
    {
        int u=e[i].to;
        if (u==pre){f++; continue;}
        if (!dfn[u]){
            tarjan(u,s);
            low[s]=min(low[s],low[u]);
        }
        else if(vis[u])
            low[s]=min(low[s],dfn[u]);
    }
    if (f>=2) return;
    if (low[s]==dfn[s]){
            while (true)
            {
                //int t=stk[--stkCnt];//stk.pop();
                int t=stk.top();stk.pop();
                flag[t]=xx;
                vis[t]=false;
                if (t==s)
                {
                    break;
                }
            }
            xx++;
    }
}
vector *nMp;//[200010];
void build(int n)
{
  /\*  for (int i=1;i<=n;i++)
   {
       for (int j=head[i];j!=-1;j=e[j].next)
       {
           if (flag[e[j].to]!=flag[i])
           {
               nMp[flag[i]].push_back(flag[e[j].to]);
               nMp[flag[e[j].to]].push_back(flag[i]);
           }
       }
   }*/
   for (int i=0;i<n;i++)
   {
       int s,t;
       s=flag[e[i*2].from];
       t=flag[e[i*2].to];
       if (s!=t)
       {
           nMp[s].push_back(t);
           nMp[t].push_back(s);
       }
   }
}

int ans,root;
void dfs(int now,int pre,int cnt)
{
    if (ans<=cnt)
    {
        ans=cnt;
        root=now;
    }
    for (int i=0;i<nMp[now].size();i++)
    {
        if (nMp[now][i]==pre) continue;
        dfs(nMp[now][i],now,cnt+1);
    }
}

int main()
{
//  int size = 256 << 20; // 256MB
//  char \*p = (char\*)malloc(size) + size;
//  \_\_asm\_\_("movl %0, %%esp\\n" :: "r"(p) );

while (scanf("%d%d",&n,&m)!=EOF)
{
    xx=0;
    memset(flag,-1,sizeof(flag));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,false,sizeof(vis));
   // memset(stk,0,sizeof(stk));
    memset(head,-1,sizeof(head));
    stkCnt=0;
    for (int i=0;i<n+5;i++) mp[i].clear();
    if (m+n==0) break;
    for (int i=0;i<2*m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        e[i].to=b;
        e[i].from=a;
        e[i].next=head[a];
        head[a]=i;
        i++;
        e[i].to=a;
        e[i].from=b;
        e[i].next=head[b];
        head[b]=i;
    }
    tarjan(1,1);
    nMp=new vector[xx+10];
    build(m);
    ans=0;
    root=0;
    dfs(0,0,0);
    dfs(root,root,0);
    printf("%d\\n",xx-1-ans);
   // delete mp;
    delete nMp;
}
    return 0;
}

发表于 更新于 分类于 阅读次数：

     cf181 div 2的C题http://codeforces.com/contest/300/problem/C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long long cal(long long s)//s^(MOD-2)
{
     long long ans=1;
     long long n=MOD-2;
     while (n!=0)
     {
         if (n&1) ans=ans*s%MOD;
         s=s*s;
         n=n>>1;
     }
     return ans;
}

long long C(int m,int n)//f[x]=x! 求的是C(m,n)
{
     return f[m]*cal(f[n]*f[m-n]%MOD)%MOD;
}

//CF181D2C 

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MOD 1000000007
using namespace std;

int a,b,n;
long long f[1000001]={0};

long long power(long long s)
{
    long long n=MOD-2;
    long long ans=1;
    while (n!=0)
    {
        if (n&1) ans=(ans*s)%MOD;
        s=(s*s)%MOD;
        n=n>>1;
    }
    return ans%MOD;
}

long long C(int n,int i)
{
    return f[n]*power(f[n-i]*f[i]%MOD);
}

bool check(int s)
{
    while (s!=0)
    {
        int t=s%10;
        if (t!=a && t!=b) return false;
        s=s/10;
    }
    return true;
}

int main()
{
    scanf("%d%d%d",&a,&b,&n);
    f[0]=1;
    for (int i=1;i<n+1;i++){
      f[i]=(i*f[i-1])%MOD;
    }
    long long ans=0;
    for (long long i=0;i<=n;i++)
    {
        if (check(i*a+(n-i)*b)){ans=(ans+C(n,i))%MOD;}
    }
    printf("%d",ans);
    return 0;
}