把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。
题目大意：
CF 1538E Funny Substrings
题目大意：对于一个变量有两种操作：赋值和加算合并（顾名思义），现在有n次操作(不超过50，但t<=1e3，且每个t中n都可以为50，虽然没什么影响吧)，要求完成所有操作后最后一个被操作的变量代表的字符串中有多少个“haha”，注意赋值操作中赋值的字符串最大长度不超过5。
解：
显然如果直接去模拟的话最后这个字符串可能被扩展到2^50的长度，是模拟所无法接受的，所以我们只能对于现有的变量去进行简单直接的计算。
如果有两个变量a,b，他们本身包含的haha数分别是numa，numb，那么合并之后的haha数量应该是numa+numb+合并产生的haha，那么我只要知道两个变量合并之后产生了多少个haha就能直接完成计算。
如何计算呢？Haha的产生一定是通过加算时左边的字符串的结尾和右边的字符串的开头来决定的，而且最多涉及三位，那么对于每个变量，我可以实时地去记录其前三位和后三位，由于原字符串长度只有5，所以对于特殊情况（字符串本身长度小于3）可以直接枚举长度去求解，注意在合并时处理两个变量合并后变量的前三位和后三位时有一定的细节。
剩下就是无脑的模拟了，常数虽然有点大但是复杂度完全不虚。
比较有意思的题，但是很简单，什么时候我也能做这么简单的E呢？不过话说回来，果然跳过D去直接开E才是最需要勇气的吧（虽然这场的D也很简单，简单到我都没写题解……）。
代码
代码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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 500005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
map<string, string> head, tail;
map<string, ll> cnt;
int main() {
cfast;
int t;
cin >> t;
while (t--) {
head.clear();
tail.clear();
cnt.clear();
int n;
cin >> n;
string var, cmd,last;
while (n--) {
cin >> var >> cmd;
last = var;
if (cmd[0] == ':') {
string str;
cin >> str;
cnt[var] = 0;
if (str.length() == 1) {
tail[var] = " " + str;
head[var] = str + " ";
}
else if (str.length() == 2) {
tail[var] = " " + str;
head[var] = str + " ";
}
else if (str.length() == 3) {
tail[var] = str;
head[var] = str;
}
else if (str.length() == 4) {
if (str == "haha")cnt[var] = 1;
head[var] = "";
inc(i, 0, 3)head[var] += str[i];
tail[var] = "";
inc(i, 1, 4)tail[var] += str[i];
}
else {
for (int i = 0; i < 2; i++) {
if (str[i] == 'h') {
if (str[i + 1] == 'a' && str[i + 2] == 'h' && str[i + 3] == 'a')cnt[var] = 1;
}
}
head[var] = "";
inc(i, 0, 3)head[var] += str[i];
tail[var] = "";
inc(i, 2, 5)tail[var] += str[i];
}
}
else {
string a, b, pls;
cin >> a >> pls >> b;
cnt[var] = cnt[a] + cnt[b];
if (tail[a] == "hah" && head[b][0] == 'a')cnt[var]++;
if (tail[a][1] == 'h' && tail[a][2] == 'a' && head[b][0] == 'h' && head[b][1] == 'a')cnt[var]++;
if (tail[a][2] == 'h' && head[b] == "aha")cnt[var]++;
head[var] = head[a];
if (head[var][1] == ' ') {
if (head[b][0] != ' ') {
head[var][1] = head[b][0];
if (head[var][2] == ' ' && head[b][1] != ' ')
head[var][2] = head[b][1];
}
}
else if (head[var][2] == ' ' && head[b][0] != ' ') {
head[var][2] = head[b][0];
}
tail[var] = tail[b];
if (tail[var][1] == ' ') {
if (tail[a][2] != ' ') {
tail[var][1] = tail[a][2];
if (tail[var][0] == ' ' && tail[a][1] != ' ')
tail[var][0] = tail[a][1];
}
}
else if (tail[var][0] == ' ' && tail[a][2] != ' ') {
tail[var][0] = tail[a][2];
}
}
}
cout << cnt[last] << endl;
}
}
|
Copyright Notice: 此文章版权归EmiteInna所有，多看看吧。
