Believe it

相信不屈不挠的努力,相信战胜死亡的年轻

发表于 分类于 ， 本文字数： 332 阅读时长 ≈ 1 分钟

给你一个括号数组，里面有不同种类的括号，每个种类都有左右两种括号，左右括号可以结合，很多组询问，问你一个区间内括号是否匹配， 1.一个空的字符串是一个合法的文档。 2.如果A,B都是合法的文档，那么AB也是合法的文档。 3.如果S是合法的文档，那么aSb也是合法的文档，其中a,b是同一种括号，并且a是左括号，b是右括号

用栈来模拟，对于每一个括号，我们用数组L记录当处理完这个括号（压入栈并完成当前匹配）的栈顶元素的下标，当我们判断[l,r]时之用比较L[l-1]与L[r]即可

发表于 分类于 ， ， 本文字数： 661 阅读时长 ≈ 1 分钟

对于尺取法，一般用于线性表的处理。

我们有两个指针一样的东西，l和r分别指向两个元素，l于r之间的东西就是我们尝试维护的东西。

例题1

询问序列中和大于s的子串的最小长度。

题解

初始左端点为0，右端点为n-1, 长度为n-1

如果当前区间不满足，同时右移左右端点

如果当前区间满足，最小长度自减

例题2

询问序列中以第k个元素为起点的长度为n的子串的前缀和的最小值大于s的最小i

题解

设立一个前缀和最小值，以及区间和，让尺子长度逐渐增大，增大到N时结束

如果当前区间最小值满足，右移右端点，更新区间和，如果区间和小于于最小值，那么当我们右移左端点时当前最小前缀和在右端点不动时永远都是整个区间和，右移左端点直到区间和大于s，迭代

例题3

询问序列中与值t相差最小的子串和

题解

​ 对前缀和排序，再尺取

​ 如果右端点减去左端点大于t，尝试用此时的端点来更新答案，然后右移左端点，如果右端点减去左端点依旧大于t，迭代，反之先尝试更新答案，然后右移右端点直到右端点减去左端点大于t(最后一次移动前尝试更新答案)，迭代

例题4

询问序列中包含所有值的最短子串

题解

​ 建立map记录有没有，cnt记录种类，以加快判断，

​ 如果当前区间不满足，右移右端点，如果此时长度大于或等于已经找到的最小长度(初始化为无穷大)，右移左端点，迭代

​ 如果当前区间满足，更新最小长度，右移右端点，迭代

发表于 分类于 ， ， 本文字数： 538 阅读时长 ≈ 1 分钟

无限大的棋盘有一只走‘日’的马呆在0，0处，也是坐标原点，（存在四个象限），给你（x，y）问你要至少跳多少步才能跳过去

不妨设\(x>y\)

\(x\le2y\),可以证明当x和y足够大的时候

\((x+y)\mod3=0\)时，我们只需要\(\frac{x+y}{3}\)步，这些步数由两种跳跃组成，他们分别是(1,2)和(2,1)

\((x+y)\mod 3=1\)时，我们选择（1，-2）或者（-2，1）来跳跃，跳跃之后\((x+y)\mod3=0\)所以一共需要\(\frac{x+y}{3}+1\)步

同理\((x+y)\mod 3=2\)时一共需要\(\frac{x+y}{3}+2\)步

综合为需要\(\frac{x+y}{3}+((x+y)\mod 3)\)步

同样分析出\(x>2y\)在\(x\)和\(y\)足够大的时候，需要\(y+\frac{x-2y}{4}\times2+(x-2y)\%4\)步

那么这个足够大是多少呢？是x>3&&y>3

发表于 分类于 ， ， 本文字数： 2.2k 阅读时长 ≈ 2 分钟

就像cantor映射一样，字符串hash采取一种更加随机化的映射，它的通项公式为\(hash[i]=\sum _{j=0}^{i}s[j]*p^{i-j}\),如此将一个字符串随机映射到了一个数字上，

我们来看这个公式的意义，他把一个字符串映射到了一个p进制数字上，位数代表着字符串的长度，然后我们将这个p进制数转化为十进制数并对1e9+7取模来存储，通项公式不好求，但是我们可以通过递推公式来求

\(hash[i]=hash[i-1]\cdot p+s[i]\)

这个公式就比较友好了，另外对于任意区间，我们有这个公式

\(hash[l~r] = hash[r] - hash[l - 1] \cdot pow(p, r - l + 1)\)

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
struct str_hash {//单hash
    static const int maxn = 3e5 + 5, p = 47, mod = 1e9 + 7;
    static int pw[maxn], pr[maxn];
    int h1[maxn], h2[maxn], len;

    str_hash() {
        if (pw[0] == 1) return;
        pw[0] = pr[0] = 1;
        int rev = qpow(p, mod - 2, mod);
        for (int i = 1; i < maxn; i++) {
            pw[i] = 1ll * pw[i - 1] * p % mod;
            pr[i] = 1ll * pr[i - 1] * rev % mod;
        }
    }

    void extend(char c) {
        len++;
        h1[len] = (1ll * h1[len - 1] * p + c) % mod;
        h2[len] = (h2[len - 1] + 1ll * c * pw[len - 1]) % mod;
    }

    void ini() { len = 0; }

