- 沈阳化工大学2025东北四省赛选拔赛
沈阳化工大学2025东北四省赛选拔赛题解
- @ 2025-5-6 20:11:40
出题人预估题目难度:
J < D < A
G < E < H
K < B < I
L < F < C
tips:
第三梯度很多题都是典,很多题比想象的简单,整体难度签掉题不是很签,但中档题都不难,如果有的题看完题解、学过的算法不感觉这题很典就该练了。
A题不关流用和会超时,在验题的时候就发现了,不是刻意卡的,所有这类输入、输出量特别大的题,尤其是一堆整数,cin和cout、还有endl就是慢,而且慢的离谱,啥比赛不关流你也过不去。
// 警钟长鸣
#define endl '\n'
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
还有好几道题爆的,长点记性吧。
还有,再强调一次,不光结果要开,过程中也要开。
比如如果的范围大,下面就会WA:
int a[N];
long long res = a[1] * a[2];
要像下面这么写
int a[N];
long long res = (long long)a[1] * a[2];
或者
long long a[N];
long long res = a[1] * a[2];
J
按提题意模拟即可,遇到“->”就输出对应数量的空格。
需要注意数据中有几个字符串行末是有"->"的,处理不好的话就可能会越界、多输出或者少输出。
时间复杂度:
D
初始有 堆石子,每堆石子有 个(),两人轮流进行操作,一个人每次可以选取一堆石子将其分成两堆石子,并把其中一堆石子染成黑色,另一堆石子染成白色,这两堆石子的个数没有限制,但不能为 0(也即只有 1 个石子的堆是不能被划分的)。当所有堆都只含有 1 个石子时,游戏结束。此时 brz 的得分为白色的石子个数,Mandy 的得分为黑色的石子个数,问两人同等聪明的情况下 brz 先手能获得的分数。
注:染过色的石子是可以再被染色的。
关键点是只有 1 个石子的堆是不能被划分的,仔细想想,每次划分只有把 分成和,并把 的那堆染成对自己有利的颜色才能获得贡献(因为不能被划分了,颜色不会变)。更进一步,如果 是偶数,那么 和 均为奇数,你的贡献多了 ,别人下次操作 ,他的贡献也会多 ,并得到一堆偶数个数的石子,因此偶数个石子的堆是无净贡献的。那么当 为奇数时,分成了一堆偶数的和一堆只有 的,只有你的贡献会多 。综上,两人都会优先处理奇数个石子的堆,因此只有初始时这样的堆有奇数个,brz 的得分才会比 Mandy 的得分多 ,否则两人得分一样。
时间复杂度:
A
手搓,或者打表,都可以发现这道题的答案。
题意是求 在满足 并且 的情况下的最大值;
设 、、,由上面的条件可得 $$\frac1t + \frac1s + \frac1r = 1$$ ,因为 为整数,而该不定方程的整数解只有如下三组,其中 如下表所示:
| $$3$$ | |||
| $$4$$ | |||
| $$2$$ |
显然如果满足第三种则一定满足第一种,因为是求最大值,所以第三种可以舍弃。如果三种都不满足,就输出。
注意:如果同时满足多种情况,要优先判断并输出大的情况。
时间复杂度:
G
差分,因为区间的范围很大(),但实际的点数很少,因此要离散化一下,将所有的区间的端点存到一个数组里,去重排序一下,这样~的个点就离散化到了从~的个位置,因为排好序了,也不会出现交叉(大的离散化到小的,小的离散化到大的),每次对区间~,只需要二分查找到两个端点在数组中的下标和,然后给差分数组即可。
但事实上,不用这么麻烦,这题的难度远比原估计的要低,其实只需要用一个代替差分数组。观察可以发现,人数最多的那一段一定包含某一个区间的端点,所以只需要在上做差分,然后遍历所有的区间端点即可。
时间复杂度:
也可达到:
E
用并查集的路径压缩来维护每个位置下一个可用的位置,就是从开始右面第一个可以插入的位置,以此为根据进行查找和更新,插入就把当前并查集指向的位置赋值,然后让并查集指向下一个可用的位置即可。
赛时还有很多其他的AC方式,可以等赛后看看别人的代码。
时间复杂度:接近
H
暴力,二进制枚举。
对于每种指标,将他的绝对值展开,都只有两种情况:
$$|x_i(\mathrm{MW}) - x_i(\mathrm{SW})| = \begin{cases} +x_i(\mathrm{MW}) - x_i(\mathrm{SW}), & x_i(\mathrm{MW}) \ge x_i(\mathrm{SW}), \\[6pt] +x_i(\mathrm{SW}) - x_i(\mathrm{MW}), & x_i(\mathrm{MW}) < x_i(\mathrm{SW}). \end{cases}$$也就是说,对于主武器和副武器的每一个指标,他对答案的贡献要么是,要么是,并且这两个的符号恰恰相反。
那一共有种指标,每种指标有加和减两种情况,是不是恰好可以用二进制的和来表示?一共有种情况,每种情况可以用一个位的二进制数来表示,从遍历到就可以枚举所有的情况,第位为就让主武器减、副武器加。第位为就让主武器加、副武器减,对于每个,分别遍历一遍所有的主副武器,分别找到对答案贡献最大的,所有情况取即可。
二进制枚举的过程也可以通过指数级枚举来实现。
时间复杂度:
K
单调栈,对于每根柱子,分别向左右遍历,用单调栈预处理出来第个柱子左边第一个比它矮的柱子的位置()和右边第一个比它矮的柱子的位置, 那么以第根柱子为最矮高度时,可形成的最大宽度是
对应的面积即:
遍历一遍取个最大值即可。
时间复杂度:
B
将每一列的方块的行数和下标存起来,从小到大排序,对于消除操作,如果可以消除,一定是先同时消除每一列最底下的方块,再同时消除每一列自底向上第二个方块...,因此排序后只需要从下往上遍历每一列的每个方块,这些方块消失的时间就是他们之中最高的一个掉到底所需的时间,遍历一遍取即可,将每一个方块消失的时间存起来,处理查询即可。
将数组所有位置初始化成正无穷,如果当前列的当前位置没有方块,同行的方块的最大值也就是正无穷,也就是他们会在第正无穷秒时消失,也就是不会消失。
时间复杂度:
I
首先,若裁判在两者中间(即 ), ,恰好等于两者之间的距离,满足题目条件,在其他位置都不满足。
进而,答案就等于严格上升三元组和严格下降三元组的总数。
对于每个位置 (做裁判),定义:
- :左侧(编号 )Rating 小于 的个数。
- 那么:左侧 Rating 大于 的个数。
- :右侧(编号 )Rating 小于 的个数。
- 那么:右侧 Rating 大于 的个数。
以 为裁判的可行比赛数为:
$$L_k \times \bigl((n-k)-R_k\bigr) \;+\; \bigl((k-1)-L_k\bigr)\times R_k.$$对所有 求和即为答案。
可以维护一个出现次数的树状数组来快速维护前缀和,第一次顺序遍历,通过树状数组的前缀和求前面比小的人的数量,将其存到中。第二次逆序遍历,求出后面比小的数量,存到中,带入公式计算累加到答案即可。
时间复杂度:
L
一道结合背包的思想(dp)、dp通过两维的和为来定值来将降到的优化、括号匹配的思想(栈)、前缀和的思想(转化成-1和+1)的好题。
首先根据题目给出的定义,我们可以考虑进行一个转化,把左括号看成 ,右括号看成 ,这样合法括号序列可以看成任意前缀和非负、区间和为 的序列。
我们由此可以列出一个 的动态规划方案:表示染色到第 项,标记G的前缀和为 ,标记H的前缀和为 的方案。
转移如下:$dp_{i,j,k} = dp_{i-1,j - A_i,k} + dp_{i-1,j,k - A_i}$,初始化,其中 表示经过转换之后我们的数组的第 项。
但是这个方法时间复杂度很高,我们考虑进一步优化。
我们发现对于一个 而言,有用的 是不变的,即数组 的前 项的前缀和,这点观察式子也可以发现。
所以我们只维护 一维,保证 不为负数即可。
非负如何保证?我们发现,其中 是当前前项的前缀和,我们只要保证即可。
时间复杂度:
F
首先声明一个概念:表示:的二进制的最高有效位,即的二进制表示的最高一位。比如。
首先, 对于两条鱼:
- 如果,一定能吃掉,并且吃掉后一定不会减少()。
- 如果,一定不能吃掉。
需要注意的就是的情况,如果该情况能吃掉,则吃掉后一定会减少( )。
在任何时候,我们都应该尽可能多地吃掉左边 较小的鱼,也就是只要小就一直吃,而如果一个一个判断,时间复杂度肯定是不够的 ,所以要用预处理的思想,用一个数组来预处理一下,表示前面(包括)最后一条(也就是离最近的那条)的鱼的下标。如果当前在位置,在和之间的鱼肯定都可以吃,直接将移到的位置,并让异或上两条鱼之间的每条鱼的重量即可,而直接一个异或也一定会超时,需要预处理一下区间的异或和,区间问题就很容易想到前缀和,开一个数组,就表示“从这条鱼开始,还没遇到下一个 的鱼”,即从第条鱼~第条鱼的前缀异或和。而对于大的鱼,直接就可以了。对于和相等的鱼,每次判断一下它的重量和哪个大,如果就吃掉,否则就,因为一直会减少,所以最多只会执行次运算,时间复杂度可以通过。
接下来就是思考如何预处理和数组:计当前,从~遍历可能的每一位:
- 对于数组:
- 如果,左边第一个的位置就是,
- 如果,就递推,
- 对于数组:
- 如果,,区间中没有鱼,
- 如果,区间中加了条鱼,
预处理完后,从第条鱼开始从右向左模拟即可。
时间复杂度:接近
C
这里引入一个概念:k-核(k-Core)。
在一个无向图中,-核是删去所有度数小于 的顶点,不断迭代,剩下的最大子图。
此题中,训练的参与者集必须是当日图中的一个 -核。要让参与人数尽可能多,则自然取整张图的-核。
如果我们直接模拟每天增加一条边后都重新跑一次 -核(删除度 的顶点),最坏每次都要 ,总共也就是 ,会超时。
所以采用算法竞赛中很常用的一个思想:正难则反。
将「每天加一条边」的问题,倒过来想成:「从全图开始,逐天『删掉』一条边」,并动态维护 -核的大小。具体做法:
- 首先,将条边全部加到图上,并将这条边都按顺序存到一个数组里。
- 然后开始求全图的-核:
- 首先,在存图的时候要记录每个点的度数
- 然后,开一个队列,将所有入度的点入队,逐个将这些点弹出队列。
- 在弹出队列的过程中,遍历这些点的出边,将这些边标记“失效”,并将这些边的终点的度数,如果某个终点的度数由减到了,将其入队。
- 循环直到队列为空。
- 剩下的点和边,即为全图的核。
然后,逆序遍历你存边的数组,一条一条删边,删边时给两个端点入度,如果某个点的度数由减到了,给它入队,重复上面的步骤,队列为空后用一个答案数组存现在剩下的点数。
这样倒序得到的答案数组,正好是正序中每一天晚上的最大参与人数。
当然,如果你不想在前面先写一遍求-核的话,那你也可以将队列改成用来模拟队列的过程。
时间复杂度: