深信服_$21$ 年 $10$ 月 $19$ 日

题型为：多选题，填空题，编程题（$2$ 道）。
多选题、填空题主要设计 C 以及 C++ 基础知识。

编程题 1

题意描述

某厨师要出售 $1 \text{~} 6$ 种不同的食物，每种食物需要使用不同的厨具进行烹饪，厨师的灶台最多容纳 $3$ 种厨具，当灶台空间不够时，厨师会更换最久没有使用的厨具。已知每种食物烹饪需要 $15$ 分钟，如果需要更换厨具则每次需要 $6$ 分钟的厨具更换时间。按照点单顺序计算本轮烹饪食物需要花费的总时间。（要求 $C$ 语言实现）

输入

每行一个数字，1-6 代表 6 种订单，7 表示本轮烹饪结束。
2 2 5 6 4 2 4 6 5 2 3 3 3 3 4 6 1 5 1 1 7

输出

厨师所需的总时间 
354

$C$ 语言代码实现

#include<stdio.h>
#include<string.h>

typedef long long LL;

#define N 3

int q[N], head, tail = -1;

LL res;

int flag = 0;      // 0：队列未满， 1：队列已满

int main() {
    int t;
    while(scanf("%d", &t) && t != 7) {
        // 判断队列中是否有重复元素
        for (int i = head; i <= tail; i++) {
            if (t == q[i]) {
                flag = 0;
            }
        }

        if (flag == 0) {
            int count = tail - head + 1;    // 当前队列中元素数量
            if (count == 0) {
                q[++tail] = t;
            }
            else if (count == 1) {
                if (t != q[0])
                    q[++tail] = t;
            } else if (count == 2) {
                if (t != q[0] && t != q[1]) {
                    q[++tail] = t;
                } else if (t == q[0]) {
                    q[0] = q[1];
                    q[1] = t;
                } 
            } else if (count == 3) {
                if (q[0] == t) {
                    q[0] = q[1];
                    q[1] = q[2];
                    q[2] = t;
                } else if (q[1] == t) {
                    q[1] = q[2];
                    q[2] = t;
                } 
            }

            res += 15;
            if (tail == 2) {
                flag = 1;           // 队列已经满
            }
        } else {        // 维护队列有序性
            q[0] = q[1];
            q[1] = q[2];
            q[2] = t;
            res = res + 21;
        }
    }
    printf("%d\n", res);
    return 0;
}

编程题 2

LC 原题链接：63. 不同路径 II

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>

using namespace std;
int n, m;

int main() {
    cin >> n >> m;
    vector<vector<int>> matrix(n, vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }

    vector<vector<int>> f(n, vector<int>(m, 0));
    // 边界处理：第一行
    for (int i = 0; i < m; i++) {
        f[0][i] = 1;
        if (matrix[0][i] == 1) {
            f[0][i] = 0;
            break;
        }
    }
    // 边界处理：第一列
    for (int i = 0; i < n; i++) {
        f[i][0] = 1;
        if (matrix[i][0] == 1) {
            f[i][0] = 0;
            break;
        }
    }

    // 从左边来，从上面来
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            f[i][j] = f[i][j - 1] + f[i - 1][j];
            if (matrix[i][j] == 1) {
                f[i][j] = 0;
            }
        }
    }
    cout << f[n - 1][m - 1] << endl;
    return 0;
}

重学 之 离散化

离散化真挺难的，这里给大家推个方法 如果看不懂视频，题解也不懂的话

那就只能靠自己了，可以把AC代码粘过来，不涉及递归什么特定的代码执行顺序的，都是一行一行代码往下看，对于每次的操作自己写一个输出函数，观察这一行或几行代码是干什么的

亲测有效，(大佬就不用看了)，但是一定要有耐心，相信我，急于求成是学不好的

进入正题：什么是离散化?为什么用离散化解决这道题目？

还是拿题目来说事： 区间和这道题：

