暑训之罚训大礼包

amcones 收录于 Algorithm

2022-11-04 约 4278 字预计阅读 9 分钟 - 次阅读

前言

由于不可抗力的迟到，被赏了一套26道的罚训大礼包，写了三四天。虽然中间有摸鱼干别的，不过确实量不少。更重要的是，1500-1800的题技巧性很强，也可能是我做题做少了，感觉很多技巧都很新鲜。总而言之，还是学到了不少东西。

写这篇文章来回忆一下这些题的技巧。

没有感情，全是技巧。

A - Decrease the Sum of Digits

题意

给一个正数$n$，问最少加多少可以让$n$的数位和小于等于$s$。

题解

可以发现只有当把$n$加到10的倍数的时候数位和才会减小，所以只要把$n$加到10的倍数即可。为了更快，每次都往最低的不是0的位数上加。

B - Two Platforms

题意

一个平面上有$n$个小球，他们都在下落，问在哪里放置两个长度为$k$的平台可以接住最多的点。

题解

可以发现这道题与纵坐标无关，只要考虑横坐标。不难发现以某个小球为起点放置平台是最佳的，但是如何放置两个最佳？

假设第一块平台放在第$i$个小球处，最远可以覆盖到第$j$个小球，那么第二块平台就要从第$j+1 \dots n$之间选一个。

可以预处理一个数组，保存从$i \dots n$之间任选一个小球开始覆盖得到的最优值。使用二分可以快速知道一块板子最远可以覆盖到哪一个小球。最后结果只要枚举第一块板子放的位置，然后二分出第一块板子可以接到的小球数加上预处理的数组值即可。

C - Maximum Distributed Tree

题意

给一颗树，给树上每一条边分配一个权重，使得每两个节点间路径总和最大，1的数量尽可能少，乘积为k。

题解

根据每条边被统计到的次数贪心。

D - RPG Protagonist

题意

有两种武器数量分别为 $cnt_s$ 和 $cnt_w$ ，重量为 $s$ 和 $w$，两个人可以携带的重量为 $p$ 和 $f$ ，问两个人最多能带出几把武器。

题解

本来以为是背包，其实可以直接贪（因为所有物品价值都一样）。肯定是尽可能装重量小的武器，只要枚举第一个人能够带出几把第一种武器，那么剩下几个值也都可以求出。

E - Binary String To Subsequences

题意

给一个01串，需要将它切成若干子序列使得每个子序列中没有2个相邻的0或1，问如果切分子序列数最少。

题解

不难发现原串中相邻的两个0或1就需要被放到不同的子串当中，那么只要放入一个字符都找有没有子串结尾与自己不同，如果有就放入，没有就新开。

实现的时候存两种结尾的子序列分别有哪些，每次放入新的数直接取一个对应的子序列出来即可。

F - Colored Rectangles

题意

给三种颜色的棒子，每种棒子有$R,G,B$对，每一对有一个长度。每次需要取两种颜色的棒子搭矩形，问最多能搭的矩形总面积多大。

题解

显然应该尽可能取长的棍子搭，但每次该取哪两种是个问题。通过dp存下每种棒子取多少数量下的最大面积，其实算是记忆化搜索了。

G - Good Subarrays

题意

给一个数组，问有多少连续子区间满足他们的和等于他们的长度。

题解

对每一个数减去1，问题就转变成有多少连续子区间的和等于0。也就是说，两个前缀和相同，这个子区间和就为0。

最后，就是看有几个前缀和相同，贡献的区间数为$x*(x-1)/2$。

H - Same GCDs

题意

两个整数$a,m$，计算有多少个$x$使得$\gcd(a,m)=\gcd(a+x,m)$。

题解

简单推一下。 $$ \begin{align} \gcd(a,m)=\gcd(a+x,m)=d\ \gcd(\frac{a+x}{d},\frac{m}{d})=1\ x’=a+x\ gcd(\frac{x’}{d},\frac{m}{d})=1 \end{align} $$ 即求$[0,\frac{m}{d})$有多少数与$\frac{m}{d}$互质，也就是裸的欧拉函数。

I - Ehab and Prefix MEXs

题意

