出题人预估题目难度:

J < D < A

G < E < H

K < B < I

L < F < C

tips:

第三梯度很多题都是典,很多题比想象的简单,整体难度签掉题不是很签,但中档题都不难,如果有的题看完题解、学过的算法不感觉这题很典就该练了。

A题不关流用cincin和coutcout会超时,在验题的时候就发现了,不是刻意卡的,所有这类输入、输出量特别大的题,尤其是一堆整数,cin和cout、还有endl就是慢,而且慢的离谱,啥比赛不关流你也过不去。

// 警钟长鸣
#define endl '\n'

ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

还有好几道题爆intint的,长点记性吧。

还有,再强调一次,不光结果要开longlonglong long,过程中也要开longlonglong long。

比如如果a[i]a[i]的范围大,下面就会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

按提题意模拟即可,遇到“->”就输出对应数量的空格。

需要注意数据中有几个字符串行末是有"->"的,处理不好的话就可能会越界、多输出或者少输出。

时间复杂度:O(T×n×m×k)O(T \times n \times m \times k)

D

初始有 nn 堆石子,每堆石子有 aia_i 个(ai≥2a_i \ge 2),两人轮流进行操作,一个人每次可以选取一堆石子将其分成两堆石子,并把其中一堆石子染成黑色,另一堆石子染成白色,这两堆石子的个数没有限制,但不能为 0(也即只有 1 个石子的堆是不能被划分的)。当所有堆都只含有 1 个石子时,游戏结束。此时 brz 的得分为白色的石子个数,Mandy 的得分为黑色的石子个数,问两人同等聪明的情况下 brz 先手能获得的分数。

注:染过色的石子是可以再被染色的。

关键点是只有 1 个石子的堆是不能被划分的,仔细想想,每次划分只有把 aia_i分成ai−1a_i - 1和11,并把 11 的那堆染成对自己有利的颜色才能获得贡献(因为11不能被划分了,颜色不会变)。更进一步,如果 aia_i 是偶数,那么 11 和 ai−1a_i - 1 均为奇数,你的贡献多了 11,别人下次操作 ai−1a_i - 1,他的贡献也会多 11,并得到一堆偶数个数的石子,因此偶数个石子的堆是无净贡献的。那么当 aia_i 为奇数时,分成了一堆偶数的和一堆只有 11 的,只有你的贡献会多 11。综上,两人都会优先处理奇数个石子的堆,因此只有初始时这样的堆有奇数个,brz 的得分才会比 Mandy 的得分多 11,否则两人得分一样。

时间复杂度:O(∑n)O(\sum n)

A

手搓,或者打表,都可以发现这道题的答案。

题意是求 xyzxyz 在满足 x+y+z=nx+y+z=n 并且 x∣n,  y∣n,  z∣nx\mid n,\;y\mid n,\;z\mid n 的情况下的最大值;

设 t=nxt=\frac{n}{x}、s=nys=\frac{n}{y}、r=nzr=\frac{n}{z},由上面的条件可得 $$\frac1t + \frac1s + \frac1r = 1$$ ,因为 t,s,rt,s,r 为整数,而该不定方程的整数解只有如下三组,其中 xyzxyz 如下表所示:

tt ss rr xyzxyz
33 $$3$$ 33 n327\dfrac{n^3}{27}
22 44 $$4$$ n332\dfrac{n^3}{32}
$$2$$ 33 66 n336\dfrac{n^3}{36}

显然如果满足第三种则一定满足第一种,因为是求最大值,所以第三种可以舍弃。如果三种都不满足,就输出−1-1。

注意:如果同时满足多种情况,要优先判断并输出xyzxyz大的情况。

时间复杂度:O(T×1)O(T \times 1)

G

