2022-02-10 20:48 已编辑浙江财经大学 C++

关注

【题解】2022年第五场寒假集训营题解

前言：由于出题人语文水平低下，且并没有验题人反馈题面难读，导致这场比赛给大家带来了不太妙的阅读体验，非常抱歉。以及题解也很有可能存在描述不清的情况，欢迎在下面评论

前言2：本来这场有12题的，但是出题的时候写前十题已经吐了觉得难度够了，所以留了魔方题和分块题，但是本来认为是简单题的乒乓小孩和飞车小孩，验题时候好几位牛逼验题人不太会做，而认为较难的H题所有验题人都在40-60分钟左右完美通过，E更是过得飞快，觉得这场要被爆ak了，就临时加了K，但没想到大家真的不太会乒乓和飞车，我直接大哭，希望补补题，把

预估题目难度:J<G<A=I=D<F<C<B<E=K<H

A.疫苗小孩

可以发现1针和0针的贡献都为0，所以直接考虑2针及以上的情况

枚举第二针所在的位置pos，二分找到离pos+k和pos-k最近的两个点计算最大贡献即可

复杂度 $O(n*log_2n)$

B.乒乓小孩

简单思索后发现如果两个比分和都大于11则一定有解，于是进行分类讨论，暂划一个有冗余的界限50,且假设x小于等于y：

1.两个数字都小于50，直接dp预处理最小方案的前缀并递归，如果dp无解就输出No，可以发现方案局数一定小于等于max(差的绝对值，1)的两倍

2.其中一个数字小于50，可以把大的那个数字通过若干局0:11调整到小于50，因为两个比分都大于等于11就有解，所以如果小的数字大于11则一定有一个最优解，此时可以直接进行方案1，否则如果 $x\leq10$ ，要么一局10:12，要么通过若干局a:11将x调到0，发现y的拆分中最多有一局12，剩下的肯定都是11，且 $y>39$ ，如果有解必然也可以在剩下的拆分中最多两局把x归零，最多需要用到23分，铁够，所以也可以回到方案1进行判断是否有解并递归

3.x=y且大于等于50：输出x-11:y-9,11:9

4.x!=y且大于等于50：通过若干局11:0将y调整到x+10以内,设y'=x+k,如果k=1,输出x-8:y-11,8:11,否则输出11-k:11并进行方案3

复杂度 $O(\sum k)$

当然你也可以像验题人@zankizero一样进行究极分类讨论，不过并不推荐这种脑溢血的做法

C.战棋小孩

在礼遇状态确定好了以后发现最优的情况是按增加的分数从大到小排序，证明如下：

假设从大到小顺序为 $w_1,w_2,...,w_n$ ,选择其中一个逆序对为(i,j)进行交换，则前缀和从 $w_1,w_1+w_2,...,w_1+...+w_j,...,w_1+...+w_i+...+w_j,...$ 可以发现对 $[1,i-1]和[j,n]$ 两个区间没有影响，且 $[i,j-1]$ 均减小了 $w_j-w_i$ ，所以数组中无正序对下为最优

然后我们二进制枚举使用礼遇的局，并对所有的局取最大提升后降序排列，取开心次数最大值即可

复杂度 $O(2^n*n*logn)$

D.数位小孩

首先这题确实可以直接数位DP(X)

不过从素数环角度入手的话就会发现实际上 $10^10$ 内满足条件的数字数量级为百万，可以直接dfs出所有素数环并找其中带数位1的，特别的1不是素数环但也满足条件

复杂度O(能过)

E.复苏小孩

假设当前三个鬼的力量为(x,y,z),当其走过了字符'1'后变为(x+y/2+z/2,y/2,z/2),相当于乘上了一个矩阵

$\begin{bmatrix}1 & 0 & 0 \\1/2 & 1/2 & 0 \\1/2 & 0 & 1/2 \\\end{bmatrix}$

同理其他两个字符也可以构造等效的矩阵，由于矩阵乘法满足结合律，我们可以用线段数维护n个矩阵，每次查询 $[l,r]$ 相当于把r-l+1个矩阵按顺序相乘，然后用(1,1,1)乘上这个矩阵即可得出解

复杂度 $O(n*logn*27)$

F.飞车小孩

通过一次选图可以确定本局之前和上次选图之间K0u1e和九峰分别选了几张图，设K0u1e选了x张，九峰选了y张，那这段未知区间内的方案数为C(x+y,y)

特别地，已知最后一局的后面的局数每局有两种可能，所以之前算的的方案数的乘积乘上 $2^{w=已知的最后一局后面的局数}$ 即为答案

复杂度 $O(n*logn)$

G.163小孩

能瞎算出来18395就行，暴力也行，主要是给下一题加的提示

假设一种方案从小到大排序后为一个六位的13进制数，只要这个数字不同就代表了不同方案，所以我们可以从小到大枚举这个13进制数，需要注意其中不能有超过4个数字相同，能枚举出的数字个数即为方案数

没有复杂度

H.一六三小孩

讲个故事：本来该题的容错是20%，但是验题人均随手写一小时不到就能40%，甚至其中两位在两小时内正确率提升到了80%以上，所以在防ak的宗旨下不得已就调整到了50%，不过还是被神仙群友乱过了

该题的初衷就是看看群友八仙过海的做法，所以没有所谓正解，这里讲一下两个80%以上的做法：

某个不愿意透露姓名的wf选手:首先打表发现99%的数据都可以只用加减乘算出163，所以不考虑除法，然后将六个分成两组每组三个后分别处理出各自能算出来的所有数字，然后枚举两组之间加减乘，随机打乱几次后重复这种做法直到算出163或次数较多，对18395种方案预处理的话可以增加随机的次数

某个不愿意透露姓名的红名oi选手:一开始读错题以后写了个暴力，发现90%以上的方案都满足以下性质：可以枚举5个运算符，遇到乘除自动加上右括号并在最左边加个左括号，因此对于所有排列 $5^4$ 枚举运算符并把能算出163点的情况的六个数字按顺序打表出来，由于该策略复杂度很低，打表只需要10s

也没有复杂度

I.兔崽小孩

将每个时间段取出来从大到小排序，对于每次询问二分查找最小的满足大于等于k的时间段下标，判断前缀和-下标*k是否大于等于p即可

复杂度O(n*logn)

J.三国小孩

己方每出一张牌对方也得跟一张才能免除伤害，直接判断n+m是否大于k即可

复杂度O(1)

K.造梦小孩

分块题

对于1操作
直接单点修改并修改所在的块

对于2操作，
len大于block：对所有需要修改的位置单点修改并修改所在的块
len小于block：记录 $s_{i,j}$ 表示len为i,最左的修改位置所在的点为j的修改量,对第二维求一个前缀和pre，并对x位置进行1操作的负修改抵消影响

对于查询,考虑前缀查询,即cal(y)-cal(x-1),对于cal(x)
首先分块查询操作1的影响
然后枚举操作2的len，对于一个x来讲，存在一个k，使得1-k内的i满足1到x内与i距离为len的倍数的下标个数为x/len+1,k+1到len内满足这个下标个数为x/len，可以发现k=x%len，通过前缀和计算贡献为 $pre[len][k]*(x/len+1)+(pre[len][len]-pre[len][k])*(x/len)$