韩国网页设计网站/深圳seo优化公司

题目：Problem - E - Codeforceshttps://codeforces.com/contest/1624/problem/E

题意：

玛莎认识了一个新朋友，并知道了他的电话号码 s  。电话号码是一个长度为m的字符串，它由从 0-9 组成 。

电话号码可能以 0 开头。 玛莎已经知道 n 个电话号码(所有号码都有相同的长度 m )。对她来说，用她已经知道的数字片段来表示，记住一个新号码会更容易。每个数字片段长度至少为 2 ，否则分段太多，玛莎会搞混。

例如，玛莎需要记住数字: s = ‘12345678’ ，并且她已经知道 n = 4 ，号码:' 12340219 '，' 20215601 '，' 56782022 '，' 12300678 '。你可以将 s 分为一个 3 段:一号的“1234”，二号的“56”，三号的“78”。

还有其他方法来表示 s 。 玛莎请你帮忙，她请你将 s 分成长度至少为2的多个段或者更多她已经知道的数字。如果有几个可能的答案，打印其中任何一个。

Input：

测试用例有t组  1<= t <=10^4 

有n个号码，长度为m 1 ≤n,m ≤10^3

输入n个号码，而后输入 s

Output：

若无答案则输出-1。反之输出你答案的长度，并且输出其L，R 和 I 。分别表示在第I个号码的L到R

input：
24 8
12340219
20215601
56782022
12300678
123456782 3
134
126
123output：
3
1 4 1
5 6 2
3 4 3
-1

思路：

数字片段的长度至少为2，说明所有的数字片段可以分解为长度为2或3，长度为4=两个长度为2相加。所以预处理先遍历出2、3长度的数字片段及其相关信息并且将其保存到map里。

通过f[]保存状态，先预处理，f[2]表示s[2]之前的信息，即f[2]=s[0,1]，f[3]=s[0,1,2]。将f[1]={0,0,0}表示无效信息。

而后进行遍历，若 f[i-2] 且 mp[s.substr(i - 2, 2)] 是有效的，则 f[i]=mp[s.substr(i - 2, 2)]（f[i-2]表示s[i-2]之前的信息。 mp[s.substr(i - 2, 2)]则表示s[i-2,i-1]）。f[i-3]同理进行判断。若都不满足则设置为无效信息。

如果最后的f[m]是存在有效信息则表示该结果有解，用vector逆序保存信息。否则输出-1。

代码：

#include<iostream>
#include<bits/stdc++.h>
using namespace std;struct point {//保存输出信息int x, y, n;
};
map<string, point>mp;
vector<point>ans;
point f[1010];
bool checked(point p) {//判断是否合法。if (p.x == 0 && p.y == 0 && p.n == 0) {return 0;}return 1;
}int main() {int t;cin >> t;while (t--) {mp.clear();string s, subs;int n, m;cin >> n >> m;for (int i = 1;i <= n;i++) {//预处理保存片段cin >> s;for (int j = 0;j < m - 1;j++) {subs = s.substr(j, 2);mp[subs] = { j + 1,j + 2,i };}for (int j = 0;j < m - 2;j++) {subs = s.substr(j, 3);mp[subs] = { j + 1,j + 3,i };}}ans.clear();cin >> s;f[1] = mp[""];//{0,0,0}if (m >= 2)f[2] = mp[s.substr(0, 2)];if (m >= 3)f[3] = mp[s.substr(0, 3)];for (int i = 4;i <= m;i++) {if (checked(f[i - 2]) && checked(mp[s.substr(i - 2, 2)])) {f[i] = mp[s.substr(i - 2, 2)];}else if (checked(f[i - 3]) && checked(mp[s.substr(i - 3, 3)])) {f[i] = mp[s.substr(i - 3, 3)];}else {f[i] = f[1];}}//for (int i = 1;i <= m;i++) cout << 'f' << i << " == " << f[i].x << " " << f[i].y << " " << f[i].n << " " << endl;if (checked(f[m])) {int pos = m;while (pos != 0) {ans.push_back(f[pos]);pos -= f[pos].y - f[pos].x + 1;}cout << ans.size() << endl;for (int i = ans.size() - 1;i >= 0;i--) {cout << ans[i].x << " " << ans[i].y << " " << ans[i].n << endl;}}else {cout << -1 << endl;}}
}