R7-07-21 题目总览

我要困死了我要睡觉我要睡觉我是た【数据删除】の

我太菜了，爆爆爆。估分 100/400，实际 75/400。把我给【数据删除】了算了。

顺便说一下，有些时候，我真的觉得这个 md to pdf 转换器的母亲有点【数据删除】。

汉字全部给我转成康熙部首了，我还搞个啥？？？

T1 study.cpp

TL：1s，ML：512MB

题目大意

在⾼⼀的第⼆个学期的个星期的时间内，有⻔课，编号为。每个星期有个课时，第个课时上课程的⼀节课。

萧瑞希是⼀位⾼⼀学⽣。对于个课时中的每⼀个，他会选择如下⾏动中的⼀个：

⾏动 1 ：萧瑞希去上课。如果他去上了课程的⼀节课，那么他对课程的理解程度会增加。
⾏动 2 ：萧瑞希不去上课。他转⽽选择任意⼀⻔课，并且⾃学选中的那⻔课。如果他选中了课程进⾏了时⻓为⼀课时的⾃学，那么他对课程的理解程度会增加。

⼀开始，对每⻔课的理解程度都为。由于萧瑞希想要在课后练习算法竞赛，他在⾮上课时间内不会学习。当第三个学期的所有课时结束后，期末考就会举⾏。萧瑞希不想挂科。所以他想要最⼤化在期末考时对每⻔课的理解程度的最⼩值。

给定学期的⻓度，课程的数量，以及对理解程度的提升数值，请写⼀个程序计算在期末考时对每⻔课的理解程度的最⼩值的最⼤可能值。

解答

二分答案，对于当前答案，先让他每一课时选中最大的那个，让他全上完。令现在每一课时的熟练度为。然后看一共多了多少节有效课时，即。然后再拿这些课时来补的课程就做完了。这道题很坑的一点就在于他会爆 long long，把我最后的希望都磨没了。

T2 exam.cpp

TL：1s，ML：512MB

题目大意

华⼆信息组学⽣们集思⼴益，想出了种题⽬，第种题⽬中有个变量，其中只有个跟其答案有关的关键变量。每种题⽬都有个版本可⽤，版本之间只有变量取值的区别，所以它们的和都是完全⼀样的。于是题库⾥现在有道题。

⼀位组题经验的同学提出，题⽬之间可以强⾏缝合：将任意两道题⽬缝合后，会得到⼀道新的题⽬，其变量数为原来的两题的变量数之和，其关键变量数为原来的两题的关键变量数之和。（注意，是任意两道题⽬都可以缝合，包括同⼀种题⽬的不同版本，以及缝合得到的题⽬都可以⽤于缝合。）缝合之后原来的两个题会消失，新的题加⼊题库。最终的试卷将从题库中选择⼀些题⽬产⽣。

对于⼀道题⽬，其爽度定义为其关键变量数除以其变量数的值。有两个整数序列与。通过调研，同学们对⼀道题⽬的评判标准如下：如果⼀道题的爽度，那么它的开⼼度为其变量数乘以。可以证明对于任意⼀道题⽬存在恰好⼀个满⾜要求。

根据试卷规范，⼀场模拟赛的总变量数不能超过个。组题⼈想知道，在任意次缝合操作后，选出题库中若⼲道题⽬作为联测，所有题⽬开⼼度的最⼤总和。

解答

相当于是我们要在这道题里面选出一些题，然后这些题的总变量数不能超过个，并且要让他们组合之后开心度最大。我们把看成重量，看作收益，就相当于是一个多重背包了。但是状态该怎么设呢？

因为题目里面说，即按照爽度增加而增加。那么我们肯定要追求说，你想选总重量为的一些物品，要让它们缝合起来的开心度最大，那肯定要让它们的和最大嘛。所以我们可以跑一个多重背包，设为考虑物品，选取总重为的一些物品所可以获得的最大和。这个跑一遍多重背包可实现。但是时间有点过于了，怎么优化？

