感觉这次 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;
}
标签:sz,1714,int,CF,flag,ans,pair,new
From: https://www.cnblogs.com/AProblemSolver/p/16736166.html