给一个数组$a$，求一个数组$b$使得： $$\forall i(i\leq i \leq n),MEX({b_1,b_2,\dots,b_i})=a_i$$。

题解

首先，在$[0,n]$中，只要是$a$中没有出现过的数就可以放入$b$。

然后对于$a$中的每一个数，只要$a[i-1]$ 与 $a[i]$不同就可以把$a[i-1]$放入，放入后可以保证$MEX=a_i$（因为之前没出现过的，出现过的都放进去了）。

$b$要用自动排序的容器，保持单调性。（比如set）

J - Skyscrapers (easy version)

题意

给一个数组，每一个数有最大限制，要求每一个数两边不能同时有数大于自己，问每个数最大是多少。

题解

即把整个数组变成一个单峰数列。枚举峰顶，然后计算更新总和即可。

在hard情况下一一枚举峰顶再全部更新会超时，所以用单调栈维护，可以直接找到需要修改的位置。当前峰顶大于上一个峰顶的时候，之前的部分不用动直接加上上一个峰顶即可。后面的部分同理。同时累加结果也需要优化，使用dp或前缀和（其实都一样）。

K - Yet Another Walking Robot

题意

给一个指令序列，包含有上下左右四种指令，机器人收到指令会朝对应方向前进一步，问能删除最小的一个子串使得机器人的最终位置没有变化。

题解

显然如果子串中包含的L与R，U与D有相同数量就能够实现，但是枚举这样的子串会超时。如果使用双指针这样的算法，没法确定两个指针的位置。

转变思路，使用map保存机器人的当前位置与指令长度，之后遇到相同的位置就说明中间的这一段都可以删去，只要找到这样的最短的指令段即可。

L - Fight with Monsters

题意

$n$个怪物，每个都有个血量。玩家与对手轮流攻击，玩家补刀可以得分。玩家可以使用$k$次技能让对手跳过回合，问玩家最多得几分。

题解

可以计算出不使用技能可以得几分，与要补刀某一个怪需要用几次技能，贪心即可。

M - String Coloring (easy version)

题意

给一个字符串，将字符串中的每个字符上两种颜色中的一种，相邻的颜色不同就可以交换两个字符，问能否找到一种上色方案使得字符串能够按照字典序排列。

题解

其实就是问能不能把字符串分成两个非降序子串（如果不能，则内部有升序，需要做违反题意的操作才能够达到），所以只要依次把原串字符放入两个子串即可。

N - Anu Has a Function

题意

给一个函数 $$f(x,y)=(x|y)-y$$ 和一个数组$a$，要使$f(f(\dots f(f(a_1,a_2),a_3),\dots a_{n-1}),a_n)$最大，问如何排列数组$a$。

题解

由于经典位运算题目套路，位独立，所以可以发现只有当最高位只出现过一次才不会被减掉，只有第一个数影响结果，后面可以随便排列，所以要把贡献唯一最高位的数放在第一个。对于每一个数枚举它的所有位即可，最后看看最高位是谁贡献的。

O - Aerodynamic

题意

对正$n$边形做一个变换，按顺时针给出变换后图形的每一个点的位置，求变换后图像是否与原图形相似。

题解

变换后也是一个正$n$边形，而正$n$边形的特征是有中心，只要判断中心即可。

中心在每一条对角线的中点上，实现的时候可以统一乘以二避免除法，判断是不是交在一个点上即可。

P - Fast Food Restaurant

题意

有三种食物有不同的数量，每个客人每个菜最多只能拿一份，每个客人至少都要拿到菜，且每个人拿到的菜品集合不同，问最多能接待多少人。

题解

一开始以为是个与二进制有关的题，但实际上直接枚举就可以了，范围很小。

代码量比较少的实现方法是按照数量从小到大去枚举。

Q - Grid-00100

题意

给一个01矩阵，定义$R_i$是每行元素的和，$C_j$是每列元素的和，$f(A)=(\max(R)-\min(R))^2+(\max(C)-min(C))^2$。

给出矩阵中1的数量，求如何安排1的位置使得$f(A)$最小。

题解

