Contents

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

  • 今天是杭电多校第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项有两种情况,要么是直接往上走要么是闪电 https://cdn.jsdelivr.net/gh/wolfdan666/BlogPic/%E7%AE%97%E6%B3%95/2019%E5%B9%B4%E5%A4%9A%E6%A0%A1/%E6%9D%AD%E7%94%B5/%E7%AC%AC%E4%BA%94%E5%9C%BA/1007_an.png

法二

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

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