可以发现因为总变量数不能超过个，所以这个【个版本】其实什么用没有，都可以看作是无限个版本。所以可以把原题的多重背包改为无限背包。也就是每一个物品可以选无数次，然后跑，这样的复杂度就是了。同时，的维度也可以被压下来。

并且发现这个性质后后面也好做了。对于每一个，都有属于它的最大的。我们也可以将的所有和也可以看作是容量为的无限背包。依然跑一下无限背包即可。对于所对应的可以使用法来求得这个分数是百分之几，进而求得属于哪一个（这个可以预处理），然后就好转移了。

T3 team.cpp

TL：2s，ML：1024MB

题目大意

Yuna 有个⼩伙伴，她决定从中选出个⼩伙伴组成⼀个队伍帮她打游戏。每个⼩伙伴的游戏⻆⾊有三项能⼒值：攻击⼒、防御⼒、魔⼒。能⼒值越⾼说明该能⼒越强。

⼀个队伍的总能⼒定义为：三⼈中攻击⼒最强的⼈的攻击⼒值、三⼈中防御⼒最强的⼈的防御⼒值、三⼈中魔⼒最强的⼈的魔⼒值之和。此外，为了使分⼯明确，Yuna 希望她选出的队伍满⾜每个成员都有⾃⼰的特⻓，即：每个成员都有⼀项能⼒值严格⼤于其他两⼈的对应能⼒值。

在所有符合条件的组队中，Yuna 想要选⼀个总能⼒最强的队伍，请你帮她计算出最⼤的总能⼒值。若不存在符合条件的队伍，输出 -1。

。

解答

如果一个人它在团队里属于：含有项值在团队里排最大，那么这个人就不能被选，也就是要将这个人删除。一轮之后继续检测。将所有这种人删除之后，剩下的人的就是答案。这个比较容易证明，难点在实现。

这里我开了三个 priority_queue，分别存目前的最大值以及它们的下标。然后就分别检查每一个最大值的下标是否在其他的领域里面也是目前最大值。如果是，那么就在检测完了之后将其删除。我这里删除的方法就是先给 vis 数组打标记，然后再给需要删除的 priority_queue pop 了。然后检测下一个是否已经 vis 了，是的话继续 pop 直到不是或者已经为空了为止。

当当前最大的三个值的下标都不违法的话，那么这三个值加起来就是答案。如果删掉之后只剩下个元素了或者 priority_queue 空了就输出。

T4 memory.cpp

TL：2s，ML：512MB

题目大意

你需要维护个可重集合，初始为空，有种操作：

操作 1：区间的集合中都插⼊。
操作 2：设为区间的集合的并集中最⼤的数，则对于所有，若集合中存在数，集合中删除恰好⼀个。
操作 3：设为区间的集合的并集中最⼤的数，查询，若并集为空输出。

。

解答

可以使用线段树维护。对于线段树上每一个节点维护一个堆。每一个堆相当于是一个标记永久化了的 lazytag。并且每一个节点维护一个代表线段树上它的子树的值的最大值。操作 1 暴力插入，操作 3 暴力查询。

对于操作 2 的话，就可以先找到那个最大值，然后：

先把这所有个区间找到。如果在路上就有堆头为的，处理那个堆头即可。并且如果或者，记得要把的部分给插入进去。然后 return。
找到之后，再对它们进行递归。如果当前点有堆头为的，一样处理。一样 return。
否则如果左儿子里面有，即，那么就继续递归左子树。右子树同理。

势能分析一下就可以得出时间复杂度。

总结

T2 没拿到分有一部分原因是题读错了导致没有往背包那方面去想，但更大的原因还是对背包问题的不熟悉。

T3 没有对原题进行认真分析导致那个性质没有被发现。

T4 则是当时想出来了与线段树有关，但是没有对线段树做法进行更深的考虑，以及后面对于势能的分析。

并且有些时候……