首页 > 其他分享 >「NOIP 模拟赛 20230705」T2-序列删数问题 题解

「NOIP 模拟赛 20230705」T2-序列删数问题 题解

时间:2023-07-05 19:35:44浏览次数:53  
标签:20230705 NOIP 删除 题解 魔法 删数 序列

题面

Natsuzora 有一个长度为 \(n\) 的排列 \(a_1,a_2,\ldots,a_n\),他想要将序列中的 \(m\) 个数删除。删除数字需要使用到“魔法工具”,其也有 \(m\) 种,其中第 \(i\) 种魔法工具能够将排列中任意一个的长度为 \(l_i\) 的区间中最大的数删除。每个魔法工具最多只能使用 \(1\) 次。每次删除操作后,序列的长度将减少 \(1\),且删去的数的右边所有数的下标减少 \(1\)。判断是否可以删去所有的 \(m\) 个数。

题解

标签:20230705,NOIP,删除,题解,魔法,删数,序列
From: https://www.cnblogs.com/qzhwlzy/p/17529606.html

相关文章

  • 洛谷P9025题解
    P9025题解简化题意求一个值\(c\)使得\[\sum_{i=1}^nw_i(\left|c-p_i\right|-d_i)\]最小化(注意题目中\(w_i\)表示每移动一米需要\(w_i\)秒)思路首先我们令选择\(c\)位置的总用时为\(f(c)\)显然,我们可以把它分成两边来看在\(c\)左边的人:\[f(c)=\sum_{p_i+d_......
  • 题解:【AT icpc2015summer day2-G】 Escape
    题目链接目前AT的最优解。树的话就是根叶链的最大点权和路径,DP随便搞。考虑扩展到图上,反复删除掉所有度数为\(1\)的节点,显然剩下的东西是可以全部取完的,因为它的形态类似于菊花套环,且末端必定为环。将这部分缩起来再跑上面的DP就好了。事实上两部分可以同时进行,一个bfs......
  • 成语积累 20230705
    焚膏继晷:焚:点燃;膏:灯油或蜡烛;继:接续;晷:日影或日光。意思是点燃灯烛来接替日光照明。形容夜以继日的用功读书或努力工作。例句:~,兀兀穷年。鹤唳华亭:表示思念,怀旧之意。亦为慨叹仕途险恶,人生无常之词。例句:但~,贵何似贱;珠沉金谷,富不如贫。拾人牙慧:牙慧:牙齿内剔出的余食。比喻拾取别人......
  • Springboot No bean named 'XXXXX' available 问题解决
    一、问题描述近日在工作中遇见了一个bug,后端程序频频报错Nobeannamed'XXXXX'available。对比同类程序文件,没有发现有任何特殊之处。在网上搜索方法基本上就是扫描包配置、注解问题、路径问题等,皆不能解决我的问题。排查问题是发现出现问题的类命名不符合驼峰规范,按照这个......
  • B0704 模拟赛题解
    原题链接前言挂分最多的一场。考虑到之前都无分可挂,这场算是最近很简单的了。T1不排序(按理说我的做法不需要排,但挂了),100->40。T2二分某个边界时单调性判错,100->30。T3原,但没做过。T4某人用模拟退火骗到60ptsorz。T1棍子签到题。考虑二分答案。显然每次要切的......
  • SPOJ Substrings 题解
    \(\text{SAM}\)入门好题。首先我们需要知道几个关于\(\text{SAM}\)的结论。结论1:题目中的\(f(x)\)单调下降。显然,对于长度为\(x\)的子串,其必存在一个\(x-1\)的后缀,这个后缀的\(\text{endpos}\)集合肯定包含子串的\(\text{endpos}\)集合,所以必有\(f(x-1)\le......
  • [NOIP2012 普及组] 寻宝
    思路:模拟必须mod20123,不然就有可能会爆掉!AC代码#include<iostream>#defineintlonglongusingnamespacestd;boolwhether[10001][101];ints[10001][101],T[10001];signedmain(){ intn,m,S,w,ans=0; cin>>n>>m; for(inti=0;i<n;i++) { for(intj=......
  • Hydro #4766. 文艺计算姬 题解--zhengjun
    link前置知识:Prufer序列,二分图别的题解都是直接给答案,没有比较易懂的思路。首先,考虑Prufer序列,发现右边点删除一定会加入一个左边点,另一边类似。且生成Prufer序列的最后一定会留下左右边各一个点。所以左边点在Prufer序列中出现的次数即为\(m-1\),右边即为\(n-1\)。......
  • 【Maven】Unknown lifecycle phase “.test.skip=true“.问题解决
    我们在运行跳过单元测试时的命令mvnpackage-Dmaven.test.skip=true时,出现Unknownlifecyclephase".test.skip=true".如下[ERROR]Unknownlifecyclephase".test.skip=true".Youmustspecifyavalidlifecyclephaseoragoalintheformat<plugin-prefix>......
  • PAT乙级【Java题解合集】
    ✨说在前面       这个暑假博主用大概两周不到的闲暇时间把PAT乙级的110道算法题全部肝完了,个人感觉题目的难度大部分在中等偏下,大概有二十道左右的题目还是蛮有意思的,值得细细去钻研,本专栏非常适合新手入门算法,也适合Java算法老手巩固一些基本知识点,由于C站上关于PAT乙级J......