差分,因为区间的范围很大(2302^{30}),但实际的点数很少,因此要离散化一下,将所有的区间的端点存到一个数组里,去重排序一下,这样v[0]v[0]~v[n]v[n]的nn个点就离散化到了从00~nn的nn个位置,因为排好序了,也不会出现交叉(大的离散化到小的,小的离散化到大的),每次对区间LL~RR,只需要二分查找到两个端点在数组中的下标ll和rr,然后给差分数组d[l]++,d[r+1]−−d[l]++,d[r+ 1]--即可。

但事实上,不用这么麻烦,这题的难度远比原估计的要低,其实只需要用一个mapmap代替差分数组。观察可以发现,人数最多的那一段一定包含某一个区间的端点,所以只需要在mapmap上做差分,然后遍历所有的区间端点即可。

时间复杂度:O(nlogn)O(nlogn)

也可达到:O(n)O(n)

E

用并查集的路径压缩来维护每个位置下一个可用的位置,find(x)find(x)就是从xx开始右面第一个可以插入的位置,以此为根据进行查找和更新,插入就把当前并查集指向的位置赋值,然后让并查集指向下一个可用的位置即可。

赛时还有很多其他的AC方式,可以等赛后看看别人的代码。

时间复杂度:接近O(N+q)O(N+q)

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}$$

也就是说,对于主武器和副武器的每一个指标,他对答案的贡献要么是++,要么是−-,并且这两个的符号恰恰相反。

那一共有kk种指标,每种指标有加和减两种情况,是不是恰好可以用二进制的00和11来表示?一共有2k2^k种情况,每种情况可以用一个kk位的二进制数来表示,maskmask从11遍历到2k2^k就可以枚举所有的情况,maskmask第ii位为11就让主武器减、副武器加。第ii位为00就让主武器加、副武器减,对于每个maskmask,分别遍历一遍所有的主副武器,分别找到对答案贡献最大的,所有情况取maxmax即可。

二进制枚举的过程也可以通过dfsdfs指数级枚举来实现。

时间复杂度:O(∑(n+m)×2k)O(\sum(n +m) \times 2^k )

K

单调栈,对于每根柱子,分别向左右遍历,用单调栈预处理出来第ii个柱子左边第一个比它矮的柱子的位置(l[i]l[i])和右边第一个比它矮的柱子的位置r[i]r[i], 那么以第ii根柱子为最矮高度时,可形成的最大宽度是

ri−li−1,r_i - l_i - 1,

对应的面积即:

hi×(ri−li−1).h_i \times (r_i - l_i - 1).

遍历一遍取个最大值即可。

时间复杂度:O(T×n)O(T \times n)

B

将每一列的方块的行数和下标存起来,从小到大排序,对于消除操作,如果可以消除,一定是先同时消除每一列最底下的方块,再同时消除每一列自底向上第二个方块...,因此排序后只需要从下往上遍历每一列的每个方块,这些方块消失的时间就是他们之中最高的一个掉到底所需的时间,遍历一遍取maxmax即可,将每一个方块消失的时间存起来,处理查询即可。

将数组所有位置初始化成正无穷,如果当前列的当前位置没有方块,同行的方块的最大值也就是正无穷,也就是他们会在第正无穷秒时消失,也就是不会消失。

时间复杂度:O(n+q)O(n + q)

I

首先,若裁判kk在两者中间(即 i<k<ji < k < j),∣i−k∣+∣j−k∣=k−i+j−k=j−i|i - k| + |j - k| = k - i + j - k = j - i ,恰好等于两者之间的距离,满足题目条件,在其他位置都不满足。

进而,答案就等于严格上升三元组和严格下降三元组的总数。

对于每个位置 kk(做裁判),定义:

  • LkL_k:左侧(编号 <k<k)Rating 小于 aka_k 的个数。
    • 那么(k−1)−Lk(k-1)-L_k:左侧 Rating 大于 aka_k 的个数。
  • RkR_k:右侧(编号 >k>k)Rating 小于 aka_k 的个数。
    • 那么(n−k)−Rk(n-k)-R_k:右侧 Rating 大于 aka_k 的个数。

