D. Ezzat and Grid
题目大意
给定一个\(n\times 10^9\)的01矩阵，要求去掉最少行，使得相邻两行有至少一列都是\(1\)。
输出去掉的最小行数和一种可行的去掉行的方案。
矩阵以给出每行\(1\)对应的列的形式给出。
解题思路
简单\(DP\)。
设\(dp[i]\)表示前\(i\)行，保留第\(i\)行，满足题目要求的去掉最小的行数。
则\(dp[i] = \min(dp[j] + i - j - 1)\)，其中第\(i\)行和第\(j\)行至少有一列都是\(1\)。
为方便期间，变换形式为\(dp[i] - i = \min(dp[j] - j) - 1\)容易猜测这个j是小于i的满足条件最大的
问题就在于如何维护可行的\(j\)。
换个角度，我们不考虑哪些\(j\)可行，而是考虑哪些\(j\)的某一列是\(1\)。
如果第\(i\)行的第\(k\)列为\(1\)，那么我们就在前面的行里，找到第\(k\)列同样为\(1\)的行，取他们的最大值。
维护辅助数组\(a[i]\)表示第\(i\)列为\(1\)的行的\(\min(dp[k] - k)\)
那么对于第\(i\)的某个连续的\(1\)区间\(l,r\)，我们就只要查询\(a[l..r]\)的最小值。
然后再将\(dp[i] - i\)的值更新到\(a\)数组即可。
区间赋值和区间查询，用线段树维护\(a\)数组。
需要先离散化列。
至于输出方案，记录转移的前继节点即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <typename T>
void read(T &x) {
int s = 0, c = getchar();
x = 0;
while (isspace(c)) c = getchar();
if (c == 45) s = 1, c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (s) x = -x;
}
template <typename T, typename... rest>
void read(T &x, rest&... Rest) {
read(x);
read(Rest...);
}
template <typename T>
void write(T x, char c = ‘ ‘) {
int b[40], l = 0;
if (x < 0) putchar(45), x = -x;
while (x > 0) b[l++] = x % 10, x /= 10;
if (!l) putchar(48);
while (l) putchar(b[--l] | 48);
putchar(c);
}
const int N = 3e5 + 8;
class Segment{
#define lson root << 1
#define rson root << 1 | 1
pair<int,int> minn[N << 3];
pair<int,int> lazy[N << 3];
public:
void pushdown(int root){
if (lazy[root] == make_pair(0, 0))
return;
minn[lson] = minn[rson] = lazy[lson] = lazy[rson] = lazy[root];
lazy[root] = {0, 0};
}
void update(int root, int l, int r, int ll, int rr, pair<int,int> val){
if (ll <= l && r <= rr){
minn[root] = val;
lazy[root] = val;
return;
}
pushdown(root);
int mid = (l + r) >> 1;
if (ll <= mid)
update(lson, l, mid, ll, rr, val);
if (rr > mid)
update(rson, mid + 1, r, ll, rr, val);
minn[root] = min(minn[lson], minn[rson]);
}
pair<int,int> query(int root, int l, int r, int ll, int rr){
if (ll <= l && r <= rr)
return minn[root];
pushdown(root);
int mid = (l + r) >> 1;
if (rr <= mid)
return query(lson, l, mid, ll, rr);
else if (ll > mid)
return query(rson, mid + 1, r, ll, rr);
else
return min(query(lson, l, mid, ll, rr), query(rson, mid + 1, r, ll, rr));
}
}Seg;
int n, m;
vector<pair<int,int>> s[N];
map<int, int> rr;
int pre[N];
set<int> ss;
int main(void) {
read(n, m);
for(int a, l, r, i = 1; i <= m; ++ i){
read(a, l, r);
ss.insert(l);
ss.insert(r);
s[a].push_back({l, r});
}
int cnt = 1;
for(auto i : ss)
rr[i] = cnt++;
int tot = ss.size();
int ou = 1e9 + 7;
int en = 0;
for(int i = 1; i <= n; ++ i){
int ans = -1;
for(auto &j : s[i]){
pair<int,int> re = Seg.query(1, 1, tot, rr[j.first], rr[j.second]);
if (ans > re.first - 1){
ans = re.first - 1;
pre[i] = re.second;
}
}
for(auto &j : s[i]){
Seg.update(1, 1, tot, rr[j.first], rr[j.second], {ans, i});
}
if (ans + n < ou){
en = i;
ou = ans + n;
}
}
write(ou, ‘\n‘);
for(int i = n; i >= en + 1; -- i)
write(i);
for(int i = en; i != 0; i = pre[i]){
for(int j = i - 1; j > pre[i]; -- j)
write(j);
}
return 0;
}