ACM学习：搜索题学习心得与比赛结果反思

在上一周里，为了完成96道搜索题的任务，我更多的偏向于看题解，对于博客，则更多的偏向于学习难题中涉及到的知识点的理解，如：拓扑排序，异或和字典序等等。96道题，由于自身能力和时间等原因并未全部完成，只完成了50多道，一般对于同类型的题，我会选择其中一个比较突出的题目进行AC，对于一部分我学习过后有明确思路的题，进行了题解口胡，对于大部分只明白题意且看过题解，但理解不深刻则浅尝辄止。单描述很难直观的展示成果，就直接上图吧：

在这些各有特色的题解中，我不仅学习了很多新知识，而且对旧知识有了更多了了解与深入，同时也发现了不同的知识，思想，数据结构之间的共同之处，并在这其中发现了我个人打代码的缺陷，那么，这篇博客就以这三个方面进行叙述吧。（由于是总结，不太涉及各类代码，只阐述自己的收获，可能比较单薄）

目录

一.旧知识的深层掌握

二.新学习到的知识

三.个人题解分析

四.上周几场比赛反思

一.旧知识的深层掌握

1.string的多元应用

对于string，我之前的理解都十分浅薄，仅仅认为它是一个非常方便的字符串类的数据结构，但当我上周在学习一道关于二叉树的基础知识：前中后序排列 的题目时，我发现了它的真实面貌：他是一个类！

题目索引：

P1030 [NOIP2001 普及组] 求先序排列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1030在这道题的AC过程中，我真真正正的明白它的用处与便利，之前只是简简单单的利用string创建变量（或者说对象？）以排除字符数组的冗杂，现在我才更深刻的明白了，它作为字符数组的上位替代，有着多么便利的功能，这里简单的列举几个我认为很常用的操作：

tips:带头文件：#include<cstring>

string.push_back() ：在一个 string 对象后面附加一个字符

string.find()：查找字符串中的某个字符

string.rfind()：从指定位置开始查找字符串中的某个字符

string.insert()：对字符串进行插入

string.empty()：判断字符串是否为空

str.size()/str.length()：获取字符串的长度

这样，以后对于各类对字符串的复杂函数可以更加有效快捷的创建了，填补了我在这方面的一个知识空白。

2.typedef以及memset用法

memset()函数其实自己早就开始使用了，但真正的认识到它的作用还是在上周三的一场比赛中，相对而言，直接在数组后加{0}确实简单方便，但如果要在函数或者循环中，对一个数组重复使用清零，还是memset更好一点。

而对于typedef而言，它与宏定义比较相似，都是用自己定义的东西去替换之前存在的东西，为编程提供便利，但这个确实与宏定义有区别，比如typedef创建的符号名只限于类型，不限于值；而且，它可以避免一些不易发现的错误，如：

typedef int*  InP;

InP pa, pb;

可以避免出现定义成一个指针，一个变量的情况

今后在面对更复杂的情况时，也确实更容易解决。

3.暴力枚举

枚举是自己在寒假时看书自学的，因此记忆不深刻，不过在这次的搜索例题学习时，发现了很多适合使用枚举的情况，比如可以在举例次数较少时，强制枚举AC，又或者利用循环，重复枚举得到答案，但当然，这也只是解决的一种想法，并不能真正的去解决问题，但今后遇到没思路的类型题时，未必不能这样一试。

二.新学习到的知识

原本自己困在一些新知识的囚笼里，没法下手，但好在自己在看了一些博客和听老师讲解后，对一些题大概有了思路，接下来，就简单聊一聊自己在题解中发现的新知识和知识间的联系。

首先，最令我印象深刻的就是二叉树和图（论），这两个都是有结点和路径（边）的存在（当然，堆也有），在搜索例题中广泛存在，很多题目都涉及到了这个知识，比如P4017 最大食物链计数、P6635 「JYLOI Round 1」箭头调度、P2853 Cow Picnic S、P3884 二叉树问题和P6591 植树等等等等。这些题目大多都是给出结点和边数，要求进行连接或求结点权值累加的最值等问题，但在对题目进行思考的过程中，我发现二叉树和图有很多相似的点，比如，都拥有结点和边，都可以与搜索结合，都能产生多种不同的解，并衍生出字典序问题等。当然，其中有些题会更适合树或者图中的一个，有些用堆来处理也会更加方便，而这正好强化了我关于这三个知识点，能够更清楚的理清题的具体要求，让我整理出自己的解题思路。

还有一个新的方面，是关于全排列的问题，这是一个与字典序结合出题的高配知识点，虽然确实不方便，但利用树的知识处理，也是很方便的。因为经典例题尚未AC，就先不再赘述，等下次与并查集一起在说一遍吧。

三.个人题解分析

这次的题库我只AC了4道题，相对于阅读量而言确实不多，但其实是代表了一部分的题型的。像连通块，N皇后等等，之前都只是进行了思路口胡，但真正下手才发现确实不是一回事。比如，自己对整体思路一般偏差不大，但落在细节上就会有缺漏。如：

    for (int i = bei; i <= end; i++)
    {
        sum += rec(k - 1, all + x[i], i + 1, end);//不能把all+x[i]提出来算
    }

P1036 选数中这一部分代码，刚开始我确实不理解先将sum++后再递归调用函数为什么行不通，后来才发现，是回溯会出错。要修改的话，可以尝试写成

    for (int i = bei; i <= end; i++)
    {
        sum +=x[i]；

        rec(k - 1, all + x[i], i + 1, end);

        sum -=x[i];//保证回溯时原数值不变；
    }

还有，还是自己看题的粗陋，比如P1331海战中，

void check(char map[MAX][MAX], int a, int b)
{
    map[a][b]='*';
    if (a >= 0 && a < r && b >= 0 && b < c) {
        if (map[a + 1][b] == '#') {
            check(map, a + 1, b);
        }
        if (map[a - 1][b] == '#') {
            check(map, a - 1, b);
        }
        if (map[a][b + 1] == '#') {
            check(map, a, b + 1);
        }
        if (map[a][b - 1] == '#') {
            check(map, a, b - 1);
        }
    }

没必要把map[a][b]='*';分别放入每个if语句中，不仅减少了打代码的累赘，还能使每一个“#”都只被数一次，不会被多数，确实非常细节（在此感谢帮我的大佬，明翰同学），这样就解决了我困扰我一个多小时的问题。

可以看出，我在编程时的一些陋习依然存在，比如看题不全等等。这也是在学习过程中不断警示我的一个点。不过，更多的收获是在看大佬们题解时独特的思路，有的通过数学原理分析，有的通过执着的枚举，有的通过巧妙的构思，但无论如何，都对我有很多启迪。

四.上周几场比赛反思

上周参加了几场比赛，基本上每一场都是只出了一道题，特别遗憾的是那个div.4的比赛，自己第一题执着于用搜索，导致浪费了大半个小时时间，而且后两场，自己都是已经完成了99%的路，却都只差一点，第二个在思考为什么AC错误时因为没思路，直接去了第三道，但因为数次更改第二道都不理想导致心情急躁，最后二三道都没AC，这是一个教训，也是一个警醒，如果我一直是这个心态的话，是完全没法参加比赛的，一旦心情不佳影响思路，只会越来越差，也许，我不止应该学习知识，更应该学会如何调理自身，更好的运用知识。

这场比赛告诉我，我的代码基础和思路现在都是有局限的，应该学会稳扎稳打，不要急。他强任他强，清风拂山岗，把自己每一步路走好，才是能取得更好成绩的前提。