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