CF1408 H. Rainbow Triples

2023-10-10 06:10
文章标签 rainbow cf1408 triples

本文主要是介绍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 ansm=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),(i1,i)(iL),(i,i+1)(iR).
    那么跑出的最大流即为最大匹配.由于最大流=最小割.(直接跑网络流复杂度较大)
    我们从割边的角度考虑加速求解.
    割边一定为某些权值,前缀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 xlxk,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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/178501

相关文章

Codeforces Round #368 (Div. 2)(C. Pythagorean Triples 勾股数规律)

题目链接 给出一个数,输出2个数,使得这三个数是勾股数 形如2n,n^2-1,n^2+1可以组合成勾股数,这是偶数的情况 奇数的时候看个例子 3, 4 , 5 | 4 = (1+3) * 1 5,12,13 | 12 = (1+5)*2 7,24,25 | 24 = (1+7)*3 9,40,41 | 40 = (1+9)*4 … 第二列数就是第一列数在以3为首项的等差数列中的位

产品推荐 | 基于 Zynq UltraScale+ RFSoC 的iW-RainboW-G42M 核心板

01 产品概述 Xilinx Zynq UltraScale+基于RFSoC的系统模块采用带有FFVF1760封装的Zynq Scale+RFSoC ZU49/ZU39/ZU29设备。RFSoC支持高达1.3GHz的Quad Cortex A53和高达533MHz的Dual Cortex R5F。SOM支持高达16通道的射频ADC@2.5Gsps和16通道的RF DAC@10Gsps,所有这些都

Codeforces Problem 707C Pythagorean Triples(数学)

此文章可以使用目录功能哟↑(点击上方[+]) 比赛链接→Codeforces Round #368 (Div. 2)  Codeforces Problem 707C Pythagorean Triples Accept: 0    Submit: 0 Time Limit: 1 second    Memory Limit : 256 megabytes  Proble

[CodeForces-707C] Pythagorean Triples【构造right三角形】

题意: 给出一个整形范围内的数n,判断是不是可以作为一个直角三角形的边,直角边斜边都可以. 另外,必须保证另外两条边是整数。 思路: 对于相邻平方差,我们可以得到{1, 3, 5, 7, ...}这样一个奇数数列。 1 = 1^2 - 0^2 3 = 2^2 - 1^2 5 = 3^2 - 2^2 …… 由此可以得出,一个奇数n,有: 勾股定理大家一定知道!再接下来,我们考虑

HCIE-Rainbow迁移工具

Rainbow迁移工具 Rainbow迁移工具支持p2v(物理机到虚拟机的迁移) v2v(虚拟机到虚拟机的迁移) Rainbow业务上云迁移: Rainbow迁移到公有云(利用公有云SMS服务,付费) Rainbow迁移到公有云(利用本地的rainbow服务,免费) Rainbow迁移到私有云 Rainbow迁移到FusionCompute Rainbow的2种迁移方式: 1、文件级迁移:li

Rainbow迁移

华为Rainbow迁移知识点整理: Rainbow的交付流程: 迁移到方式:文件级迁移和块级迁移。 Rainbow Rainbow是华为在线迁移工具,可以将其他第三方VM或物理机,迁移到华为的FusionSphere平台。只支持X86架构的,windows、linux的VM或物理机。 物理图: Rainbow包含了两种:1.OVFconvert。2.Hconvert。 OVFconver

Rainbow的商店

Rainbow的商店 总时间限制:  1000ms 内存限制:  262144kB 描述 Rainbow开了一家商店,在一次进货中获得了N个商品。 已知每个商品的利润和过期时间。 Rainbow每天只能卖一个商品,并且过期商品不能再卖。 Rainbow也可以选择在每天出售哪个商品,并且一定可以卖出。 由于这些限制,Rainbow需要制定一份合理的售卖计划。请你计算一下,Rain

Rainbow开发 step2

Rainbow的web SDK 是一个纯净的Angular JavaScript库,可以工作在多种浏览器下,包括IE11、Chrome、Firefox、Safari和Edge。它可以使你更好的建立Angular的应用去连接Rainbow 云服务。 首先先通过npm先把Rainbow的web SDK安装到你本地 $ npm install rainbow-web-sdk --save 在该

强化学习Rainbow复现

复现代码: https://github.com/Curt-Park/rainbow-is-all-you-need 同复现DQN代码一样,在Jupyter notebook上运行 —————————————————————————————————————————— 因为没有认真看原文件,导致走弯路。 如果第一次运行强化学习代码,估计需要导入gymnasium (这个我在前面复现DQN时已导入过

Python 彩虹色映射【cm.rainbow()方法】(Matplotlib篇-10)

Python 彩虹色映射【cm.rainbow()方法】(Matplotlib篇-10)         🍹博主 侯小啾 感谢您的支持与信赖。☀️ 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ   ✨本博客收录于专栏Python