Codeforces1624E. Masha-forgetful

传送门

题目大意

给出 \(n+1\) 个长度为 \(m(1\leq n,m\leq1000,\sum nm\leq10^6)\) 的由数字 \(0\sim9\) 组成的串，求能否把最后一个串分成若干个长度 \(\geq2\) 的段，使得它们都在前 \(n\) 个串中出现过，未出现过输出 \(-1\) 否则按顺序输出所分割的段数，每一段输出 \(l,r,i\) 表示该段在第 \(i\) 段中 \([l,r]\) 处出现。

思路

考虑到所有长度 \(\ge2\) 的段都能够由长度为 \(2\) 和 \(3\) 的段组成，所以只用考虑这些长度的段即可。然后我们可以记录一下有哪些长度为 \(2\) 和 \(3\) 的字串在前 \(n\) 个串中出现过并记录一个它们出现的位置。之后我们在最后一个串上进行 \(dp\) ，设 \(dp[i]\) 为是否能够拼接出前 \(i\) 个字符组成的串，之后很容易进行转移，复杂度 \(O(nm)\) 。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
typedef pair PLL;
typedef tuple TP;
#define all(x) x.begin(),x.end()
//#define int LL
#define lc p*2
#define rc p*2+1
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 1000010;

int T, N, M;
string A[maxn], S;
bool dp[maxn];

void solve()
{
	TP vis2[10][10], vis3[10][10][10];
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (j + 1 < M)
				vis2[A[i][j] - '0'][A[i][j + 1] - '0'] = { j + 1,j + 2,i };
			if (j + 2 < M)
				vis3[A[i][j] - '0'][A[i][j + 1] - '0'][A[i][j + 2] - '0'] = { j + 1,j + 3,i };
		}
	}
	dp[0] = true;
	for (int i = 0; i <= M; i++)
	{
		if (dp[i])
		{
			if (i + 2 <= M)
				dp[i + 2] |= (vis2[S[i] - '0'][S[i + 1] - '0'] != TP(0, 0, 0));
			if (i + 3 <= M)
				dp[i + 3] |= (vis3[S[i] - '0'][S[i + 1] - '0'][S[i + 2] - '0'] != TP(0, 0, 0));
		}
	}
	if (!dp[M])
		cout << -1 << endl;
	else
	{
		vectorans;
		int i = M, cnt = 0;
		while (i)
		{
			if (dp[i - 2])
			{
				ans.push_back(vis2[S[i - 2] - '0'][S[i - 1] - '0']);
				i -= 2;
			}
			else
			{
				ans.push_back(vis3[S[i - 3] - '0'][S[i - 2] - '0'][S[i - 1] - '0']);
				i -= 3;
			}
			cnt++;
		}
		cout << cnt << endl;
		reverse(all(ans));
		for (auto& c : ans)
			cout << get<0>(c) << ' ' << get<1>(c) << ' ' << get<2>(c) << endl;
	}
}

int main()
{
	IOS;
	cin >> T;
	while (T--)
	{
		cin >> N >> M;
		for (int i = 0; i <= M; i++)
			dp[i] = false;
		for (int i = 1; i <= N; i++)
			cin >> A[i];
		cin >> S;
		solve();
	}

	return 0;
}