2023牛客NOIP赛前集训营-提高组题解：填数游戏、放假回家、分糖果

"2023牛客OI赛前集训营-提高组（第三场）题解" 在本次2023年牛客NOIP赛前集训营提高组的第三场比赛中，我们关注到三道题目，分别是T1填数游戏、T2放假回家和T3分糖果。下面是对这三道题目的详细解析： 1. T1 - 填数游戏 这道题目考察的是搜索和贪心策略。10%的分数可以通过暴力搜索得到答案。30%的分数要求每个数都要填入格子，可以采取贪心策略，将大的数匹配给大的数，小的数匹配给小的数，以最大化结果。为了获得50%的分数，可以实现一个𝑂𝑂(𝑛𝑛^2)的前缀优化算法。最后的100%分数需要考虑到有些数可能不用填，可以将数分为正负两部分，先匹配负数与负数，正数与正数，剩余的数按照大小原则匹配，复杂度为𝑂𝑂(𝑁𝑁)。 2. T2 - 放假回家 这道题目的关键在于权值线段树的应用。对于初始的30%分数，可以通过重新排序或插入排序来解决。当数据规模较小（如第四、第五个数据点𝑀𝑀小于等于100）时，可以仅维护前100个数字的排序，以获取50%的分数。为了达到满分，可以利用权值线段树，每个节点存储指定区间内数字的数量及其总和，查询时判断左子树的数字和是否超过限制，根据结果决定递归方向。时间复杂度为𝑂𝑂(𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁𝑁)。 3. T3 - 分糖果 这是一道涉及二分查找、动态规划、离散化和树状数组的综合问题。对于20%的分数，只需检查是否存在前缀和小于等于𝑚𝑚𝑖𝑖𝑑𝑑的情况。对于更高分数，我们使用动态规划解决问题。定义𝑓𝑓[𝑖𝑖]表示前𝑖𝑖个数字最多可以分成多少段，每段和不超过𝑚𝑚𝑖𝑖𝑑𝑑。如果𝑓𝑓[𝑖𝑖]大于或等于𝐾𝐾，则𝑚𝑚𝑖𝑖𝑑𝑑是可行解，否则不是。转移方程为𝑓𝑓[𝑖𝑖]=𝑚𝑚𝑖𝑖𝑑𝑑(𝑓𝑓[𝑗𝑗]+1)，其中𝑆𝑆[𝑖𝑖]−𝑆𝑆[𝑗𝑗]≤𝑚𝑚𝑖𝑖𝑑𝑑，𝑆𝑆数组为前缀和数组。整体的时间复杂度为𝑂𝑂(𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙)。 通过这三道题目，参赛者可以锻炼自己的搜索技巧、贪心策略、动态规划、线段树以及二分查找等算法应用能力，这些都是在OI竞赛中非常重要的技能。通过训练，选手们能够更好地应对类似的问题，并在正式比赛中取得优异成绩。