XtestW's Blog

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

本文只是概述几种简单的传统加密算法，没有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
52
53

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
54
55

#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;
}

kruskal算法的主要思想就是从当前路径中选择一个不能构成环的最小边加入

for (int i=1;i<n;i++)
{
int mi=1000000,k;
for (int j=0;j<m;j++)
{
if ((v[e[j].x] + v[e[j].y]==1 || i==1 ) && e[j].d<mi){ mi=e[j].d; k=j; } } result.push_back(k); v[e[k].x]=1; v[e[k].y]=1; if (mi>ma) ma=mi;
}

因为此算法本质上是一个贪心策略，可以通过并查集进行优化，现将其从小到大排序

int kruskal()//返回最小生成树的和
{
int ans=0;
qsort(e,e+n,cmp);//cmp是将其按d值从小到大排序
for (int i=0;i<m;i++)//m is the number of edges
{
if (find(e[i].x)!=find(e[i].y)) {//判断边的两个端点是否在一个集合
result.push_back(i);
ans+=e[i].d;
}
}
return ans;
}

poj 1861

#include
#include
#include
#include
using namespace std;
struct P{
    int x,y,d;
};
P e[15100];
vector result;
int ma=-1;
int v[1002]={0};
int main()
{
    int n,m;
    scanf(“%d%d”,&n,&m);
    for (int i=0;i<m;i++)
        scanf(“%d%d%d”,&e[i].x,&e[i].y,&e[i].d);
    for (int i=1;i<n;i++)
    {
        int mi=1000000,k;
        for (int j=0;j<m;j++)
        {
            if ((v[e[j].x] + v[e[j].y]==1 || i==1 ) && e[j].d<mi){                 mi=e[j].d;                 k=j;             }         }         result.push_back(k);         v[e[k].x]=1;         v[e[k].y]=1;         if (mi>ma) ma=mi;
    }
    cout<<ma<<endl;
    cout<<result.size()<<endl;
    for (int i=0;i<result.size();i++)
    {
        cout<<e[result[i]].x<< “ “<<e[result[i]].y<<endl;
    }
    return 0;
}

题意不追溯，关于匈牙利算法看：http://my.oschina.net/xuwei8091/blog/126320。 最小路径覆盖等于N-最大匹配

#include #include #include using namespace std;
int T;
int n,m;
int map[200][200];
int vis[200];
int result[200];
bool find(int s)
{
for (int i=1;i<=n;i++)
{
if (map[s][i] && !vis[i])
{
vis[i]=1;
if (result[i]==0 || find(result[i]))
{
result[i]=s;
return true;
}
}
}
return false;
}
int main()
{
scanf(“%d”,&T);
while (T–){
memset(map,0,sizeof(map));
memset(result,0,sizeof(result));
scanf(“%d%d”,&n,&m);
for (int i=0;i

关于算法的说明，可以参看这个大牛的讲解，很详细： http://imlazy.ycool.com/post.1603708.html 直接上代码

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

bool find(int s)
{
    for (int i=1;i<=n;i++)//从1到n编号
    {
         if (map[s][i] && !visit[i])
        {
            visit[i]=1;
            if (pre[i]==0 || find(pre[i]))
             {
                 pre[i]=s;
                 return true;      
             }
    }
    return false;
}

int hungary()//返回最大匹配数
{
     int ans=0;
     for (int i=1;i<=n;i++)
     {
        memset(visit,0,sizeof(visit));
        if (find(i)) ans++;
     }
     return ans;
}

  好吧，具体的代码就应该是这样了，但是二分图是无向图吧。。。有向图，怎么破…

题意就不赘诉了，青蛙约会。是一个关于欧几里得扩展的定理的题目

int gcd(int a,int b)//欧几里得求最大公约数
{
if (b==0) return a;
return gcd(b,a%b);
}

int exgcd(int a,int b,int &x,int &y)//欧几里得扩展求ax+by=gcd(a,b)的一组解
{
if (b==0) {x=1;y=0;return a;}
int r=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}

针对本题，需要注意的是，    1.数据比较大，需要用long long 2.因为是时间，所以x不能是负数，如果出现负数怎么办呢？ a*x1+b*y1=d(d=gcd(a,b)),那个转换成 a*(x1+b*n）+b*（y1-a*n)=d 最终x=(x1%b+b)%b;或者(x1+(abs([x1/b])+1)*b)%b; AC代码：

#include #include #include #include #include using namespace std;

int gcd(int a,int b)
{
if (b==0) return a;
return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if (b==0){ x=1;y=0;return a;}
long long r=exgcd(b,a%b,x,y);
long long t=x;
x=y;
y=t-(a/b)*y;
return r;
}
int main()
{
long long x,y,m,n,L;
cin>>x>>y>>m>>n>>L;
long long s=gcd(n-m,L);
if ((x-y)%s!=0){
cout<<”Impossible”<

好吧，前两天做了一场CF，遇到一道并查集的题目，感觉并查集还需学习啊，记录一下 具体的算法如下

1. 有father数组，全部初始化为本身
2. 添加一个关系进来的时候，s–t，找到s的祖先a,t的祖先b，将a的father设为b
3. 通过查找祖先，来确定是否在一个集合内

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

void init(int n){//初始化，节点编号1-n
    for (int i=1;i<=n;i++) father[i]=i;
}

int find(int x)//查找祖先节点
{
	while (father[x]!=x) x=father[x];
	return x;
}

void add(int s,int t)//增加一个关系，改变集合
{
  int a=find(s);
  int b=find(t);
  father[a]=b;
}



bool judge(int s,int t)//判断是不是一个集合
{
    return find(s)==find(t);
}