2019杭电多校1006和1007算法日常[4/100]

发表于 更新于 分类于 阅读次数：
1006 ekmp本来应该10mins写完(发现好多大佬用dc3(一种据说复杂度O(n)的后缀数组算法,发现自己孤陋寡闻))，结果自己太菜写了两个小时，然后1007是真滴有点好玩,只是我太菜,一开始把自己玩死了 -- 以及今天叨叨好像有点多

序

  • 今天是杭电多校第5场，然后1006签到本来应该10mins内写完，然后我菜鸡写了2小时(各种问题不熟练和紧张)，赛后发现有大佬用dc3(一种据说复杂度O(n)的后缀数组算法,发现自己孤陋寡闻)
  • 1007真滴有趣…闪电蛇皮走位，然后自己想复杂了一点点…

题目

链接

2019杭电多校5

1006解法

Ekmp，用s.substr(1)的串来做ekmp函数的原串，s做ekmp函数的匹配串，这样跑一次ekmp就行，然后累加extend

ekmp学习教程·我觉得比较好的一个(我也用这个学的)

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
#include <iostream>
#include <string>
using namespace std;
long long ans;
// int next[1000000];
int nxt[1000000];
int extend[1000000];
string S, T;
int n, m;
/* 求解 T 中 next[]，注释参考 GetExtend() */
void GetNext(string & T, int & m, int next[])
{
    int a = 0, p = 0;
    next[0] = m;

    for (int i = 1; i < m; i++)
    {
        if (i >= p || i + next[i - a] >= p)
        {
            if (i >= p)
                p = i;

            while (p < m && T[p] == T[p - i])
                p++;

            next[i] = p - i;
            a = i;
        }
        else
            next[i] = next[i - a];
    }
}

/* 求解 extend[] */
void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[])
{
    int a = 0, p = 0;
    GetNext(T, m, next);

    for (int i = 0; i < n; i++)
    {
        if (i >= p || i + next[i - a] >= p) // i >= p 的作用：举个典型例子，S 和 T 无一字符相同
        {
            if (i >= p)
                p = i;

            while (p < n && p - i < m && S[p] == T[p - i])
                p++;

            extend[i] = p - i;
            a = i;
        }
        else
            extend[i] = next[i - a];
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int t;
    cin>>t;
    while(t--){
        ans = 0;
        cin>>S;
        n = S.size();
        T = S.substr(1);
        m = n - 1;
        /*可能程序以为我用了前面的函数声明中的next[],所以说我模棱两可,加个全局的命名空间就行
        或者换个变量名也行*/
        // GetExtend(T, m, S, n, extend, ::next);
        GetExtend(T, m, S, n, extend, nxt);
        for (int j = 0; j < m; j++){
            // cout << extend[j] << " \n"[j==m-1];
            ans += extend[j]+j==n-1 ? extend[j] : extend[j]+1 ;
        }


        cout << ans << endl;
    }
    return 0;
}

1007解法

法一

a[i] = a[i-1]+a[i-3],就是对于第i项有两种情况，要么是直接往上走要么是闪电

法二

dls说暴力打表找规律比较不用动脑子，哭了，臭大佬，好过分

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int inf = 0x3f3f3f3f;
const int maxn = 100000 + 5;

ll a[maxn];

int main() {
    a[1] = a[2] = a[3] = 1;
    for(int i = 4; i < maxn; i++) a[i] = (a[i-1]+a[i-3])%mod;
    int T; scanf("%d", &T);
    while(T--) {
        int n, l, r;
        scanf("%d%d%d", &n, &l, &r);
        if(l > r) swap(l, r);
        if(l != 1) l++;
        if(r != n) r--;
        printf("%lld\n", a[r-l+1]);
    }

    return 0;
}

注

因为今天一直在听dls的直播，尽管后面的题听不懂，想听听dls一般解题思路是啥(其实后面听不懂就容易发呆了),所以今天还没有补很多题，然后就只写了这么一点点,我好弱啊

每天一句叨叨

人总得有个目标，才能继续勇敢而坚强地活着，大部分成年人，在三十岁左右已经没了活着的目标，为了不让自己死去，他们制造了一个孩子，有了这个小孩，他们终于找到了努力工作和继续活下去的目标。

不，不是的，那是基因的谎言…让你这个机器人帮忙传递他们的存在

但如果你知道这是谎言，并决定真的要选择它，那才是真正的选择

教育本来就是不平等的，有些人很年轻就是OI金牌了，然而有些人还在发愁下次要怎么骗外公外婆我出去玩了，其实是偷偷跑去了网吧，如饥似渴地享受那几个小时的奥比岛，赛尔号，功夫派，洛克王国，地下城与勇士，英雄联盟…(从小学到高中渐渐变化的是游戏),然而别人早就享受到了算法的美妙，并将来很大程度能因此受到更好的教育，然后享受社会上最好的资源，过上幸福的生活，虽然我不能这样定义幸福，但是不平等确实存在，想要跨越社会阶层的鸿沟，可能要花上很久很久的努力.不过，我认为，跨越社会阶层的鸿沟，才是这个和平时代个人最英雄的挑战.做你自己的英雄，不断超越自己，并同时珍爱身边的人，过好这一生…

今天说的好像有点小多，叨叨叨多了，快滚去运动洗澡睡觉，明天继续来补题