暑训之罚训大礼包

发布于 2022-07-15  58 次阅读


前言

由于不可抗力的迟到,被赏了一套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

标签

DFS,贪心

题意

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

题解

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

D - RPG Protagonist

标签

枚举,贪心

题意

有两种武器数量分别为 cnt_scnt_w ,重量为 sw,两个人可以携带的重量为 pf ,问两个人最多能带出几把武器。

题解

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

E - Binary String To Subsequences

标签

思维,模拟,实现

题意

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

题解

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

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

F - Colored Rectangles

标签

贪心,dp

题意

给三种颜色的棒子,每种棒子有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

标签

思维,dp

题意

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

题解

可以发现子序列长度为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的处理
* 使用数据结构保存状态来转化问题
* 字符串问题的转化
* 根据数据范围,运用抽屉原理等方法简化问题
* 绝对值的处理
* 多项式的推理与假设
最重要的还是贪心、构造、枚举等基本功,一方面要敢想,一方面要敢转变思路。


盛夏日落迟 灯火未夜匆匆明