Delete

每次删除最长上升/下降子序列,删500次就行。

以为保证1到n的排列,利用树状数组就可以nlogn找到序列。

O(500nlogn)

Floor

sqrt(5)前的系数是斐波那契数列,f[1]=1,f[2]=3;

然后矩阵乘法求f[i].

经过打表找规律可以发现,ans[i]=f[i]/2-((n&1)^1);(偶数-1,奇数不变)

具体推的过程似乎是利用方程 x^2-x-1,我也不是太清楚

Permutation

不难发现一个数x在矩阵第x排出现n-x次,所以一个有解的矩阵只有n和n-1的位置不确定,所以只有两个解,从中找到字典序较小的解,先检查这个解是否是1到n的排列,再带回矩阵里检查即可。

复杂度O(n^2)

String

暴力竟然能过…

暴力写法:每次暴力比较,当长度为奇数时 return false.注意短路运算符的使用可以减小搜索次数以减小复杂度。

正解:分别对两个序列排序:递归,对于左右两个子串,让字典序小的排在左边,这样就可以找到它字典序最小的相似串,如果这两个串相等,则两个原串相似。

Number

数位DP

//Seal到此一游

 

 

T1

这道题很容易想到处理前缀来处理区间,但在这里有一些问题。

首先就是一个右括号在[l,r]里面而与之匹配的左括号在[1,r)里面,这样就会出现错误,我们只要把每一对的值记录在左括号就可以处理好。

但这样的话对于一个左括号在[l,r]里面,而与之匹配的右括号在(l,n]里面,这里我们用离线处理的方法,对于这种的每一对,我们还没处理它就行了。

代码实现:

 

百题纪念~

cyl已经在内网刷了100道水题啦

最近几道题的题解

T3

对于前序遍历的每一个节点都把他当做一棵子树的根,在中序遍历中找到这个点,然后在这段区间中递归,每个点我们只把它当成一次根,在dfs后输出即可。

具体可看代码实现

T4

线段树维护区间剩多少人

直接看代码吧

T5

出题人恶意卡trie树…

(…)

正解?:链式前向星存trie树,强行时间换空间

 

T1

这个问题,我们可以称作为4+7问题233…

对于这一张1e9的图只有1e5的点有用,所以我们可以压缩这个图

对于一个大于等于18的数,是一定能分解成4和7的和的(证明过程略)

所以对于两个相邻的点,如果他们的距离大于18,我们就把他当做18,然后压缩后的图最大为2e6,即可dp求解

T2

吐槽:固输最大值+1 可得60分,数据是真的强大

模拟的时候我自己写了个树状数组,然后很神奇的过了80的点

正解其实就是用了奇技淫巧的模拟

模拟每一次操作,有两个0就合并,最后统计还剩多少个0就AC了

T3

我在这里就说一下m=0的30分怎么得

我们任取一点为根,dfs处理出每个节点的子树大小,以及这个根到所有点的距离之和。

第二次dfs,对于一个已知所求答案的点,向他的儿子转移,不难发现他与儿子的距离和只差为k*e[i].w

手动找规律可以发现k为n-ch[i]*2(ch[i]是以i为根的子树大小)

这样O(n)dfs预处理+O(n)转移即可30分

从’++……++’开始bfs,只不过入队的条件类似于SPFA,需要relax再决定入不入队,最后访问dis[0]即可。

在这个过程中可以直接利用2进制表示状态来进行转移

这道题数据范围很小,有很多种写法,暴力、哈希、trie树复杂度都能过,对于这道题我采用STLmap,把string映射成bool,即可轻松AC