CF 1714 D

感觉这次 D 比 F 还难……

题面

传送门走起！

思路

原先我的贪心写挂了。
我只考虑了开头，没考虑结尾。
事实证明结尾才是最重要的！

本题数据非常小。
从开头起，贪心的选择染哪个部分。
$ r \leftarrow -1 $， $ r $ 代表染完的下标。（-1 只是开始）
每次我们从下标 $ 0 \to r + 1 $ 里选择开头，贪心的选择结尾最后面的。
把 $ r $ 更新上去，就完成了一次染色。

结束是什么时候呢？
$ r + 1 \geq \text{size} (t) $

代码

有点凌乱。

#include <bits/stdc++.h>
using namespace std;

pair<string, int> s[15];
vector<pair<int, int> > ans;

int main() {
	int q;
	cin >> q;
	while (q--) {
		ans.clear();
		string t;
		cin >> t;
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> s[i].first;
			s[i].second = i;
		}
		sort(s, s + n);
		int r = -1;
		bool flag;
		while (r + 1 < t.size()) {
			flag = 0;
			pair<string, int> ths;
			int new_r = -1, new_i = -1;
			for (int i = r + 1; i >= 0; i--) {
				for (int sz = 10; sz >= r - i + 2; sz--) {
					pair<string, int> use = *lower_bound(s, s + n, make_pair(t.substr(i, sz), -1));
					if (use != *upper_bound(s, s + n, make_pair(t.substr(i, sz), 0x3f3f3f3f))) {
						if (i + sz - 1 > new_r) {
							ths = use;
							new_r = i + sz - 1;
							new_i = i;
							flag = 1;
							break;
						}
					}
				}
			}
			ans.emplace_back(ths.second + 1, new_i + 1);
			r = new_r;
			if (!flag) {
				puts("-1");
				break;
			}
		}
		if (flag) {
			printf("%d\n", ans.size());
			for (auto i : ans) {
				printf("%d %d\n", i.first, i.second);
			}
		}
	}
	return 0;
}