以 kk 为裁判的可行比赛数为:

$$L_k \times \bigl((n-k)-R_k\bigr) \;+\; \bigl((k-1)-L_k\bigr)\times R_k.$$

对所有 k=1…nk=1\ldots n 求和即为答案。

可以维护一个出现次数的树状数组来快速维护前缀和,第一次顺序遍历,通过树状数组的前缀和求kk前面比a[k]a[k]小的人的数量,将其存到l[k]l[k]中。第二次逆序遍历,求出ii后面比ii小的数量,存到r[k]r[k]中,带入公式计算累加到答案即可。

时间复杂度:O(T×n×logn)O(T \times n \times logn)

L

一道结合背包的思想(dp)、dp通过两维的和为来定值来将O(n2)O(n ^ 2)降到O(2n)O(2n)的优化、括号匹配的思想(栈)、前缀和的思想(转化成-1和+1)的好题。

首先根据题目给出的定义,我们可以考虑进行一个转化,把左括号看成 +1+1,右括号看成 −1-1,这样合法括号序列可以看成任意前缀和非负、区间和为 00 的序列。

我们由此可以列出一个 O(n3)O(n^3) 的动态规划方案:dpi,j,kdp_{i,j,k}表示染色到第 ii 项,标记G的前缀和为 jj,标记H的前缀和为 kk 的方案。

转移如下:$dp_{i,j,k} = dp_{i-1,j - A_i,k} + dp_{i-1,j,k - A_i}$,初始化dp0,0,0=1dp_{0,0,0} = 1,其中 AiA_i 表示经过转换之后我们的数组的第 ii 项。

但是这个方法时间复杂度很高,我们考虑进一步优化。

我们发现对于一个 ii 而言,有用的 j+kj+k 是不变的,即数组 AA 的前 ii 项的前缀和,这点观察式子也可以发现。

所以我们只维护 jj 一维,保证 kk 不为负数即可。

dpi,j=dpi−1,j−Ai+dpi−1,jdp_{i,j} = dp_{i-1,j - A_i} + dp_{i-1,j}

kk非负如何保证?我们发现k=sum−jk = \text{sum} - j,其中sumsum 是当前前ii项的前缀和,我们只要保证j≤sumj \le \text{sum}即可。

时间复杂度:O(n2)O(n^2)

F

首先声明一个概念:msb(n)msb(n)表示:nn的二进制的最高有效位,即nn的二进制表示的最高一位11。比如msb(1101)2=3,msb(1)=0msb(1101)_2 = 3,msb(1) = 0。

首先, 对于两条鱼:

  • 如果msb(鱼a)>msb(鱼b)msb(鱼a)>msb(鱼b),鱼a鱼a一定能吃掉鱼b鱼b,并且吃掉鱼b鱼b后msb(鱼a)msb(鱼a)一定不会减少(1⨁0=01 \bigoplus 0 = 0)。
  • 如果msb(鱼a)<msb(鱼b)msb(鱼a)<msb(鱼b),鱼a鱼a一定不能吃掉鱼b鱼b。

需要注意的就是msb(鱼a)=msb(鱼b)msb(鱼a)=msb(鱼b)的情况,如果该情况鱼a鱼a能吃掉鱼b鱼b,则吃掉鱼b鱼b后msb(鱼a)msb(鱼a)一定会减少(1⨁1=01 \bigoplus 1 = 0 )。

