D

给定一个数m(1e15),找出一个小于等于m的数X,每次减去一个比之小的最大的立方数,直到为0
求减的最多的次数,在此情况下,求最大的X

贪心

我们每次考虑当前数取多少
若取最大的a($a^3 \leq m < (a+1)^3$),则剩余部分为$m-a^3$
若取第二大的数,起始值最大为$a^3 - 1$,剩余部分为$a^3 - 1 - (a-1)^3$
若取第三大的数,起始值最大为$a^2 - 1$,剩余部分为$(a-1)^3 - 1 - (a-2)^2$
很明显$a^3 - 1 - (a-1)^3 > (a-1)^3 - 1 - (a-2)^2$,因此取第二大的数一定比第k(k>2)大的数更优

因此我们有两种决策,取$a^3$或取$(a-1)^3$,直接写一个递归就可以了

复杂度$O(m^{\frac{1}{3}}log(m))$

E

nn的方阵,有一些连通块,要求选择一kk区域,使它们都连通,求此时最大的连通块的大小

二维滑窗

先dfs出连通块的信息
然后移动k*k的块,维护与之相连的连通块

复杂度$O(n^2k)$