信誉好的常州网站建设,泉州网站建设设计,期货融网站建设,网站开发背景怎么写很优美的解法。 推荐大佬博客 如果没有保证字典序最小这一个要求#xff0c;这题就是一个水题了#xff0c;但是要保证字典序最小#xff0c;然后我就不会了…… 如果一条线段能放入一个区间$[l, r]$并且不影响最优答案#xff0c;那么对于这条线段$[l, r]$#xff0c;设$…很优美的解法。 推荐大佬博客 如果没有保证字典序最小这一个要求这题就是一个水题了但是要保证字典序最小然后我就不会了…… 如果一条线段能放入一个区间$[l, r]$并且不影响最优答案那么对于这条线段$[l, r]$设$solve(l, r)$表示$[l, r]$这个区间里面最多能放多少条线段一定要有条件$solve(l, l - 1) solve(r 1, r) 1 solve(l, r)$。 那么贪心的时候顺便考虑一下怎么检验的问题就可以了如果暴力检验是$O(n)$的考虑优化利用一下倍增思想我们设$f_{i, j}$表示从$i$开始选择$2^{j}$条线段所能到达的最靠左的右端点那么在离散化之后就可以用$O(nlogn)$的时间预处理出$f$数组这样子每一次检验求$solve$的时间是$O(logn)$的具体怎么处理可以参照下面的代码。 考虑一下最后怎么进行的贪心对于每一条线段我们检验一下是不是能放这个检验的过程可以用很多数据结构做到$O(logn)$如果能放入我们就找出之前放过的最前的右端点和最后的左端点然后chk一下上面的条件是否成立就可以了。 感觉这个过程写个线段树更直观一点还是学习了一下上面那位大佬高能的树状数组写法。 时间复杂度$O(nlogn)$。 Code #include cstdio
#include cstring
#include algorithm
using namespace std;const int N 2e5 5;
const int Lg 20;
const int inf 1 30;int n, tot 0, maxn 0;
int l[N], r[N], f[N 1][Lg];
int ans[N], lmax[N 1], rmax[N 1], lsum[N 1], rsum[N 1];struct Innum {int val, id;
} in[N 1];bool cmpIn(const Innum x, const Innum y) {if(x.val ! y.val) return x.val y.val;else return x.id y.id;
}inline void read(int X) {X 0; char ch 0; int op 1;for(; ch 9|| ch 0; ch getchar())if(ch -) op -1;for(; ch 0 ch 9; ch getchar())X (X 3) (X 1) ch - 48;X * op;
}inline int max(int x, int y) {return x y ? x : y;
}inline int min(int x, int y) {return x y ? y : x;
}inline void chkMax(int x, int y) {if(y x) x y;
}inline void discrete() {sort(in 1, in 1 tot, cmpIn);for(int cnt 0, i 1; i tot; i) {if(in[i].val ! in[i - 1].val) cnt;maxn max(maxn, cnt);if(in[i].id n) r[in[i].id - n] cnt;else l[in[i].id] cnt;}
}#define lowbit(x) ((x) (-x))inline void aSum(int *now, int x) {for(; x maxn; x lowbit(x))now[x];
}inline int qSum(int *now, int x) {int res 0;for(; x 0; x - lowbit(x))res now[x];return res;
}inline void aMax(int *now, int x) {for(int t x; x maxn; x lowbit(x))chkMax(now[x], t);
}inline int qMax(int *now, int x) {int res 0;for(; x 0; x - lowbit(x))chkMax(res, now[x]);return res;
}inline int solve(int ln, int rn) {int res 0;for(int i 18; i 0; i--)if(f[ln][i] rn) res (1 i), ln f[ln][i] 1;return res;
}int main() {read(n);for(int i 1; i n; i) {read(l[i]), read(r[i]);in[tot] (Innum) {l[i], i};in[tot] (Innum) {r[i], i n};}discrete();memset(f, 0x7f, sizeof(f));for(int i 1; i n; i)f[l[i]][0] min(f[l[i]][0], r[i]);for(int i maxn; i 1; i--) {f[i][0] min(f[i][0], f[i 1][0]);for(int j 1; f[i][j - 1] maxn (1 j) n; j)f[i][j] f[f[i][j - 1] 1][j - 1];} /* for(int i 1; i maxn; i)printf(%d , f[i][0]);printf(\n); *//* for(int i 1; i n; i)printf(%d %d\n, l[i], r[i]);printf(\n); */tot 0;for(int i 1; i n; i) {int v tot - qSum(rsum, l[i] - 1) - qSum(lsum, maxn - r[i]);if(v 0) continue;int lst qMax(rmax, l[i] - 1), nxt maxn - qMax(lmax, maxn - r[i]);if(solve(lst 1, l[i] - 1) solve(r[i] 1, nxt) 1 solve(lst 1, nxt)) {ans[tot] i;aSum(rsum, r[i]), aSum(lsum, maxn - l[i] 1);aMax(rmax, r[i]), aMax(lmax, maxn - l[i] 1);}// printf(%d , v);}
// printf(\n);
printf(%d\n, tot);for(int i 1; i tot; i)printf(%d , ans[i]);printf(\n);return 0;
} View Code转载于:https://www.cnblogs.com/CzxingcHen/p/9553116.html
