字节跳动杯简易题解

未分类

---

A. 甜甜值（签到）
数组的甜甜值可以简化成$2 \times \sum_{i=1}^na_i - a_1 - a_n$，所以要让$a_1+a_n$尽量小。先对数组排个序，把第二小的放到最后去即可。注意特判$n=1$的情形。

B. 甜甜的区间（中等）
考虑二分，对一个区间$[l,r]$，选其中点为$m=\lfloor \frac{l+1}{2} \rfloor$，那么其所有子区间分为三种：
1. $[a,b](l \le a \le b \le m)$
2. $[a,b](m+1 \le a \le b \le r)$
3. $[a,b](l \le a \le m < b \le r)$
前两种情况可以递归处理，那么只需处理剩下的第3种情况。
如果区间内最小值不只出现一次，我们假定下标最小的那个才是最小值。
那么我们分两部分枚举最小值的下标$k$，也即$k \le m$和$k > m$两种情况，令$l_k,r_k$分别表示$a_k$为最小值时区间左界的最小值和右界的最大值，显然这两个值随$k$的变化具有单调性，维护一个$std::map$记录区间xor即可维护答案。

C.德州扑克（困难）
按题意枚举即可，没有特意卡常数。
让甜甜lose的话很容易判定，枚举是否有两张底牌能让甜甜输即可。
让甜甜win的话判定稍微复杂一点，需要把$2n$张牌拆成$n$对，每对都会输给甜甜，写个简单的记忆化搜索（甚至裸暴力）或者状态压缩dp都行。
最后请注意，A2345也是顺子，题目中已特意标明。

D.小学生算数（中等）
因为小数点后最多$9$位，那么给每个数乘上$10^9$之后都是整数，题目转变成$n$个$10^{18}$以内的整数，有多少对相乘的结果能被$10^{18}$整除。只需要记录每个数$2$和$5$的因子个数即可，$2^a5^b$在$10^{18}$内个数不多（有兴趣可以自己算算，简单口算一下：$a+2b \le 60,60 \times 30=1800$，上界是$1800$，平方暴力枚举十分安全），使用$std::map$记录并暴力枚举即可。

E.金币竞赛（中等）
这是一个十分简单的数据结构题目，重点就是计算斜前缀和。
记录$S(i,j)=\sum_{k=1}^j A_{ik} + S(i+1, j-1)$，每次询问差分一下即可。
不小心被$O(min(n,m))$的解法冲过去了，白给...

F.简单计算题（困难）
记$s(n,k)=\sum_{i=1}^n i^k$

$$\begin{align*} f(n,k)&=\sum_{i=1}^n\sum_{j=1}^n(\frac{lcm(i,j)}{gcd(i,j)})^k \\ &=\sum_{i=1}^n\sum_{j=1}^n (\frac{ij}{gcd(i,j)^2})^k \\ &=\sum_{d=1}^n \sum_{i=1}^{n/d}\sum_{j=1}^{n/d} (\frac{idjd}{d^2})^k [gcd(id,jd)=d] \\ &=\sum_{d=1}^n \sum_{i=1}^{n/d}\sum_{j=1}^{n/d} (ij)^k \sum_{d'|gcd(i,j)} \mu(d') \\ &=\sum_{d=1}^n \sum_{d'=1}^{n/d} \mu(d') \sum_{i=1}^{n/d/d'} \sum_{j=1}^{n/d/d'} (id'jd')^k \\ &=\sum_{d=1}^n \sum_{d'=1}^{n/d} \mu(d')d'^{2k} (\sum_{i=1}^{n/d/d'} i^k)^2 \\ &=\sum_{i=1}^n s(n/i)^2 \sum_{d|i} \mu(d)d^{2k} \end{align*}$$

令$f(n)=\sum_{d|n}\mu(d)d^{2k}$，显然是个积性函数，可以用线性筛求。$i^k$也是积性函数，也可以用线性筛求，总的时间复杂度为$O(n)$。
稍微有点卡常，尽力优化吧！

G.hry打小怪兽（困难）
首先显然每次选定一个怪兽之后，将其击杀是最优解。
显然hry击杀30个怪兽之后就无敌了，剩下的怪兽都是一击必杀，所以hry要做的就是在前30次击杀怪兽中尽量少受伤害。那么问题就变成前三十次击杀分别分给哪个怪兽，那么就是一个最小权值匹配问题，用最小费用流。可以建出一个$30 \times n$的二分图，边权为第$i$个回合打第$j$个怪兽需要的回合数$-1$再乘上怪兽的攻击力，跑最小费用最大流即可。时间复杂度$O(30\times 30 \times n \times log(30 \times n))$。
貌似不小心卡了部分最小费用流板子...

H.两面包夹（简单）
定位是个简单题，但是写起来有比较多需要注意的地方。
首先如果有边平行于$x$轴，那么肯定无解，否则肯定有解。对左右两边分别计算，求最上面的边和最小面的边的交点，如果在城堡和线的中间（不在线上），一个炮台即可，否则需要两个。
定位是简单题，但是不小心变成了难题...

I.ykmnb（签到）
$std::next\_permutation$秒之。

J.长寿星人（签到）
$a+1$过程中肯定是最右边连续若干个$1$变成0，然后左边$1$个$0$变成$1$，模拟二进制加法即可。有更取巧的做法$f(i)=bits(i \oplus (i+1))-1$，$bits(i)$表示$i$的二进制位数。

K.长寿星人2（签到）
判断一个十进制数是否被$3$整除，等价于判断其十进制各位相加之和是否被$3$整除。

L.长寿星人3（困难）
首先简化方差公式$var(a[1,...,n])=\frac{n\times \sum_{i=1}^na_i^2 - (\sum_{i=1}^na_i)^2}{n^2}$。

枚举位置$i,j(i < j)$的贡献。
（1）在平方和中，假设$i,j$是随机选定的数中相邻的两个，那么$(A_j-A_i)^2=A_j^2+A_i^2-2A_iA_j$，总共有$C(n-(j-i+1),m-2)$种。
（2）在和的平方中，假设$i,j$是随机选定的$m$个数中的左右端点，那么有$(A_j-A_i)^2=A_j^2+A_i^2-2A_iA_j$（恰好和上面一样），总共有$C(j-i-1, m-2)$种。
综上，枚举$j-i$，可以比较方便的算答案。问题在于$A_iA_j$的计算，显然符合卷积的形式，用$NTT$计算即可。
复杂度$O(nlogn)$。

M. 长寿星人4（困难）
据说是$splay$模板题，但我并不会做，逃~