2022集训队选拔赛题解

发布于 2022-03-06  269 次阅读


A 坐标

签到题,模拟一下即可。比较方便的写法是先找到原点的位置,然后减一下就行了。

B A+B

签到题,展开可得每一项都被加了n-1次。

C 你的原石还够吗

数据结构题。需要实现一种数据结构,能够在任意位置快速插入。

正着放入队列时,已经被放进去的值的位置可能会随着之后的插入而改变,而倒着取出的时候当前值的位置是固定的,即为在最终答案中的位置。只要能快速求出这个位置,问题就得到解决。

容易发现,p_i在这种情况下表示当前值前面还有几个数。维护一个树状数组(类似维护区间和的数据结构皆可)表示[1,n]每个位置的数前面有几个数,那么从前往后扫,找到最小的满足前面的数大于等于$p_i$的位置,这个位置就是它在最终答案中的位置。

但每次查询从前往后扫一遍,最坏情况下为O(n^2)。而查询和的函数单调递增,正好可以使用二分优化到O(nlogn)

D 高木与西片

lca板子题,找到最近公共祖先的深度,与根结点的深度相减即可。

E 高木与西片2

防签到的概率题。

假设当前回合自己手上有n张卡,对方有m张卡。

如果这回合直接猜桌子上的牌,赢的概率是\frac{1}{m+1}

如果要求对方舍弃的牌是对方没有的就会输(因为自己找出了答案,却没法选),而到对方的回合猜中了桌子上的牌也会输。用1减去这两种可能就是这一回合要求对方舍弃卡赢的概率。

事实上,双方所做的博弈就是每一步都选择两种赢的概率中更大的一种进行。

边界条件n=i,m=0时概率是1,n=0,m=i时概率是\frac{1}{i+1}。其余的状态下,由于每一步都做最优的选择,所以每一步的概率都可以由n,m更小的状态决定。因此可以递归解决。

每次查询跑dfs会超时,所以可以使用记忆化搜索,预处理一遍答案即可。

F 小康爱咕咕

最短路板子题。这个数据范围几种最短路算法都可以。

每次删一个点,再跑一次最短路,再还原,记录最小的代价即可。

删一个点即为把它和相邻点之间的边全都设为inf

G A*B

组合数学。式子和B题长得很像,将每一个括号作为一个整体考虑,可以发现每个括号(a_i+a_j)被乘的次数为a_i出现的次数和a_j出现的次数之积,即C_{cnt[a_i]}^1*C_{cnt[a_j]}^1。当a_i=a_j的情况下,乘的次数是C_{ai}^2。使用快速幂求出每一项的值相加即可。

注意指数取模需要模mod-1(欧拉定理)。

听说hard版是只保证a_i<998244353,大佬们可以思考一下。

H 01背包

算是线性dp?首先考虑只要一个人得分确定,另一个人也就确定了,那么总得分也就确定了。

dp[i]表示是否能够得到i分,那么对于每一道题更新能够到达的所有分数即可。

需要注意的是分数的范围是[-10000,10000],而数组下标不能为负,所以可以将dp下标偏移10000。

注意题目分数分别为正和负时转移的顺序相反。

I position zero

二分。易知花费香蕉最少来满足题意的情况是第k个猴子拿到最多香蕉,向两边与k的距离每增加1,拿到的香蕉数就-1,直到为1。那么二分第k个猴子最多拿到的香蕉数,计算出这种情况下最小需要的总香蕉数是否小于等于m即可。

J 小郑爱摸鱼

dp。首先子序列的个数等于第一位数字在原字符串出现的个数*第二位数字在原字符串出现的个数。

那么可以用一个dp求出数字j在长度为i的字符串中出现的个数,然后再用一个dp求出子序列在长度为i的字符串中出现的个数,最后通过类似前缀和的方式来查询区间的值即可,注意减去区间左边对子序列的贡献

K 小贺爱熬夜

并查集比较容易。

众所周知n个点最少需要n-1条边来连通,而题目不保证无重边和环。

每加进来一条边,就判断这条边所连的点是否加入连通块,如果没有,那么连通所需的边就少了一条。


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