库特

分类

未归档(22)

/ 注册

全部文章（共4篇）

牛牛与围棋

100分解法本题算是一道构造题。首先对于题中n个棋子对气的定义，显然n个棋子气的上限是4*n,但是我们不是在问上界，并且n的范围还是1e18，所以考虑如何用o(1)或者o(logn)的时间复杂度构造出下界。我们把下界如何确定并如何证明我们得到的数是下界分为以下几个步骤 1.首先，如果要想气最小，n...

2020-07-22

1 817

牛牛浇树题解

100分解法比较基础的一个差分题。可以选择离散化m个区间去差分，时间复杂度o(mlogm)，空间复杂度o(m)。当然，由于本题n较小，也可以不进行差分，时间复杂度o(n)，空间复杂度o(n)。讲一下具体的思路。首先如果我们每棵树都没有浇水的话，m天后每棵树高度都为m。如果m是奇数的话，我们找到浇水...

2020-07-22

1 879

warrant

做法一（时间复杂度o(n),空间复杂度o(1)）首先如果一个单词中没有重复字母是一个比较简单的dp问题。比如如果找单词为“air”的子序列，我们只需要开一个dp[3]数组，dp[0]记录前面“a”的个数，dp[1]记录前面为“ai”的个数，dp[2]记录前面“air”的个数即可，更新分别以dp[0...

2020-07-05

0 705

幂运算与阶乘

30分做法因为n最大是10，所以n!最大只有3628800。所以直接用裸的快速幂即可。 100分做法首先此时n最大为20，显然n!已经达到longlong范围了，而快速幂中需要两个longlong的数相乘会爆longlong，此时介绍四种做法。（四种做法空间复杂度均为o(1)，下面不再赘述）。 ...

2020-07-04

0 946