使用每行错开一位的构造方式得到最优解。（由于行与列数量相同，所以每行错开一位就可以做到平均分配1）如果1的数量少了或者多了（就是不能整除），就把差值分配到每一行。

R - Different Rules

题意

第一场排名$x$，第二场排名$y$，总的得分为$x+y$，总的排名为总的得分小于等于$x+y$的人数，求最好情况和最坏情况下能够得到的名次。

题解

就硬推，找规律，最坏的情况下就是总得分比自己小的人全都是不同的人，最好情况就是每个人尽量大于等于$x+y$。

S - Cow and Message

题意

给一个字符串，求出现次数最多的子序列的出现次数。

题解

可以发现子序列长度为2的时候是最优的，多了只会减少。使用dp算出每一种长度为2的子序列出现的次数。

T - Kuroni and Impossible Calculation

题意

给$n$个数，求 $$ \prod_{1\leq i \lt j \leq n}|a_i-a_j|。 $$ 结果对$m(1\leq m \leq 1000)$取模。

题解

首先应该非常敏感的发现$m$的范围很小以及$O(n^2)$会爆。

$n(n\geq m+1)$个数对$m$取模，则必有两个数同模。（抽屉原理，易证）

也就是说在$n \geq m+1$的情况下，有两个数同模，他们的差必然是$m$的倍数，取模后结果为0，总的结果也为0。

那么就只要考虑 $n \leq m$的情况，暴力即可。

U - Motarack’s Birthday

题意

给一个数列，找到一个数$k$替换数组中的所有-1，使得数列中相邻两数差的绝对值之和最小。

题解

只要考虑最大和最小值即可，取最大和最小值的中间数，到其它数的距离一定包含在其中。

V - Ayoub’s function

题意

一个01串，给定其长度和其中1的个数，问有多少子串至少包含一个1。

题解

容易发现平均划分0的串是最优的。首先计算出如果全部都是1有多少区间，然后减去全0串的情况。不能整除长度的全0串分散到各个全0串中。

W - Perfect Keyboard

题意

给一个字符串$s$，要求重新排列26个字母，使得$s$中相邻的两个字母在新的排列中也相邻。

题解

不难发现题目要求每个节点度数至多为2，而度数为1的节点可以作为根。一边进行dfs一边把字符加入到答案即可。

X - Primitive Primes

题意

定义三个函数 $$ \begin{align} f(x)=a_0+a_1x+\dots+a_{n-1}x^{n-1}\ g(x)=b_0+b_1x+\dots+b_{m-1}x^{m-1}\ h(x)=f(x)\cdot g(x) \end{align} $$ 和一个质数$p$，求在$h(x)$中找到一个系数不能被$p$整除。

题解

设$a_i,b_j$是第一个不能被$p$整除的系数。 $$ c_{i+j}=(a_0\cdot b_{i\cdot j}+\dots+a_{i\cdot j}\cdot b_0) $$ 由于$a_i,b_j$是第一个不能被$p$整除的系数，所有前面的系数都能够被整除，前面的项都能够被整除，只有$a_i\cdot b_j$不能。找到第一个不能被$p$整除的$a_i,b_j$相加即可。

Y - Air Conditioner

题意

每个客人有一个满意的温度区间，每一个时刻能够向上向下调整空调温度1度，问能否让所有人都满意。

题解

记录每一个时刻能够到达的最大的温度区间，看是否在满意的区间内，然后再从这个状态开始处理下一个人即可。

Z - Shortest and Longest LIS

题意

有一个字符串，给定一个包含大于小于号的串描述它相邻两位的关系，求满足条件的含有最短LIS和最长LIS的串。

题解

在求最短LIS的时候，在前面放最大的数，最长则相反。

总结

通过这26道题不难发现，全部都是基础算法，但有很多有意思且经典的技巧，比如：

对原数组每个元素-1使得前缀和问题简化
二分预处理
gcd与互质结论转化
位运算、位独立
mex的处理
使用数据结构保存状态来转化问题
字符串问题的转化
根据数据范围，运用抽屉原理等方法简化问题
绝对值的处理
多项式的推理与假设最重要的还是贪心、构造、枚举等基本功，一方面要敢想，一方面要敢转变思路。