废话不多说，看到给定的下标值是-1e9到1e9就知道不可能开个数组循环相加了吧。就是因为下标值太大所以要用离散化

解题思路：我们定义前缀和数组a, s是用来求最终答案的，还需要一个alls 的 vector数组，使用来存储输入的所有下标的，
这里的下标包括 给下标为x的加上c的下标 还有 输入一个区间，输出区间内的和的 区间下标，再来一对 add 和
query 的 vector数组，前缀和的数值需要用到add数组的(也就是在下标为x的位置加上c) 这里的x,c都存储在add数组中，
query数组存储区间下标(l,r), 用来最后查询区间和并输出答案。

代码分析：
1. 首先我们将读入的n次 给下标为x的位置加上c 的x 和 c都存入add数组中，同时将下标x存储到数组alls中
2. 接下来我们会读入m个区间， 将每个区间下标l, r存储到 query数组中，同时存储到数组alls中
3. 在这里我们已经处理完所有输入，在下一步之前你不妨 试着输出一下 alls, add, query, 这三个数组都存储了那些元素
4. 已知alls数组中存储了所有下标值，为了离散化需要先将他们排序，因为离散过程使用的二分，二分保证有序某种性质， 但二分 != 单调性
5. 排完序后记得 去重，去重保证了每个下标值只会有一个且唯一的离散后的映射值，使用unique函数实现
6. 这时候你可以再次输出alls数组，看看数据变化，有助于理解(离散过程使用二分实现的，就是在一个有序序列中找到当前值x的位置，就是一个简单的二分)
7. 这时候下标处理好了，就只用处理每个下标所代表的值了，将插入数据中的每个离散后的下标用a数组来保存当前下标的值是多少
8. 给定单个数组a，如何求出他的前缀和数组不用讲了吧。用s来存储。
9. 万事俱备，只用处理每个询问，操作query数组，记得输出答案的下标 是 经过 离散化后的映射下标值

完美解决！

反正我是看了很久，一步步啃代码写出来了自己的理解。

(写了很久，希望能帮到你们)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;

int n, m;

//用来存储下标
vector<int> alls;

//存储区间下标，和查询操作
vector<PII> add, query;

//前缀和数组
int a[N], s[N];

int find(int x)
{
    int l = 0, r = alls.size() - 1;
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(alls[mid] >= x) r = mid;
        else l = mid + 1;
    }

    return r + 1;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int x, c;
        cin >> x >> c;

        add.push_back({x, c});

        alls.push_back(x);
    }

    for(int i = 1; i <= m; i ++)
    {
        int l, r;
        cin >> l >> r;

        query.push_back({l, r});

        alls.push_back(l);
        alls.push_back(r);
    }

    //先排序，离散化之前每个数只能出现一次
    sort(alls.begin(), alls.end());

    //去重
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    //处理插入,就是将每个下标进行离散化
    for(auto item : add) 
    {
        int x = find(item.first);
        a[x] += item.second;
    }

    //操作一遍前缀和
    for(int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];

    //输出每次查询的结果
    for(auto item : query)
    {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;

}

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int N=scanner.nextInt();
int V=scanner.nextInt();
int []v;
v=new int[1000];
int []w;
w=new int[1000];
int[] arr=new int[5];
int b = 0;
int a=0;
for (int i=0;i<N;i++){
v[i]=scanner.nextInt();
w[i]=scanner.nextInt();
}

    for(int j=0;j<N;j++) {
        a = v[j] + v[j + 1];
       if(a<=V) {
           b= w[j] + w[j + 1];
       }
          else
             for (int k=1;k<N;k++){
                 arr[k]=b;
                 if (arr[0]<arr[k]){
                     arr[0]=arr[k];
                 }

       }

    }
    System.out.println(arr[0]);

}

}

白送的60分写法

虽然我也参考别人的博客改了好长时间吧

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> a[5010];
int n, m;
int ans[5010], cnt;
bool st[5010];

