合肥网站建设网页设计,网站入口设计,海北网站建设,wangye最近的题都只会抄题解#x1f605;
首先#xff0c;操作顺序会影响答案#xff0c;因此不能直接贪心。其次#xff0c;因为是求贡献最大#xff0c;所以可以考虑枚举最终哪些位置对答案产生了贡献#xff0c;进而转化为全局贡献。 1.1 1.1 1.1 如果 [ l 1 , r 1 ) ⊆ [ …最近的题都只会抄题解
首先操作顺序会影响答案因此不能直接贪心。其次因为是求贡献最大所以可以考虑枚举最终哪些位置对答案产生了贡献进而转化为全局贡献。 1.1 1.1 1.1 如果 [ l 1 , r 1 ) ⊆ [ l 2 , r 2 ) [l_1,r_1)\subseteq [l_2,r_2) [l1,r1)⊆[l2,r2)那么一定是贪心的先操作 [ l r , r 2 ) [l_r,r_2) [lr,r2)因此这部分限制不用考虑 1.2 1.2 1.2 对于两个区间 [ l 1 , r 1 ) , [ l 2 , r 2 ) [l_1,r_1),[l_2,r_2) [l1,r1),[l2,r2)如果满足 l 1 l 2 r 1 r 2 l1l2r_1r_2 l1l2r1r2并且选择了 r 1 r_1 r1那么意味着 l 2 l_2 l2一定比 r 1 r_1 r1先操作反之亦然因此 l 2 l_2 l2和 r 1 r_1 r1不能同时被选择。注意到 l i , r i l_i,r_i li,ri互不相同因此我们考虑到了所有位置并且每个位置至少有一次产生贡献的机会。
容易证明这样不会产生环因为 r r r是递增的
发现只有 l i l_i li和 r i r_i ri之间会有连边问题转化为求二分图最大独立集。
使用 bitset \text{bitset} bitset优化复杂度 O ( n 3 w ) O(\frac{n^3}{w}) O(wn3)。
类似的题目[ARC092F] Two Faced Edges
#includebits/stdc.h
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
const int N5005;
int n,tot,l[N],r[N],match[N];
int px[N],py[N];
bitsetNto[N],vs;
queueintQ;
int bfs(int u){while(Q.size())Q.pop();vs.set(),Q.push(u);int v-1;while(Q.size()){int xQ.front();Q.pop();bitsetNtmpvsto[x];for(int ytmp._Find_first();yn;ytmp._Find_next(y)){int zmatch[y];vs[y]0;if(z0){match[y]x,vx;break;}Q.push(z),px[z]x,py[z]y;}if(~v)break;}if(v-1)return 0;while(v!u){match[py[v]]px[v];vpx[v];}return 1;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cinn;for(int i1;in;i){cinl[i]r[i];}for(int i1;in;i){for(int j1;jn;j){if(l[i]l[j]l[j]r[i]r[i]r[j]){to[i][j]1;}}}for(int i1;in;i){totbfs(i);}cout2*n-tot;
}
