P10784 【MX-J1-T4】『FLA - III』Wrestle题目背景原题链接https://oier.team/problems/J1D。在 2022 年末疫情将西北某不知名知名学校的大多数学生关在家中上网课安同学还不知道他和语文老师的对决已然悄无声息地开始了——他每天早读和语文课都直接睡过去了。安同学习惯起来穿好衣服、面对摄像头睡觉摄像头只能拍到他的半个肩膀就算被强制打开也不会暴露他在睡觉的事实而且从来没有老师强制打开他的摄像头。而这个不凡的早晨语文老师打开了他的摄像头现在是早读时间他在朦胧中被老师的关爱声叫醒可惜为时已晚老师已经愤怒。安同学决定假装网络卡顿平复老师愤怒的心情。老师愤怒了在安同学醒来后的某些时间段她要呼叫他的真名其余时间等他应答。与此同时安同学要打造网卡的假象他可以在某些时间段内检查设备或者呼叫老师其余时间静止或随机在画面中闪现他在这些时间段内的行为称为表演。你的任务是帮助安同学在不激怒老师的情况下最大化表演时间。因为安同学实在是太抽象了原始题面受他影响变得也很抽象这里只有形式化题面给你看。题目描述给定三个正整数n , m , k n,m,kn,m,k和两组线段。第一组线段有权值共n nn条是红色的第二组线段没有权值共m mm条是蓝色的。这些线段位于同一个数轴。使用l , r , w l,r,wl,r,w三个正整数表示一条从数轴上第l ll个整点覆盖到第r rr个整点权值为w ww的红色线段。保证数轴上任意一个整点至多被红色线段覆盖一次。使用L , R L,RL,R两个正整数表示一条从数轴上第L LL个整点覆盖到第R RR个整点没有权值的蓝色线段。保证数轴上任意一个整点至多被蓝色线段覆盖一次。如果一条红色线段从第l 0 l_0l0​个整点覆盖到第r 0 r_0r0​个整点一条蓝色线段从第L 0 L_0L0​个整点覆盖到第R 0 R_0R0​个整点且max ⁡ ( l 0 , L 0 ) ≤ min ⁡ ( r 0 , R 0 ) \max(l_0,L_0) \leq \min(r_0,R_0)max(l0​,L0​)≤min(r0​,R0​)就认为这两条线段有交集交集包含从第max ⁡ ( l 0 , L 0 ) \max(l_0,L_0)max(l0​,L0​)个整点到第min ⁡ ( r 0 , R 0 ) \min(r_0,R_0)min(r0​,R0​)个整点的全部min ⁡ ( r 0 , R 0 ) − max ⁡ ( l 0 , L 0 ) 1 \min(r_0,R_0)-\max(l_0,L_0)1min(r0​,R0​)−max(l0​,L0​)1个整点。你可以选择一些蓝色线段一种合法的选择方案必须符合以下条件题目给定的每条红色线段至多与你选择的1 11条蓝色线段有交集。所有和你选择的蓝色线段有交集的红色线段权值之和不超过k kk。选择方案合法时你选择的蓝色线段和所有红色线段的交集至多能包含多少个整点输入格式第一行输入三个正整数n , m , k n,m,kn,m,k。接下来n nn行第i ii行输入三个正整数l i , r i , w i l_i,r_i,w_ili​,ri​,wi​表示一条红色线段。接下来m mm行第i ii行输入两个正整数L i , R i L_i,R_iLi​,Ri​表示一条蓝色线段。保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。输出格式输出一行一个整数表示答案。输入输出样例 #1输入 #12 3 23 7 18 7 63 71 2 77 86 13 19 63 71输出 #115输入输出样例 #2输入 #24 5 7 59 65 7 39 42 1 43 51 2 19 33 2 14 25 71 81 6 11 59 69 83 92输出 #27输入输出样例 #3输入 #34 8 45 80 94 22 60 67 2 35 44 45 7 14 5 82 86 2 3 58 63 48 50 73 80 25 45 11 19 93 94输出 #313说明/提示「样例解释 #1」如图选择输入的第2 22条蓝色线段和第3 33条蓝色线段。第2 22条蓝色线段与第1 11条红色线段有交交集包含从第13 1313个整点到第18 1818个整点的所有整点第3 33条蓝色线段与第2 22条红色线段有交交集包含从第63 6363个整点到第71 7171个整点的所有整点。第1 11条红色线段仅与第2 22条蓝色线段有交第2 22条红色线段仅与第3 33条蓝色线段有交和被选择的蓝色线段有交的红色线段权值和为9 99方案合法。故答案为15 1515。「数据范围」本题采用捆绑测试。Subtaskn ≤ n \leqn≤m ≤ m \leqm≤k ≤ k \leqk≤l i , r i , L i , R i ≤ l_i,r_i,L_i,R_i \leqli​,ri​,Li​,Ri​≤分值#110 101010 101050 5050100 10010020 2020#2200 200200200 200200200 20020010 5 10^510530 3030#35000 500050005000 500050005000 5000500010 9 10^910930 3030#42 × 10 5 2 \times 10^52×1055000 500050005000 5000500010 9 10^910920 2020对于100 % 100\%100%的数据1 ≤ n ≤ 2 × 10 5 1 \leq n \leq 2 \times 10^51≤n≤2×1051 ≤ m , k ≤ 5000 1 \leq m,k \leq 50001≤m,k≤50001 ≤ l i , r i , L i , R i ≤ 10 9 1 \leq l_i,r_i,L_i,R_i \leq 10^91≤li​,ri​,Li​,Ri​≤1091 ≤ w i ≤ k 1 \leq w_i \leq k1≤wi​≤kl i r i l_i r_ili​ri​L i R i L_i R_iLi​Ri​。保证数轴上任意一个整点至多被红色线段覆盖一次。保证数轴上任意一个整点至多被蓝色线段覆盖一次。C实现#includebits/stdc.husingnamespacestd;structSegment{intl,r,v;longlongw;}a[200005],b[5005];intn,m,k,ans,cnt,ri[5005],pre[5005],sumv[200005],p[400005],dp[5005][5005];longlongsumw[200005];boolcmp(constSegmentx,constSegmenty){returnx.ly.l;}intmain(){cinnmk;for(inti1;in;i)cina[i].la[i].ra[i].w;for(inti1;im;i)cinb[i].lb[i].r;sort(a1,an1,cmp),sort(b1,bm1,cmp);for(inti1;in;i){a[i].va[i].r-a[i].l1;sumw[i]sumw[i-1]a[i].w;sumv[i]sumv[i-1]a[i].v;p[i*2-1]a[i].l,p[i*2]a[i].r;}for(inti1;im;i){if(b[i].la[n].r||b[i].ra[1].l)continue;intllower_bound(p1,pn*21,b[i].l)-p;intrupper_bound(p1,pn*21,b[i].r)-p-1;if(l%21p[l]b[i].r||r%20p[r]b[i].l)continue;l(l1)/2,r(r1)/2,ri[i]r;for(intj1;ji-1;j)if(ri[j]l)pre[i]j;b[i].wsumw[r]-sumw[l-1];if(l!r){b[i].vsumv[r]-sumv[l-1]-a[r].v-a[l].v;b[i].vmin(b[i].r,a[l].r)-max(b[i].l,a[l].l)1;b[i].vmin(b[i].r,a[r].r)-max(b[i].l,a[r].l)1;}elseb[i].vmin(b[i].r,a[l].r)-max(b[i].l,a[l].l)1;}for(inti1;im;i){for(intj1;jk;j)dp[i][j]dp[i-1][j];for(intjk;jb[i].w;j--){dp[i][j]max(dp[i][j],dp[pre[i]][j-b[i].w]b[i].v);ansmax(ans,dp[i][j]);}}coutans\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容