void dfs(int u, int father)
{
    if(st[u]) return ;

    st[u] = true;
    ans[ ++ cnt] = u;

    for (int i = 0; i < a[u].size(); i ++ )
    {
        int j = a[u][i];
        if(j == father) continue;

        dfs(j, u);
    }
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i ++ )
    {
        int u, v;
        cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }

    for (int i = 1; i <= n; i ++ ) sort(a[i].begin(), a[i].end());

    dfs(1, 0);

    for (int i = 1; i <= cnt; i ++ )
    {
        cout << ans[i] << ' ';
    }

    return 0;
}

正解

自己就先不写正解了
某谷的

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> a[5010];
int n,m;
int res[5010],ans[5010],tot;
int cir1[5010];
int u1[10010],v1[10010],cnt;
int vis[5010];
int du,dv;
int flag;
struct Edge {
    int from,to;
}e[5010];
void dfs2(int u,int fa) {
    if(vis[u])
        return ;
    vis[u]=1;
    ans[++tot]=u;
    for(int i=0;i<a[u].size();i++) {
        int v=a[u][i];
        if(v==fa)
            continue ;
        dfs2(v,u);
    }
}
void dfs1(int u,int fa) {
    if(vis[u])
        return ;
    vis[u]=1;
    res[++tot]=u;
    for(int i=0;i<a[u].size();i++) {
        int v=a[u][i];
        if(v==fa)
            continue ;
        if((u==du&&v==dv)||(u==dv&&v==du))
            continue ;
        dfs1(v,u);
    }
}
void dfs3(int from,int fa) {
    vis[from]=1;
    for(int i=0;i<a[from].size();i++) {
        int to=a[from][i];
        if(to==fa)
            continue ;
        if(vis[to]) {
            flag=1;
            cir1[to]=1;
            cir1[from]=1;
            u1[++cnt]=from;
            v1[cnt]=to;
            return ;
        }
        dfs3(to,from);
        if(flag&&cir1[to])
            if(cir1[from]) {
                flag=0;
                u1[++cnt]=from;
                v1[cnt]=to;
                return ;
            } else {
                cir1[from]=1;
                u1[++cnt]=from;
                v1[cnt]=to;
                return ;
            }
    }
}
int check() {
    for(int i=1;i<=n;i++) {
        if(res[i]<ans[i])
            return 1;
        else if(res[i]>ans[i])
            return 0;
    }
    return 0;
}
void update() {
    for(int i=1;i<=n;i++) {
        ans[i]=res[i];
    }
}
int main() {
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++) {
        scanf("%d%d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
        e[i].from=u;
        e[i].to=v;
    }
    for(int i=1;i<=n;i++)
        sort(a[i].begin(),a[i].end());
    if(m==n) {
        dfs3(1,0);
        int flag=1;
        for(int i=1;i<=cnt;i++) {
            du=u1[i];dv=v1[i];
            memset(vis,0,sizeof(vis));
            tot=0;
            dfs1(1,0);
            if(tot<n)
                continue ;
            if(flag) {
                update();
                flag=0;
            }
            if(check())
                update();
        }
        for(int i=1;i<=n;i++) {
            printf("%d ",ans[i]);
        }
    } else {
        dfs2(1,0);
        for(int i=1;i<=n;i++) {
            printf("%d ",ans[i]);
        }
    }
    return 0;
}

题目描述

给定两个正整数 a,m，其中 a<m。

请你计算，有多少个小于 m 的非负整数 x 满足：

gcd(a,m)=gcd(a+x,m)
输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据占一行，包含两个整数 a,m。

输出格式
每组数据输出一行结果，一个整数，表示满足条件的非负整数 x 的个数。

数据范围
前三个测试点满足，1≤T≤10。
所有测试点满足，1≤T≤50，1≤a<m≤1010。

样例

输入样例：
3
4 9
5 10
42 9999999967
输出样例：
6
1
9999999966

算法1

() $O()$

时间复杂度

参考文献

python3 代码

