P10845 [EGOI 2024] Bouquet / 花束制作题目背景Day 1 Problem B.题面译自 EGOI2024 bouquet。翻译来自于 ChatGPT 并进行人工校对若有误请联系 rui_er。题目描述参观了世界上最大的花园之一库肯霍夫后Lieke 非常喜欢花因此她决定收集一些路边生长的郁金香来制作一个漂亮的花束。然而在收集花朵时她必须遵守荷兰严格的郁金香保护法的一些规定。沿着道路从左到右有N NN株郁金香编号从0 00到N − 1 N - 1N−1。郁金香保护法为郁金香i ii分配了两个整数l i l_ili​和r i r_iri​。如果郁金香i ii被包含在花束中则郁金香i ii左边紧邻的l i l_ili​株郁金香和右边紧邻的r i r_iri​株郁金香不能包含在花束中。注意如果郁金香i ii左边的郁金香少于l i l_ili​株或者右边的郁金香少于r i r_iri​株那么该侧所有的郁金香仍然不能包含在花束中允许溢出。Lieke 想知道如果她最佳地选择花朵最多能摘取多少株郁金香。帮她找到这个问题的答案制作一个漂亮的花束吧输入格式输入的第一行包含一个整数N NN表示沿路生长的郁金香数量。接下来的N NN行描述了郁金香保护法的信息第i ii行包含两个整数l i l_ili​和r i r_iri​表示郁金香i ii的保护限制。输出格式输出一个整数表示 Lieke 在遵守保护法的情况下可以摘取的最大郁金香数量。输入输出样例 #1输入 #13 0 3 1 0 1 0输出 #11输入输出样例 #2输入 #25 0 3 1 0 0 1 2 0 1 0输出 #23输入输出样例 #3输入 #37 0 0 0 0 1 0 1 0 2 0 3 0 2 0输出 #34输入输出样例 #4输入 #46 2 2 2 2 2 2 2 2 2 2 2 2输出 #42输入输出样例 #5输入 #57 0 2 2 0 1 1 2 2 0 0 0 1 0 1输出 #53说明/提示样例解释在第一个样例中如果 Lieke 摘取郁金香0 00她不能摘取右边的两朵郁金香。摘取郁金香1 11并不禁止她摘取郁金香2 22但郁金香2 22禁止她摘取郁金香1 11因此她不能同时摘取它们。所以Lieke 可以摘取的最大花朵数量是1 11。在第二个样例中Lieke 可以摘取的郁金香数量最多是3 33获得此结果的方式如图所示。其他摘取郁金香的方式会导致更小的答案。在第三个样例中通过摘取郁金香0 , 1 , 3 0, 1, 30,1,3和6 66可以获得最多的4 44朵郁金香。数据范围对于全部数据1 ≤ N ≤ 2 × 10 5 1\le N\le 2\times 10^51≤N≤2×1050 ≤ l i , r i ≤ N 0\le l_i,r_i\le N0≤li​,ri​≤N。子任务一8 88分对于任意( i , j ) (i,j)(i,j)l i r i l j r j l_ir_il_jr_jli​ri​lj​rj​。子任务二16 1616分r i 0 r_i0ri​0。子任务三28 2828分N ≤ 1000 N\le 1000N≤1000。子任务四18 1818分l i , r i ≤ 2 l_i,r_i\le 2li​,ri​≤2。子任务五30 3030分无特殊限制。注部分测试点在 EGOI 中被放在多个子任务中。为节省评测资源及整理数据的工作量这些测试点被放在包含它的所有子任务中编号最小的一个。这可能导致一份代码得到比预期更高的分数但是无法过题。C实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN200010;intn,l[N],r[N],tr[N],f[N],ans;vectorintupd[N];intlowbit(inti){returni-i;}voidupdate(intx,intk){for(intix;in;ilowbit(i))tr[i]max(tr[i],k);}intquery(intx){intres0;for(intix;i0;i-lowbit(i))resmax(res,tr[i]);returnres;}intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);cinn;for(inti1;in;i)cinl[i]r[i];for(inti1;in;i){if(i-1l[i])f[i]1;elsef[i]query(i-l[i]-1)1;ansmax(ans,f[i]);upd[min(n,ir[i])].push_back(i);for(intj:upd[i])update(j,f[j]);}coutans\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容