【本周总结：搜索，比赛，心得，新发现】

【本周总结：搜索，比赛，心得，新发现】

一、搜索

（一）深搜理解

1.认识：拿背包问题举例，有限的空间，如何装入价值最大的物品。越基础，越经典。我写代码有个习惯就是自己模拟计算机运行一遍，看看各个步骤是如何开展的，于是我自己走了一遍深搜，遇到的第一个问题就是，搜索已经到底了，return 是回到哪里呢？之前学的都是“一维”函数，返回主函数，明显深搜不是，这个问题我钻牛角尖困扰了我一阵，当中午和队友（也是师傅）讨论完发现，深搜就是个层层嵌套，从上一层的哪里进入，下一层结束后就返回那个入口，继续执行入口之后的操作。我俩拿全排列问题为例，把深搜的过程全部写了一遍，真是恍然大悟，原来的问题（eg:每一个数是怎么被搜索到的）迎刃而解！写过程的时候发现，深搜像一棵树，主干不变，每个主干有两个分支（拿0-1问题举例），不同点在于，由主干到分支，会一直到支路末梢（认准一条路走到底），那么执行完这一分支后，是该层的数值的叠加，带着值返回上一级，其结果作为上一级的另一分支的新节点（eg:4=1+1+1+1,4=1+1+2）。每返回一层就从后往前叠加一次。潜在风险：递归层数过多可能会超时！

综上，用模板套题，理解运行方式，不需要硬钻如何实现（限制条件没错、剪枝没错。结束条件都对的话应该问题不大）

（二）.应用：

（1）（dfs+vector(用于找合适的单个元素、记录方案)）

【从N个数里选K个数】限制：K个数的和为n，找平方和最大的一组序列。

        要做的事：找出和为K的序列，记录方案

        我的理解：记录现在的位置、已选数总和、平方和、已有序列内元素个数都视为该位置元素的外部属性，也是深搜每个数伴随的形参，也是判断return 的条件，而元素自身的值是内部属性。只有外部属性符合条件后才内为其赋值，

        变形：N中每一个数可以被选择多次，再选择K个数。---》先搜索完当前元素再换下一个

（2）（dfs+回溯）健康的荷斯坦奶牛 Healthy Holsteins

【题目大意】：输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少，而且如果有多个解，输出饲料序号最小的。

法二：（迭代加深）

【思路】因为题目中要求饲料越少越好，所以我们可以借助迭代加深的思想，先限制每一次搜索的深度，搜到一定的深度就返回，即每一次选择的饲料数量，选择了足够的饲料就返回，然后判断是否存在一种这样数量的组合，满足题目条件，这样的话能把最优解放搜在前边，不需要任何的剪枝就能AC。

（3）（循环打印，坐标分解，dfs）南蛮图腾

【技巧】坐标分解，先把基础的小三角写出来，观察x,y变化的规律，每次搜索变化初始打印小三角的位置，实现大三角的整体输出。

（4）（回溯，搜索，标记）八皇后 Checker Challenge

【题目大意】有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。（有点类似数独游戏，但是没本题困难）

本道题最重要的就是记录下皇后占领的格子（打标记的思想），通过此判断下一个皇后是否可以在某个位置，如果可以，则继续搜索下一个皇后可以在的位置，如果不行，则清除标记回到上一步，继续搜索；

（5）（回溯，搜索，标记）P1123 取数游戏

        额外收获：memset()--->在做每个数据前都要初始化数组

二、小技巧总结与新发现（又学到了）：

1.竞赛中有大量输入样例时，可通过此避免重复输入，要在stdio.h的文件下。

freopen(&#","r",stdin);

://t.csdn/1h4mI

2.abs() 、fabs() 、fabsf()的区别在于，

abs()返回整形（int）数据的绝对值，fabs()返回浮点型数据（double）的绝对值；fabsf（）返回float型数据的绝对值；

三者都要在<cmath>的头文件下。

3、://t.csdn/mrmDtC++ for(auto &a:b)、for(auto a:b)、for(const auto &a:b)

可以替换数组循环输入

三、心得体会

1.循序渐进，大纲上跟着老师的步伐（虽然也强调过这远远不够，但是先做好当下在进一步拓展），遇到的不懂得点，找相关的上一级开始理解，实践，循序渐进虽然速度慢但确实最扎实的方法。平时题解里遇到的新鲜解法注意积累学习，人家为什么这么写？他是怎么想到的？

2.勤能补拙，不要降低对自己的要求

3.比赛时，自己写的代码怎么看都对，就是运行测试错误，可以先重新读题，看看是不是落了什么条件。头脑要清醒，抽丝剥茧，简化题目。找规律！