    int query(int l, int r) { return (h1[r] + 1ll * h1[l - 1] * (mod - pw[r - l + 1])) % mod; }//注意没有下标检查
    int qurev(int l, int r) { return 1ll * (h2[r] - h2[l - 1] + mod) * pr[l - 1] % mod; }//注意没有下标检查
};

int str_hash::pw[maxn], str_hash::pr[maxn];


//双hash，双倍常数，1e6 的数据 nlgn的做法 1s的时限 不建议使用
typedef unsigned long long ull;

struct double_hash {
    static const ull maxn = 1e3 + 666, p = 26, mod1 = 1e9 + 7, mod2 = 1e9 + 9;
    static ull pw1[maxn], pw2[maxn];
    ull hash1[maxn], hash2[maxn], len;

    double_hash() {
        if (pw1[0] == 1)return;
        pw1[0] = pw2[0] = 1;
        for (ull i = 1; i < maxn; i++) {
            pw1[i] = pw1[i - 1] * p % mod1;
            pw2[i] = pw2[i - 1] * p % mod2;
        }
    }

    void build(char *s, ull _len) {
        len = _len;
        for (ull i = 1; i <= len; i++) {
            hash1[i] = (hash1[i - 1] * p + s[i] - 'a') % mod1;//无边界
            hash2[i] = (hash2[i - 1] * p + s[i] - 'a') % mod2;//same
        }
    }

    ull query1(ull l, ull r) { return (hash1[r] - hash1[l - 1] * pw1[r - l + 1] % mod1 + mod1) % mod1; }

    ull query2(ull l, ull r) { return (hash2[r] - hash2[l - 1] * pw2[r - l + 1] % mod2 + mod2) % mod2; }

    ull query(ull l, ull r) { return query1(l, r) * mod2 + query2(l, r); }//注意没有下标检查
} hash_a, hash_b;

ull double_hash::pw1[maxn], double_hash::pw2[maxn];

http://codeforces.com/contest/727/problem/E

给你一个长度为n×k的环，环上每一个位置有一个字符。现在给你g个长度为k的字符串，问是否可以在g个字符串中选出n个构成这个环。 1 ≤ n ≤ 10^5, 1 ≤ k ≤ 10^5, n*k ≤ 10^6, n ≤ g ≤ 10^5, g*k ≤ 2*10^6

枚举起点,hash.

发表于 分类于 ， ， 本文字数： 661 阅读时长 ≈ 1 分钟 
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
inline void GetNext(char *s) {
    int l = strlen(s), t;
    next[0] = -1;
    for (int i = 1; i < l; ++i) {
        t = next[i - 1];
        while (s[t + 1] != s[i] && t >= 0)
            t = next[t];
        if (s[t + 1] == s[i])
            next[i] = t + 1;
        else
            next[i] = -1;
    }
}

inline void KMP(char *s1, char *s2) {
    ans.clear();
    GetNext(s2);//预处理next数组
    int len_1 = strlen(s1);
    int len_2 = strlen(s2);
    int i = 0, j = 0;
    while (j < len_1) {
        if (s2[i] == s1[j]) {
            ++i;
            ++j;
            if (i == len_2) {
                ans.push_back(j - len_2 + 1);
                i = next[i - 1] + 1;
            }
        } else {
            if (i == 0)
                j++;
            else
                i = next[i - 1] + 1;
        }
    }
}

发表于 分类于 ， ， 本文字数： 1.5k 阅读时长 ≈ 1 分钟 
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
const double eps=1e-8;
struct MCMF{
    static const int maxn=200,maxm=40000;
    struct star{int v,nex;double c,w;} edge[maxm<<1];
    int head[maxn],cnt,n;
    int inq[maxn],pre[maxn];
    double dist[maxn];

    void ini(int n){
        cnt=-1;this->n=n;
        for(int i=0;i<=n;i++) head[i]=-1;
    }
    void add_star(int u, int v, double c, double w){
        //cout<<"     "<<u<<" "<<v<<" "<<c<<" "<<w<<endl;
        edge[++cnt]=star{v,head[u],c, w}; head[u]=cnt;
        edge[++cnt]=star{u,head[v],0,-w}; head[v]=cnt;
    }
    void minCostMaxFlow(int s, int t,double&flow,double&cost){
        flow=cost=0;
        while(true){
            for(int i=0;i<=n;i++) dist[i]=1e9;
            queue<int>que; que.push(s);
            inq[s]=1; dist[s]=0;

            while(!que.empty()){
                int u=que.front();
                que.pop(); inq[u]=0;
                for(int i=head[u];~i;i=edge[i].nex){
                    int v=edge[i].v;
                    double c=edge[i].c,w=edge[i].w;
                    if(c>eps&&dist[v]>dist[u]+w+eps){
                    // if(c>0&&dist[v]>dist[u]+w){
                        dist[v]=dist[u]+w;
                        pre[v]=i;
                        if(!inq[v]) que.push(v);
                        inq[v]=1;
                    }
                }
            }
            if(dist[t]==1e9) return ;
            double addf=1e9;
            for(int x=t;x!=s;x=edge[pre[x]^1].v) addf=min(addf,edge[pre[x]].c);
            for(int x=t;x!=s;x=edge[pre[x]^1].v){
                edge[pre[x]].c-=addf;
                edge[pre[x]^1].c+=addf;
            }
            flow+=addf;
            cost+=dist[t]*addf;
        }
    }
} g;