把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。
题目大意：
CF1624E Masha-forgetful
题目大意：给你n个长度为m的字符串（n*m不超过1e6），然后再给你一个串，问你能否将整个串表示为长度大于1的子串相加，其中这些子串一定要在前面的串中出现过，求每个子串的来源位置，输入任意即可。
解：
看似是很恐怖的字符串题目，实际上我们可以发现，对于每一个子串，它都可以分解为长度为2或3的子串相加，因此我们记录n个字符串中的子串的时候只需要记录长度为2和3的子串，在这里我直接用map来存哈希，map的value值用结构体（数字也行，然后再映射），表示这个子串出现的位置。
接下来就是遍历目标串来判定哪些是2哪些是3，这个时候就要用过到dp啦。
状态还是很好想的，dp[i]表示以i结尾的串是否合理，状态转移为dp[i]=dp[i-k]&&fk，记得在转移的同时记录下来转移的来源，最后倒推回去求得每个子串的来源位置。
题目给了三秒，我最后是702ms过的，内存消耗也不多，仔细想想，虽然有1e6的数据范围，但是长度为2和3的字母组成的串其实一共也没多少个吧（26^2+26^3），所以空间完全不用担心。
这题的dp含量其实很小了，毕竟不需要求最小的子串数量（要求的话这题就完全是另一道题了），哈希的建立也非常简单明显，考了一个记录路径但无足轻重，个人感觉不配2000分（）
代码
代码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
|
#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>
#define ll long long
#define maxn 200005
#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);
using namespace std;
struct ck {
int start, end, num;
};
map< string, ck> has;
map<string, int> exi;
stack<ck> ans;
int dp[1001];
int main()
{
cfast;
int t;
cin >> t;
while (t--) {
int n, m;
cin >> n >> m;
has.clear();
exi.clear();
for (int i = 0; i <= m; i++)dp[i] = -1;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
for (int j = 0; j < m-1; j++) {
string tmp = "";
tmp += s[j];
tmp+=s[j + 1];
ck c1 = { j + 1,j + 2,i };
has[tmp] = c1;
exi[tmp] = 1;
if (j < m-2) {
tmp += s[j + 2];
c1.end = j + 3;
has[tmp] = c1;
exi[tmp] = 1;
}
}
}
string a;
cin >> a;
if (m == 1) {
cout << "-1" << endl;
continue;
}
int f = 0;
int flag = 0;
dp[0]=-1;
for (int j = 2; j <= m; j++) {
string tmp = "";
tmp += a[j - 2];
tmp += a[j-1];
if (exi[tmp] == 1&&(dp[j-2]!=-1||j-2==0)) {
dp[j] = j - 2;
}
if (j > 2) {
tmp = "";
tmp += a[j - 3];
tmp += a[j - 2];
tmp += a[j-1];
if (exi[tmp] == 1 && (dp[j - 3] != -1 || j - 3 == 0)) {
dp[j] = j - 3;
}
}
}
int now = m;
int num = 0;
if (dp[m] == -1) {
cout << "-1" << endl;
continue;
}
while (now>0) {
num++;
int tar = dp[now];
string tmp = "";
for (int i = tar + 1; i <= now; i++)tmp += a[i-1];
ans.push(has[tmp]);
now = tar;
}
cout << num << endl;
while (!ans.empty()) {
ck c = ans.top();
printf("%d %d %d\n", c.start, c.end, c.num);
ans.pop();
}
}
}
|
Copyright Notice: 此文章版权归EmiteInna所有，多看看吧。