在任何时候,我们都应该尽可能多地吃掉左边 msbmsb较小的鱼,也就是只要msbmsb小就一直吃,而如果一个一个判断,时间复杂度肯定是不够的 ,所以要用预处理的思想,用一个lastlast数组来预处理一下,left[i][j]left[i][j]表示ii前面(包括ii)最后一条(也就是离ii最近的那条)msb≥jmsb \ge j的鱼的下标。如果当前xx在位置ii,在ii和left[i][msb(x)]left[i][msb(x)]之间的鱼肯定都可以吃,直接将xx移到left[i][mbs(x)]left[i][mbs(x)]的位置,并让xx异或上两条鱼之间的每条鱼的重量即可,而直接一个异或也一定会超时,需要预处理一下区间的异或和,区间问题就很容易想到前缀和,开一个prepre数组,pre[i][j]pre[i][j]就表示“从这条鱼ii开始,还没遇到下一个msb≥jmsb \ge j 的鱼”,即从第left[i][j]+1left[i][j] + 1条鱼~第ii条鱼的前缀异或和。而对于msbmsb大的鱼,直接breakbreak就可以了。对于msbmsb和msb(x)msb(x)相等的鱼,每次判断一下它的重量和xx哪个大,如果w≤xw \le x就吃掉,否则就breakbreak,因为msbmsb一直会减少,所以最多只会执行log(x)log(x)次运算,时间复杂度可以通过。

接下来就是思考如何预处理leftleft和prepre数组:计当前msb(a[i])=dmsb(a[i]) = d,从00~3030遍历可能的每一位jj:

  • 对于leftleft数组:
    • 如果j≤dj \le d,左边第一个msb≥jmsb \ge j的位置就是ii,left[i][j]=ileft[i][j] = i
    • 如果j>dj > d,就递推,left[i][j]=left[i−1][j]left[i][j] = left[i - 1][j]
  • 对于prepre数组:
    • 如果j≤dj \le d,left[i][j]=ileft[i][j] = i,区间中没有鱼,pre[i][j]=0pre[i][j] = 0
    • 如果j>dj > d,区间中加了条鱼ii,pre[i][j]⨁=w[i];pre[i][j] \bigoplus= w[i];

预处理完后,从第nn条鱼开始从右向左模拟即可。

时间复杂度:接近O(∑(n+q)×log(maxw))O(\sum(n + q) \times log(max w))

C

这里引入一个概念:k-核(k-Core)。

在一个无向图中,kk-核是删去所有度数小于 kk 的顶点,不断迭代,剩下的最大子图。

此题中,训练的参与者集必须是当日图中的一个 kk-核。要让参与人数尽可能多,则自然取整张图的kk-核。

如果我们直接模拟每天增加一条边后都重新跑一次 kk-核(bfsbfs删除度<k<k 的顶点),最坏每次都要 O(n+m)O(n+m),总共也就是 O((n+m)m)O((n+m)m),会超时。

所以采用算法竞赛中很常用的一个思想:正难则反。

将「每天加一条边」的问题,倒过来想成:「从全图开始,逐天『删掉』一条边」,并动态维护 kk-核的大小。具体做法:

  • 首先,将mm条边全部加到图上,并将这mm条边都按顺序存到一个数组里。
  • 然后开始求全图的kk-核:
    • 首先,在存图的时候要记录每个点的度数d[u]d[u]
    • 然后,开一个队列,将所有入度<k<k的点入队,逐个将这些点弹出队列。
    • 在弹出队列的过程中,遍历这些点的出边,将这些边标记“失效”,并将这些边的终点的度数−1-1,如果某个终点的度数由kk减到了k−1k - 1,将其入队。
  • 循环直到队列为空。
  • 剩下的点和边,即为全图的kk核。

然后,逆序遍历你存边的数组,一条一条删边,删边时给两个端点入度−1-1,如果某个点的度数由kk减到了k−1k - 1,给它入队,重复上面的步骤,队列为空后用一个答案数组存现在剩下的点数。

这样倒序得到的答案数组,正好是正序中每一天晚上的最大参与人数。

当然,如果你不想在前面先写一遍求kk-核的话,那你也可以将队列改成用vectorvector来模拟队列的过程。

时间复杂度:O(n+m)O(n+ m)

1 條評論

  • @ 2025-9-21 21:28:02

    加油加油

    • 1