牛客小白月赛20

第一次出正式比赛的题目，感谢大家参加这场比赛，比心.jpg，对题目有任何疑问欢迎牛客私信我。
std在题解的最后。

By Keven

A、斐波那契

暴力算出前n项平方和的复杂度是 O(n) ，显示是不能通过本题的，如果对斐波那契比较了解的话，不难得出 $\sum_{i=1}^n fib_i^2 = fib_n * fib_{n+1}$ ，具体证明参考 https://blog.csdn.net/lanchunhui/article/details/51840616 ，所以现在题目就变成了求 $fib_n * fib_{n+1}$ ，到了这里就可以用两次矩阵快速幂求出 $fib_n$ 和 $fib_{n+1}$ ，然后直接输出就行了。

B、最大边长

固定边长的长方形里面放入三个变成相等的正方形，只有两种放***使正方形边长最大

所以最大边长就是两者的最大者，注意只输出整数部分，小数部分舍去。

（PS：二分也可以通过此题，一血就是二分通过的）

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42551244

C、球的表面积

首先，判断两个球的位置关系，若内含，直接输出最大的球的表面积，若相离，直接输出两个球的表面积和。

若相交，由图可以看出两球的相交部分是两个球缺（什么是球缺）https://baike.baidu.com/item/%E7%90%83%E7%BC%BA/1902201?fr=aladdin

所以我们只需要算出两个球失去的表面积大小，就可以得到答案。

我们已知 $r,r',dis$ ，由三角形 $Aoo’$ 和余弦定理，可以求出 $cos\alpha$ 和 $cos\beta$ 的值，由三角形Abo中 $cos\alpha=dis1/r$ ，我们可以求出 $dis1$ ，由于球缺曲面的表面积公式是 $S=2πRH，H=r-dis1$ ，就可以得出球o失去的表面积，同理，可以得出球o’失去的表面积，用两个球的表面积之和减去两个球失去的表面积就可以得到两球相交之后的表面积。

（PS：由于验题人有一个数据产生了1e-6的误差，所以spj放到了四位小数）

D、3的倍数

由于n的范围较小，所以直接枚举所有情况就可以了。

考虑状态压缩，把每个字符串用一位 0/1 来表示，其中1表示该字符串取，0表示不取，所以我们只需要n位 0/1 就可以表示出所有状态了，对应的这些状态都可以用 [0,2^n] 的二进制形式来代表，所以我们只需要枚举所有状态，对于每种状态，判断一下取的所有字符的每个字母总的出现次数是否是3的倍数，若是，更新答案。

E、区区区间

题面暗示线段树

考虑第一个操作，将区间设置为等差数列，若区间需要更新，我们可以在O(1) 的时间求出当前区间的左端点的值，并在 O(1) 的时间求出当前区间的和（等差数列前N项和），考虑重复更新，我们只需要设置一个懒惰标记为当前区间左端点的值，在重复更新的时候，覆盖之前的懒惰标记就可以了。

考虑第二个操作，在第一个操作的同时维护一个区间和就可以了。

F、进制转换

如果只会C语言的话，这题没有看起来那么签到，首先，你需要找一个C++大数的板子或者用数组模拟大数，如果没有的话可以去通过的C语言代码里面找一个（当然，你会Java/Python当我没说），然后你就可以暴力算出这个数字的10进制形式，然后再将他转化为k进制并输出。

G、快乐风男

这题就是让求一个最长上升子序列，若有多个最长上升子序列则输出字典序最小，显然二分是不能通过本题的，因为二分不能维护字典序最小这一特性，考虑线段树，以每个位置的值作下标，每个位置的答案作为该下标的值，对于每一个位置，只需要求出 $[1,a_i]$ 里面的字典序最小的最大的值，和对应的下标，那么当前位置的 lis 就可以从求出的下标转移过来。

H、好点

题目说明了不存在横坐标相等或纵坐标相等的点，所以显然纵坐标最大的点一定是“好点”，我们考虑将所有点按照纵坐标降序，横坐标降序的方法排序，那么第一个点一定是“好点”，依次遍历剩下的所有点，若当前的点的横坐标大于上一个“好点”，那么这个点也一定是“好点”。（横坐标大于上一个“好点”，说明纵坐标大于它的点都在它的左边，由于我们是按照横坐标排序，并且这个点横坐标大于上一个“好点“，所以，横坐标和它相等的点，必定不在它的右边）

I、小小小马

简单思维，若 $n,m>=3$ 并且 $n,m$ 不同时为 $3$ ，都是可以走遍全图的。

注意特判 $n=m=1$ 的情况。

当然，考虑到小白月赛，所以大家如果不想思维的话bfs也可以通过本题。

J、dh的帽子

这题就是一个裸的数位dp，如果你不会数位dp可以先去学一下。

一般来说数位dp都有一个上界，可以方便剪枝。这道题还需要判断下界，同样也是用于剪枝。首先转换成二进制可以方便计算。递归的时候每一个数多加一种状态ismin判断数与下界的关系，三重for循环枚举三个数字当前数位的情况取0或者1，如果前面的数位与下界完全相同，那么当前数位只能取大于或等于下界当前数位，否则当前数位就可以任取。然每次判断每一位是否满足 $a\oplus b\oplus c==a|b|c$ ，如果满足就继续下一位。不满足就跳出。