标题统计

送分题。

空格和回车不算在内,每次都读取一整个字符串,统计所有字符串的长度和即可。

龙虎斗

送分题。

根据题目的意思,算出初始的分数。

枚举兵降落在哪个位置,分别计算代价,去最小值的位置。

摆渡车

比较基础的dp,但可能对初中生的要求还是算高的。

先考虑暴力的dp,\(f[i][j]\)表示前\(i\)个人,其中发车时间在第\(i\)个人之后\(j\)分钟所需要最小的等待时间

这样的状态第一维\(\le 500\),第二维\(\le 500*100\),状态太多,直接转移的话,不仅有MLE的风险,还有TLE的风险

再仔细考虑一下,大部分状态是无效的。

其实每个人的等待时间最多是\(m\)。即在这个人到达前一分钟发车,那么他的等待时间是\(m\),其余更多的状态显然不是最优的,直接忽略即可。

这样我们就把状态压下来了,\(f[i][j](i\le 500,j\le 100)\),这个时候直接暴力转移就可以了。

时间复杂度\(O(n^2*m)\)。

对称二叉树

似乎就是一道纯粹的暴力题啊?只需要把题目理解清楚。

首先我们考虑以\(x\)作为根结点的子树在什么情况下是对称的,显然,如果\(l[x]\)子树和\(r[x]\)子树对称,则以\(x\)作为根结点的子也对称

更一般地,对于一个一个节点\(x\)的,如何判断\(l[x]\)子树和\(r[x]\)子树对称,根据所有子树旋转的原则,只需要\(l[l[x]]\)子树和\(r[r[x]]\)子树对称并且\(r[l[x]]\)子树和\(l[r[x]]\)子树对称即可。

那么我们枚举所有节点作为根结点是否是对称二叉树,dfs判断即可。

这样暴力复杂度的很有疑问的,我们不妨来看一下。直观上感觉,直接枚举所有的节点,然后判断的话,复杂度应该是\(O(n^2)\),其实不然。

一棵树的形态已经定了,我们每次是对一个节点作为根结点的子树进行判断,显然最坏的情况就是满二叉树的情况,因为如果不是满二叉树,很容易就能判断到冲突,而直接停止判断。

这样的情况下,我们判断满二叉树总复杂度是\(\Theta (\sum _{i=1}^{d} (2^{i-1}*(2^{d-i+1}-1)))=O(nlogn)\)。

所以这道题目直接这样暴力的均摊复杂度是\(O(nlogn)\)。暴力过去没有问题的。

考场上写hash的肯定是亏了啊?

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注