def my_gcd(a: int, b: int) -> int:
    while b > 0:
        tmp = a % b
        a = b
        b = tmp
    return a

def get_euler(num: int) -> int:
    res = num
    #----先找num所有的质因子
    x = 2
    while x * x <= num:
        if num % x == 0:
            res = res // x * (x - 1)
            #----将x这个质因子，全部除掉
            while num % x == 0:
                num //= x
        x += 1
    #----还有一个大的质因子，大于根号num的质因子
    if num > 1:
        res = res // num * (num - 1)
    return res


T = int(input())
for _ in range(T):
    a, m = map(int, input().split())
    res = get_euler(m // my_gcd(a, m))
    print(res)

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <assert.h>

using namespace std;

long long my_gcd(long long a, long long b)
{
    while (b > 0)
    {
        long long tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

long long get_euler(long long num)
{
    long long res = num;
    long long x = 2; 
    while (x * x <= num)
    {
        if (num % x == 0)
        {
            res = res / x * (x - 1);
            while (num % x == 0)
            {
                num /= x;
            }
        }
        ++ x;
    }
    if (num > 1)
    {
        res = res / num * (num - 1);
    }
    return res;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;    cin >> T;
    while (T -- )
    {

        long long a;    cin >> a;
        long long m;    cin >> m;

        cout << get_euler(m / my_gcd(a, m)) << endl;
    }

    return 0;
}

java 代码

import java.util.*;
import java.io.*;

public class Main
{
    public static long my_gcd(long a, long b)
    {
        while (b > 0)
        {
            long tmp = a % b;
            a = b;
            b = tmp;
        }
        return a;
    }

    public static long get_euler(long num)
    {
        long res = num;
        long x = 2;
        while (x * x <= num)
        {
            if (num % x == 0)
            {
                res = res / x * (x - 1);
                while (num % x == 0)
                {
                    num /= x;
                }
            }
            x ++;
        }
        if (num > 1)
        {
            res = res / num * (num - 1);
        }
        return res;
    }


    public static void main(String [] args)
    {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while (T -- > 0)
        {
            long a = scan.nextLong();
            long m = scan.nextLong();
            System.out.println(get_euler(m / my_gcd(a, m)));
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

改为：求方案数

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$Text 2

$\quad$$\quad$Just how much does the Constitution protect your digital data? The Supreme Court will now consider whether police can search the contents of a mobile phone without a warrant if the phone is on or around a person during an arrest.

$\quad$$\quad$宪法保护了多少你的个人隐私数字信息？最高法院如今将考虑是否允许警察在怀疑或已经确凿一个人是嫌犯的时候，在没有搜查令的情况下搜查嫌犯的手机清单。

$\quad$$\quad$California has asked the justices to refrain from a sweeping ruling particularly one that upsets the old assumptions that authorities may search through the possessions of suspects at the time of their arrest. It is hard, the state argues, for judges to assess the implications of new and rapidly changing technologies.

$\quad$$\quad$加州已经要求法官不要做出一项全面的裁决，尤其是那项裁决颠覆了以往的假设，即当局在逮捕嫌疑人时可以搜查他们的财产。该州认为，法官很难评估快速变化的新技术的影响。

$\quad$$\quad$The court would be recklessly modest if it followed California’s advice. Enough of the implications are discernable, even obvious, so that the justices can and should provide updated guidelines to police, lawyers and defendants.

$\quad$$\quad$如果法庭采取了加州的建议，那就会显得他们太过谦逊了。足够多的影响里是可以被重视的，甚至是明显的，所以法官能且应当提供与时俱进的指导方针给警察、律师和被告人。

$\quad$$\quad$They should start by discarding California’s lame argument that exploring the contents of a smart phone — a vast storehouse of digital information — is similar to, say, going through a suspect’s purse. The court has ruled that police don’t violate the Fourth Amendment when they go through the wallet or pocketbook of an arrestee without a warrant. But exploring one’s smart phone is more like entering his or her home. A smart phone may contain an arrestee’s reading history, financial history, medical history and comprehensive records of recent correspondence. The development of “cloud computing,” meanwhile, has made that exploration so much the easier.

$\quad$$\quad$他们应该从抛弃加州的蹩脚论点开始，即探索智能手机的内容—一个巨大的数字信息仓库—类似于，比如说，搜查嫌疑人的钱包。法院规定了警察在逮捕过程中在没有搜查令的情况下搜查嫌犯的钱包或皮夹不违反第四搜查令。但是搜查一个人的手机更像进了他的家门。手机可能包含了嫌犯的阅读记录，财政记录，医药记录和最近联系人的记录。与此同时，“云计算”的发展使这种探索变得更加容易。

$\quad$$\quad$Americans should take steps to protect their digital privacy. But keeping sensitive information on these devices is increasingly a requirement of normal life. Citizens still have a right to expect private documents to remain private and protected by the Constitution’s prohibition on unreasonable searches.

$\quad$$\quad$美国人需要采取保护自己数字隐私的行动。但在这些设备上保存敏感信息正日益成为日常生活的要求。公民仍然有权要求私人文件保持私密性，并受到宪法禁止不合理搜查的保护。

$\quad$$\quad$As so often is the case, stating that principle doesn’t ease the challenge of line-drawing. In many cases, it would not be overly burdensome for authorities to obtain a warrant to search through phone contents. They could still invalidate Fourth Amendment protections when facing severe, urgent circumstances, and they could take reasonable measures to ensure that phone data are not erased or altered while waiting for a warrant. The court, though, may want to allow room for police to cite situations where they are entitled to more freedom.

$\quad$$\quad$通常情况下，陈述原则并不能缓解制定法条的挑战。在很多情况下，对于当局来说，获得搜查电话内容的搜查令并不会太麻烦。在面临严重、紧急的情况时，他们仍然可以使第四修正案的保护失效，他们还可以采取合理措施，确保在等待搜查令期间，手机数据不会被删除或更改。不过，法院可能希望给警察留出空间，让他们引述他们有权获得更多自由的情况。

$\quad$$\quad$But the justices should not swallow California’s argument whole. New, disruptive technology sometimes demands novel applications of the Constitution’s protections. Orin Kerr, a law professor, compares the explosion and accessibility of digital information in the 21st century with the establishment of automobile use as a virtual necessity of life in the 20th: The justices had to specify novel rules for the new personal domain of the passenger car then; they must sort out how the Fourth Amendment applies to digital information now.

$\quad$$\quad$但是法官们不应该全盘接受加州的论点。新的颠覆性技术有时需要对宪法保护的新应用。法学教授奥林·克尔(Orin Kerr)将21世纪数字信息的爆炸式增长和可获取性与20世纪汽车使用作为一种实际生活必需品的确立进行了比较:当时，法官必须为乘用车的新个人领域制定新的规则;他们现在必须弄清楚第四修正案如何适用于数字信息。

26 The Supreme Court will work out whether, during an arrest, it is legitimate to

[A] prevent suspects from deleting their phone contents.

[B] search for suspects’ mobile phones without a warrant.    正确

[C] check suspects’ phone contents without being authorized.

[D]prohibit suspects from using their mobile phones.

27 The author’s attitude toward California’s argument is one of

[A] disapproval.      正确

[B] indifference.

[C] tolerance.

[D]cautiousness.

28 The author believes that exploring one’s phone contents is comparable to

[A] getting into one’s residence.        正确

[B] handling one’s historical records.

[C] scanning one’s correspondences.

[D] going through one’s wallet.

29 In Paragraph 5 and 6, the author shows his concern that

[A] principles are hard to be clearly expressed.

[B] the court is giving police less room for action.

[C] citizens’ privacy is not effectively protected.       正确

[D] phones are used to store sensitive information.

30 Orin Kerr’s comparison is quoted to indicate that

[A] the Constitution should be implemented flexibly.       正确

[B] new technology requires reinterpretation of the Constitution.

[C]California’s argument violates principles of the Constitution.

[D]principles of the Constitution should never be altered

思路

1. 先将所有数字与所有字符串分别放放到两个数组中，其中“DDD nao cadastrado”我用数字0表示，也可以用其他与前面的数不重复的数表示[HTML_REMOVED]
2. 输入一个数字后，我们先确定数字是否在数组中，如果在那我们需要确定ta的索引值；若不在则索引值为8，通过索引值，我们可以输出对应字符串数组位置的字符串，及结果。

C++数组法

#include <iostream>

using namespace std;

int main(){
    int DDD[9]={61,71,11,21,32,19,27,31,0},i,t;
    string Des[9]={"Brasilia","Salvador","Sao Paulo","Rio de Janeiro","Juiz de Fora","Campinas","Vitoria","Belo Horizonte","DDD nao cadastrado"};
    cin >> t;
    for(i=0;i<8;i++) if(DDD[i]==t) break;
    cout << Des[i] << endl;
    return 0;
}

python

inp = int(input())
DDD=[61,71,11,21,32,19,27,31]
Des=["Brasilia","Salvador","Sao Paulo","Rio de Janeiro","Juiz de Fora","Campinas","Vitoria","Belo Horizonte","DDD nao cadastrado"]
if inp in DDD:
    print(Des[DDD.index(inp)])
else:
    print(Des[8])

欢迎各位大佬评论

给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数l1,r1,l2,r2，请你判断[l1,r1]和[l2,r2]这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式
第一行包含整数n和m，表示字符串长度和询问次数。

第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。

接下来m行，每行包含四个整数l1,r1,l2,r2，表示一次询问所涉及的两个区间。

注意，字符串的位置从1开始编号。

输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。

每个结果占一行。

数据范围
1≤n,m≤105
输入样例：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

Yes
No
Yes

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,P=131;
typedef unsigned long long ull;
char str[N];
int n,m,l1,r1,l2,r2;
ull h[N],p[N];
ull get(int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}
int main(){
    cin>>n>>m>>str+1;
    p[0]=1;
    for(int i=1;i<=n; i++){
        p[i]=p[i-1]*P;
        h[i]=h[i-1]*P+str[i];
    }
    while(m--){
        cin>>l1>>r1>>l2>>r2;
        if(get(l1,r1)==get(l2,r2))puts("Yes");
        else puts("No");
    }
    return 0;
}

字符串前缀哈希法:

例:
str=="ABCABCDEWUZGNMACWING"
h[0]=0
h[1]="A"的哈希值
h[2]="AB"的哈希值
h[3]="ABC"的哈希值
h[4]="ABCD"的哈希值
   ······
预处理所有出来前缀的哈希值
问题1:如何定义某前缀的哈希值？
例：求"A B C D"的哈希值
公式：h[i]=h[i-1]*P+str[i];
(1)把它看成P进制的数，有四位，第1位里的数是A，第2位里的数是B，第3位里的数是C，第4位里的数是D（从左边数）。
假设只有大写字母"A"~"Z"
A B C D E ...... Z
1 2 3 4 5 ...... 26
ABCD=P进制的1234
再把它转成十进制
(1*p^3+2*p^2+3*p^1+4*p^0)
因为会非常大，所以需要%Q来把一个字符串映射成一个从0~q-1的一个数
注意：
（1）不可以把-个字母映射成0
例:
   A=0
  AA=0                  冲突
 AAA=0
AAAA=0
......
哈希数字可存在冲突，
哈希字符串不存在冲突。
经验值：
p=131或13331
Q=2的六十四次方
99.99%不冲突
哈希前缀的好处：用它可以求出来任意一个子串的哈希值
已知：
L
R
H[R]    1~R的哈希值
h[l-1]  1~L-1的哈希值
公式：h[r]-h[l-1]*p[r-l+1];
求两段哈希值，如果哈希值相同，认为字符串就相同，如果哈希值不同，认为字符串就不同