传送门:https://ac.nowcoder.com/acm/contest/3282#question

A.斐波那契 - 矩阵快速幂模板

证明:


 --- 两个边长为1的正方形的面积等于它俩组合起来长方形的面积

那么递推来就有:

...

由数学归纳法可知:

从几何出发:前n项斐波那契数列为边长的正方形可以拼成一个边长为的长方形.

B.最大边长

题意：给你一个长方形，问你最大能在里面摆多大的三个一样的正方形，使得三个正方形不重合.

思路:只有两种摆法，摆成一行，还有就是摆成一个角.第二种二分解决即可.


C.球的表面积(待补)


D.3的倍数

思路:发现n很小，最大只有15，状态压缩暴力跑完所有情况比较最大值即可.

E.区区区间

线段树的题目，待补.

F.进制转换

大数模拟模板的题，但java里有进制转换现成的函数，所以没写出来真的可惜了

注：s^200 就是代表这个数只有两百位,一位就代表一个s进制下的值。


G.快乐风男

线段树的题，最后的时候偷懒用树状数组搞，然后写挂了。待补，还是有写的价值.


H.好点

题意:给若干个点(x,y),问有多少点右上方没有点，即不存在

思路:

跟题解写的不一样，个人感觉挺像偏序题的，

自己的思路：用树状数组+离散化去写的，CDQ分治也可写。（想复杂了）

AC代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42553754

CDQ分治:(待补)

题解的思路：没懂。。还用了map啥的


I.小小小马

题意：给定一个棋盘，已知棋盘的行数和列数是n,m，每个整数坐标处都有一个糖果，Keven初始在棋盘的左下角 (1,1)(1,1)(1,1)出发，并且Keven每次只能跳 ”日” 字，假设Keven可以跳无数次，但不可以跳出棋盘，现在 Keven 想知道他能否拿到棋盘上的所有糖果。

思路1：看到2000*2000的数据果断dfs了。

思路2:如果n,m再大就不能这么写了，找规律发现n,m>=3且n,m不同时为3时可遍历全图,特判1,1

过程：

首先: n <3 或者 m < 3，马只能横着跳，必不可能遍历完全图.

考虑3x3的情况：

我们发现只有点(2,2)不能遍历到.把马跳的范围看成以3*3为单位.现在假设多一行或者一列,那么可以看成是两个3*3的网格上下或左右重叠在一起.这样我们可以借助新增出来的一列或一行来转化这个网格来到达之前到达不了的地方.自己分析一下就懂了.

J.dh的帽子

数位dp的题，跟南昌站那道题非常像，寒假必抽时间出来把它给补了！

K.Hello World

题如其名。。签到题。

不过，如果只有唯一输出的情况下，其他数据其实可以不读入的，这原理当时没想到。撒了。