当前位置：首页 > news >正文

打卡信奥刷题（3507）用C++实现信奥题 P10845 [EGOI 2024] Bouquet / 花束制作

news 2026/8/15 11:35:58

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

输入 #1

3 0 3 1 0 1 0

输出 #1

输入输出样例 #2

输入 #2

5 0 3 1 0 0 1 2 0 1 0

输出 #2

输入输出样例 #3

输入 #3

7 0 0 0 0 1 0 1 0 2 0 3 0 2 0

输出 #3

输入输出样例 #4

输入 #4

6 2 2 2 2 2 2 2 2 2 2 2 2

输出 #4

输入输出样例 #5

输入 #5

7 0 2 2 0 1 1 2 2 0 0 0 1 0 1

输出 #5

说明/提示

样例解释

在第一个样例中，如果 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×105，0 ≤ 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_i=r_i=l_j=r_jli=ri=lj=rj。
子任务二（16 1616分）：r i = 0 r_i=0ri=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++实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=200010;intn,l[N],r[N],tr[N],f[N],ans;vector<int>upd[N];intlowbit(inti){returni&-i;}voidupdate(intx,intk){for(inti=x;i<=n;i+=lowbit(i))tr[i]=max(tr[i],k);}intquery(intx){intres=0;for(inti=x;i>0;i-=lowbit(i))res=max(res,tr[i]);returnres;}intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);cin>>n;for(inti=1;i<=n;i++)cin>>l[i]>>r[i];for(inti=1;i<=n;i++){if(i-1<=l[i])f[i]=1;elsef[i]=query(i-l[i]-1)+1;ans=max(ans,f[i]);upd[min(n,i+r[i])].push_back(i);for(intj:upd[i])update(j,f[j]);}cout<<ans<<"\n";return0;}