本文主要是介绍CF1408 H. Rainbow Triples,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
做法1
参考BLOG
引理:
- 设 z e r o zero zero为0的个数.则 a n s ≤ m = z e r o 2 ans\le m=\dfrac {zero} 2 ans≤m=2zero.
- 我们把下标划分成两个集合 L , R L,R L,R,其中 L L L集合内的元素左边的0的个数 ≤ m \le m ≤m.
原问题等价于每一个非0数如果成功和两边的0配对,那么答案+1
.
那么对于弱化版问题: L L L匹配位置左边的0, R R R匹配位置右边的0.(一个非0数只能和一个0配对)
如果配对数量 > m >m >m,那么答案一定可以为 m m m.
构造方法:把配对数量删剩下 m m m个.那么 L L L的右边接上一个 R R R中未选择的0, R R R的左边接上 L L L未选择的0即可.
类似地,我们对于配对数量 ≤ m \le m ≤m的情况,也可以构造出来.
所以 a n s = min ( m a t c h e s , m ) ans=\min(matches,m) ans=min(matches,m). - 由上,我们可以发现 L L L集合内的数受限于左边0的个数, R R R类似.
所以我们可以对每个数 x x x取 L L L中最右的位置, R R R中最左的位置,下面表示为 ( l x , r x ) (l_x,r_x) (lx,rx).
可以建出一个网络流图:
连边为( S S S,权值 x x x), ( x , l x ) , ( x , r x ) , ( i − 1 , i ) ( i ∈ L ) , ( i , i + 1 ) ( i ∈ R ) (x,l_x),(x,r_x),(i-1,i)(i\in L),(i,i+1)(i\in R) (x,lx),(x,rx),(i−1,i)(i∈L),(i,i+1)(i∈R).
那么跑出的最大流即为最大匹配.由于最大流=最小割.(直接跑网络流复杂度较大)
我们从割边的角度考虑加速求解.
割边一定为某些权值,前缀0,后缀0.
所以我们只要对于每个前缀0计算一下每个后缀0的最少割边即可.
具体地,我们一开始割去所有的权值边.
然后,设当前缀删去 i i i个0,那么某些权值 x . . . x... x...就不能取左边 l x l_x lx进行配对,只能流向 r x r_x rx.
这个时候,对于删去了 r x r_x rx后面的0的情况,那么 x x x这个权值就没有必要割了,所以就进行一次区间-1
操作.
特别的,对于 l x = 0 , r x > 0 l_x=0,r_x>0 lx=0,rx>0的( x x x不在 L L L中出现) x x x,我们一开始就执行区间-1
.
int n, a[N], vis[N], L[N], R[N], zero, cnt, ans, m, pre[N], nxt[N], type[N];int mn[N << 1], tag[N << 1];
#define lson lc, l, mid
#define rson rc, mid + 1, r
#define pushup(x) cmin(mn[x] = mn[lc], mn[rc])
void bt(int x, int l, int r) {tag[x] = 0;if (l == r) {mn[x] = l + cnt;return;}int mid = (l + r) / 2;bt(lson);bt(rson);pushup(x);
}
void add(int x, int y) {mn[x] += y;tag[x] += y;
}
void pushdown(int x) {if (tag[x])add(lc, tag[x]), add(rc, tag[x]), tag[x] = 0;
}void del(int x, int l, int r, int L, int R) {if (L <= l && r <= R)return add(x, -1);int mid = (l + r) / 2;pushdown(x);if (L <= mid)del(lson, L, R);if (mid < R)del(rson, L, R);pushup(x);
}void solve() {qr(n);nxt[n + 1] = 0;rep(i, 1, n) qr(a[i]), L[i] = R[i] = vis[i] = 0;rep(i, 1, n) pre[i] = pre[i - 1] + !a[i];REP(i, 1, n) nxt[i] = nxt[i + 1] + !a[i];zero = pre[n] / 2;ans = zero;rep(i, 1, n) vis[a[i]] = 1;cnt = 0;rep(i, 1, n) cnt += vis[i], type[i] = (pre[i] <= zero) ? 1 : 2;rep(i, 1, n) if (type[i] == 1) L[a[i]] = i;REP(i, 1, n) if (type[i] == 2) R[a[i]] = i;bt(1, 0, m = pre[n] - zero);rep(i, 1, n) if (!L[i] && R[i]) del(1, 0, m, nxt[R[i]], m);cmin(ans, mn[1]);rep(i, 1, n) {if (type[i] == 2)break;if (a[i] && L[a[i]] == i) {del(1, 0, m, nxt[R[a[i]]], m);cmin(ans, pre[i] + mn[1]);}}pr2(ans);
}
做法2
参考自官方题解.
每个权值 x x x,可以抽象成一个数对 ( l x , r x ) (l_x,r_x ) (lx,rx).
且只能配对 < l x o r > r x <l_x ~or~>r_x <lx or >rx的位置.
这类图还有一个性质,存在一个阈值 k k k满足 ∀ x l x ≤ k , r x > k \forall_x l_x\le k,r_x>k ∀xlx≤k,rx>k.
这类图有贪心做法求最大匹配.
i > k i>k i>k从左到右扫描,然后对于没匹配的数对 ( l x , r x ) (l_x,r_x) (lx,rx),若满足 r x < i r_x<i rx<i,我们取 l x l_x lx最小的进行配对.
然后倒序扫描 i < k i<k i<k贪心配对.
第一部分,我们可以用一个 p r i o r i t y _ q u e u e priority\_queue priority_queue进行处理.
正确性证明:
我们定义 S S S为数对 ( l x , r x ) (l_x,r_x) (lx,rx)的集合.
定义拟阵 M = ( S , I ) M=(S,\mathcal{I}) M=(S,I),规定独立子集为所有元素都被配对.
容易证明 M M M的遗传性和交换性成立,所以 M M M是拟阵.
M M M的基的大小为所求,所以我们尽可能地加入元素即可.
选择 l x l_x lx最小的,是因为 l x l_x lx如果和前面配对的话不一定成功,而此时一定成功,所以这样做更优.
int n, a[N], ans, L[N], R[N], first[N];void solve() {qr(n);V<int> zero;ans = 0;rep(i, 1, n) {qr(a[i]);first[i] = 0;if (!a[i])zero.pb(i);}if (SZ(zero) < 2) {puts("0");return;}int z = zero[SZ(zero) / 2];rep(i, 1, z - 1) first[a[i]] = i;priority_queue<pii> q;rep(i, z, n) {if (!a[i]) {if (q.size()) {first[q.top().se] = -1;q.pop();ans++;}} else {if (first[a[i]] >= 0)q.push(mk(-first[a[i]], a[i])), first[a[i]] = -2;}}int cnt = 0;REP(i, 1, z - 1) {if (!a[i]) {if (cnt)ans++, cnt--;} else if (first[a[i]] != -1)cnt++, first[a[i]] = -1;}pr2(min(ans, SZ(zero) / 2));
}
这篇关于CF1408 H. Rainbow Triples的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!