几道hihocoder不会做的题

1. https://hihocoder.com/problemset/problem/1433?sid=970287 boarding passes,不会做,看的别人的代码,现在还不是很理解。

2. https://hihocoder.com/problemset/solution/970330 ac自动机,对trie,ac自动机的理解还不是很深刻!这道题目是找每一个字符里面的最长匹配。ac自动机,是对trie加上了失败节点,也就是到当前为止,所能匹配的最长后缀,但是这个最长后缀不一定是keywords的完整单词,所以要不断的找以它结尾的最长的keywords,这个可以通过失败节点查找,直到根节点为止。这道题很有意思,进一步加深对ac自动机的理解,其实有点后缀数组的概念,我也不是很懂哎!

3. https://hihocoder.com/problemset/problem/1444?sid=970386 这道题目,我看完不会做,但是可以得到长度为1-8的答案,(通过上一题的枚举答案),然后拿出神器http://oeis.org/,查找通项,得到公式,直接编写代码,就a了,但是,这样,老感觉有作弊的嫌疑,缺少自己思考的过程,还需要自己的枚举方法。看了几个答案,实在想不出来是怎么推导出来的,有的是枚举分割数目,然后对这个数目求全排列,这算是一种解决办法!我突然想到:我好笨啊,既然是dp,为什么不枚举最后一个部分是什么,然后缩小问题规模呢,然后再翻看前面的别人的代码,才恍然大悟,就是这样的思路!感觉自己真是蠢,这么简单的dp的方法都忘记了!然后码代码,就过了!

哎!看来还需要加对这个方法的理解!就是枚举最后一部分是什么,然后看一下能不能变成规模较小的问题,然后利用已经算出来的求解! 转化成规模较小的问题这个过程需要仔细分析,但是首先你要有枚举部分,减少问题规模的想法!

4. https://hihocoder.com/problemset/problem/1451 这个也是,不会,上网站查找通项,得到公式编写,其实这道题目的方法是:打表,找规律,但是规律在n>=16以后才出现,也不容易发现!

原文地址:https://www.cnblogs.com/y119777/p/6227272.html