首页 > 其他分享 >杂题总结 Vol.4

杂题总结 Vol.4

时间:2024-09-26 15:34:12浏览次数:9  
标签:总结 端点 收集 Vol.4 USACO24JAN text 药水 杂题 HD

杂题总结 Vol.4

试题总结 2

Status: OPEN

\(\def\EZ{\textcolor{#51af44}{\text{EZ}}}\EZ\) 表示简单,10分钟内就能想到。
\(\def\HD{\textcolor{#3173b3}{\text{HD}}}\HD\) 表示中等,能独立想出
\(\def\IN{\textcolor{#be2d23}{\text{IN}}}\IN\) 表示困难,独立思考能想到 \(50\%\) 以上
\(\def\AT{\textcolor{#383838}{\text{AT}}}\AT\) 表示非常困难,独立思考只能想出 \(50\%\) 以下

USACO24JAN [2024-09-26]

P10134 [USACO24JAN] Cowmpetency S

\(\HD\)

细节较多的贪心题。但是仍然是一道非常不错的题目。


考虑要发现如下性质:以下“区间”均指代 \([a_i,h_i]\)

  1. 若有互相包含的区间则不存在

  2. 若有互相相交(可以共端点)则不合法。特别地,右端点是同一个值的情况是不算的。

  3. 对于右端点是同一个值的情况,保留最大的一个不影响答案

考虑采用反悔贪心,将右端点重复的区间去重之后按照左端点排序。考虑我们需要限制一个前缀的最大值的最小值,我们发现:

  • 对于 \([a_i,h_i]\) 若 \(a_i\) 前面没有可以调整的数(i.e. \(\forall j\le a_i,c_j\neq 0\)),则无解

  • 否则如果 \(\max_{j\in[1,a_i]}<\max_{j\in(a_i,h_i)}c_j\) 只需要将最后一个 \(0\) 的下界以 \(\max_{j\in(a_i,h_i)}c_j\) 更新,记该下界为 \(req_j\)

然后你就会发现你 WA 了。。

重新观察以上步骤,如果之前已经限制过 \(c_i\ge req_i\),那么这个限制值也要考虑在内,若当前扫描到第 \(i\) 个区间,记 \(s=\max_{j\in[1,a_i]}req_j\),则当 \(\max\{s,\max_{j\in[1,a_i]}\}<\max_{j\in(a_i,h_i)}c_j\) 才将上一个 \(0\)(位置记作 \(x\) )的 \(req_x\) 值以 \(\max_{j\in(a_i,h_i)}c_j\) 更新,然后令 \(s\leftarrow \max\{s,req_x\}\)。

P10135 [USACO24JAN] Potion Farming S

\(\EZ\)


考虑有贪心结论:

  1. 最小遍历次数为叶子数量。

  2. 最优药水数量可以这样构造:从下往上收集药水,优先消耗子树中叶子数量收集更深的药水。

考虑原因。由于越深的药水 \(y\) 就越少有叶子能够收集他,而若有药水 \(x\) 是 \(y\) 的祖先,那么显然能够收集 \(y\) 的叶子必然能够收集到 \(x\),如果最优方案是放弃 \(y\) 而收集 \(x\),那么用能够收集 \(y\) 的叶子改为收集 \(y\) 必然不劣,因为这样其他更浅的叶子就有了利用的机会。

P10136 [USACO24JAN] Cowlendar S

\(\HD^{+}\)

缺了一步,想到做差和枚举因数,但是没想到抽屉原理。


有一个巧妙的想法,那就是如果我们考察两个数的差值,那么应该把原序列能够分成三组,每一组当中两两的差都是可能的 \(L\) 的倍数。

但是,难蚌的是,你不可能枚举哪两个是可能的同余的数。

由于取模形成了一个有限的空间,我们常常要考虑抽屉原理。如果有四个不相同的数,那么在合法的方案下,一定有两个数是同余的,那么我们只需要尝试 \(6\) 个可能的差值然后用试除法枚举因数, \(\mathcal O(n)\) 检验即可。

其实难点主要在于第一步转化

P10137 [USACO24JAN] Walking in Manhattan G

\(\HD\)

有一个观察是:实际上奶牛遇到奇数长度的边的时候就会转向。

另一个观察是:奇数边都是一排一排一列一列出现的。

那么我们可以对每一个询问采用倍增。

标签:总结,端点,收集,Vol.4,USACO24JAN,text,药水,杂题,HD
From: https://www.cnblogs.com/haozexu/p/18433542

相关文章

  • 吴恩达-深度学习-课后作业-答案与总结
    deeplearning-assignment吴恩达-深度学习-课后作业-答案与总结作业只上传了ipynb文件,ipynb文件会持续更新,其它附件如预训练模型等由于太多太大,存放于网盘中执行ipynb文件所需附件下载地址,链接:百度网盘-链接不存在 密码:66gd吴恩达深度学习视频地址:进入 http://study.163......
  • PHP判断访客是否手机端(移动端浏览器)访问的方法总结
    方法一:使用$_SERVER全局变量我们可以使用PHP中的$_SERVER全局变量来获取访问者的User-Agent头部信息,进而判断是否为移动端设备。User-Agent头部信息包含了访问者的浏览器和操作系统信息,在移动设备的User-Agent中会包含”Mobile”的关键字,所以如果检测到User-Agent中包含”Mobile”......
  • JAVA语法基础总结
    packagecom.chunchuner.fourcompute;importjava.util.Random;publicclassArithmatics{privatestaticRandomrandom=newRandom();privatefinalstaticintCOUNT=30;privatestaticbooleangetProject(){intnum1=random.nextInt(101);intnum......
  • 06 常用内置模块总结
    -其他需背会len获取长度openrange随机生成数id是比较内存地址is/==是进行比较type获取数据类型输入输出printinput强制转换dict()list()tuple()int()str()bool()set()数学相关abs,绝对值v=abs(-1)print(v)float,转换成浮点型(小数)v=55v1=......
  • 9.25日总结
    单向链表单向链表是最基本的一种链表形式。每个节点包含一个数据元素和一个指向下一个节点的指针。单向链表的优点在于实现简单,插入和删除操作方便。缺点是只能从头节点开始遍历整个链表,访问效率较低。双向链表双向链表在单向链表的基础上增加了前驱节点指针,使得可以从任意......
  • 进制数知识(2)—— 浮点数在内存中的存储 和 易混淆的二进制知识总结
    目录1.浮点数在内存中的存储1.1浮点数的大V表示法1.2浮点数的存储格式1.3 浮点数的存入规则1.4 浮点数的读取规则1.5补充:移码与掩码1.6 题目解析2. 易错的二进制知识2.0 符号位到底会不会参与运算?2.0.1存储前的编码变化运算2.0.2存储后的数值算术运算2......
  • 06 深浅拷贝 总结
    浅拷贝:只拷贝第一层。深拷贝:拷贝嵌套层次中的所有可变类型。特殊情况#------特殊情况"""v1=(1,2,3,4)importcopyv2=copy.copy(v1)#地址不变print(id(v1),id(v2))v3=copy.deepcopy(v1)#地址不变print(id(v1),id(v3))""""""v1=(1,2......
  • 25博世机械结构面试最常见面试问题总结 校园招聘机械面试最全攻略综合面试
    开头附上工作招聘面试必备问题噢~~包括综合面试题、无领导小组面试题资源文件免费!全文3000+干货。【免费】25博世机械面试问题总结博世面试经验分享面试全攻略面试最常见问题资源-CSDN文库https://download.csdn.net/download/m0_72216164/89797247?spm=1001.2014.3001.5503......
  • 25歌尔机械结构面试最常见面试问题总结 校园招聘机械面试最全攻略综合面试
    歌尔机械面试经验开头附上工作招聘面试必备问题噢~~包括综合面试题、无领导小组面试题资源文件免费!【免费】25歌尔机械面试问题总结机械工程师提前批面试经验心得必备题目和答案资源-CSDN文库https://download.csdn.net/download/m0_72216164/89797209?spm=1001.2014.3001.55......
  • 12 列表总结
    1、增:append/insert2、删:remove/pop/clear/delusers[2]3、改:users[3]="新值"4、查:索引/切片5、列表嵌套users=["alex",0,True,[11,22,33,"老男孩"],[1,['alex','oldboy'],2,3]]users[0]users[2]users[0][2......