传送门
思路
感觉自己越来越笨了……首先，很明显这道题需要把没有看到忍者的区间给删去，可以用前缀和
O(n)
O
(
n
)
处理，然后对没有删去的地方重新标号。重新标号时，需要对发现忍者的区间的左右端点也重新标号，用二分就好了，比较简单（细节留给你们思考）。
然后我发现，如果一个区间最后只能覆盖一个位置，那么这个区间是必选的。然后我就什么也看不出来了……
正解
这道题最重要的一点是如何理解某个位置必须存在一个忍者，我们来想一想除了位于一个长度为
1
1
的区间的情况，为什么某个地方必须存在一个忍者。
由于题目没有限制，我们可以随便放忍者，只要满足所有区间都有至少一个忍者被覆盖到就好了。这很自然地让我们联想到点覆盖线段的问题，自然也就想到了用最少的点覆盖所有线段的问题。
由于保证至少有一个合法解，那么我们可以知道：覆盖所有线段的最小点数一定小于等于 k，否则问题一定无解。如果有剩下的，那就随便放即可。
注意到，既然剩下的是随便放，那么它们一定不在最后的答案中。换句话说，最后的答案一定是各区间的右端点，且它在贪心求最小点数时被选中了（如果没有被选，那这个点已经是不能一定选的了）。
那么我们考虑，为什么一个区间的右端点必须选中。正面考虑显然已经无路可走（选都选了，怎么判断必须选？），我们考虑当不选这个右端点时会发生什么。如果一定不选这个右端点，我们仍然可以在
O(n)
O
(
n
)
的时间复杂度内求出覆盖所有线段的最小点数，只需要在选这个区间时改成选择右端点左边那个点就可以了，但是这时总点数就可能会变大。我们自然就会想到：如果总点数变得超过
k
k
，就说明不选这个点将会产生矛盾，所以这个点必须选。
于是我们立即得到了一个时间复杂度为 O(n2) 的算法。另外，我们发现我们全程都在求最小线段覆盖点数，所以包含了其它线段的线段就没有用了，因为被包含的线段被覆盖就意味着包含的线段也会被覆盖，因此剩下的线段如果按照左端点从小到大排序，它们的右端点也一定是递增的。具体操作用单调栈即可。
我们考虑优化这个算法。思考这个过程究竟做了什么，我们发现，我们在从左往右决策时前面一定不变，到了规定不能选的右端点后我们一定会选择右端点左边那个点，也就是说，我们知道是知道前面是选了多少个点的。考虑暴力计算时我们后面是怎么算的，我们一定会选择第一个不能被最后一个选的点覆盖的线段的右端点，然后依次覆盖剩下的所有线段。我们可以预处理出覆盖后面所有线段的最小点数（从后往前贪心即可），在计算答案时二分查找第一个不能被覆盖的区间，就能在
O(logn)
O
(
log
n
)
的时间复杂度内计算不选某个位置时的最小点数了。细节留给你们思考。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
putchar('\n');
}
const int maxn = int(1e5) + 5;
int n, m, k;
struct Area
{
int l, r;
Area() {}
Area(int l, int r) :l(l), r(r) {}
};
int newIdx[maxn];
std::vector<Area> areas;
int ans[maxn];
void solve1()
{
for (int i = 1; i <= n; i++)
{
bool bOk = false;
int pre = -1;
int cnt = 0;
for (int j = 0; j < areas.size(); j++)
{
if (areas[j].l == i && areas[j].r == i)
{
bOk = true;
break;
}
if (areas[j].l <= pre) continue;
cnt++;
if (areas[j].r == i)
pre = areas[j].r - 1;
else
pre = areas[j].r;
}
if (bOk || cnt > k) ans[++ans[0]] = i;
}
}
int f[maxn];
int left[maxn];
void solve2()
{
for (int i = 0; i < areas.size(); i++)
left[i] = areas[i].l;
int pre, cnt;
pre = n + 1;
cnt = 0;
for (int i = areas.size() - 1; ~i; i--)
{
if (pre > areas[i].r)
{
pre = areas[i].l;
cnt++;
}
f[i] = cnt;
}
pre = -1;
cnt = 0;
for (int i = 0; i < areas.size(); i++)
{
const Area& a = areas[i];
if (pre < a.l)
{
if (a.l == a.r)
ans[++ans[0]] = a.l;
else
{
int R = std::upper_bound(left, left + m, a.r - 1) - left;
if (cnt + 1 + f[R] > k)
ans[++ans[0]] = a.r;
}
pre = a.r;
cnt++;
}
}
}
int del[maxn];
void run()
{
n = readIn();
k = readIn();
m = readIn();
std::vector<Area> temp;
for (int i = 1; i <= m; i++)
{
int l = readIn();
int r = readIn();
int c = readIn();
if (!c)
{
del[l]++;
del[r + 1]--;
}
else
{
temp.push_back(Area(l, r));
}
}
for (int i = 2; i <= n; i++)
del[i] += del[i - 1];
for (int i = 1; i <= n; i++)
if (!del[i])
newIdx[++newIdx[0]] = i;
for (int i = 0; i < temp.size(); i++)
{
Area& a = temp[i];
a.l = std::lower_bound(newIdx + 1, newIdx + 1 + newIdx[0], a.l) - newIdx;
a.r = std::upper_bound(newIdx + 1, newIdx + 1 + newIdx[0], a.r) - newIdx - 1;
if (a.l <= a.r)
areas.push_back(a);
}
temp = areas;
areas.clear();
std::sort(temp.begin(), temp.end(),
[](const Area& a, const Area& b)
{
if (a.l != b.l) return a.l < b.l;
return a.r > b.r;
});
for (int i = 0; i < temp.size(); i++)
{
const Area& a = temp[i];
while (areas.size() && areas.back().r >= a.r)
areas.pop_back();
areas.push_back(a);
}
n = newIdx[0];
m = areas.size();
if (k == n)
{
for (int i = 1; i <= n; i++)
printOut(newIdx[i]);
return;
}
solve2();
if (ans[0])
for (int i = 1; i <= ans[0]; i++)
printOut(newIdx[ans[i]]);
else
printOut(-1);
}
int main()
{
run();
return 0;
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
