【团体程序涉及天梯赛】L1~L2实战反思合集（C++）

 实战反思汇总记录

仔细审题，想好再写

L1-104 九宫格 - 团体程序设计天梯赛-练习集

易忽略的错误：开始习惯性地看到n就以为是n*n数组了，实际上应该是9*9的固定大小数组，查了半天没查出来

L1-101 别再来这么多猫娘了！ - 团体程序设计天梯赛-练习集

New：最后那两个长字符串测试点的处理，不要在一开始就将违禁词替换成“<censored>”，而是先替换成“-_-”这样的比较短的字符串，否则违禁词多的时候，不断地改成长替换词，会加重下一次查找操作的负担。故先替换成短的，最后在输出前再替换成题目要求的

string类型常用方法

getline(cin, str);//在此之前如果单独用过cin>>, 则需要在二者之间用一次getline“清空缓存”，才能够成功用getline接收

int pos = str.find( to_find, start_pos);

str.replace(pos, len, "to_replace_with")

 L2-001 紧急救援 - 团体程序设计天梯赛-练习集

尝试DFS：开始使用DFS来遍历求解，但 DFS 存在大量重复计算，像同一节点会被多次访问并重复计算路径信息，导致时间复杂度高，部分测试点未通过

改用迪杰斯特拉：为了求解，设置了很多的辅助数组，对于他们本身的初始化、以及对于起始点S的初始化赋值容易出错，需要小心

迪杰斯特拉相当于是用一次过程找出了所有点的信息，最后只需要按要求输出D对应的信息即可

迪杰斯特拉算法，通过储存每个点的信息，为后续的其他点的信息求取打下了坚实基础，用空间换取了大量时间

图论问题，应思考是否可以在dijistra的基础上改进来实现

 L2-002 链表去重 - 团体程序设计天梯赛-练习集
//混乱时，先文字写出大致的思路，然后将这思路一条条实现
//printf("%05d\n", cur_node.nxt_address);//补零输出
//段错误一般是数组访问越界导致，比如Del为空时，Del[0]是非法访问

L2-003 月饼 - 团体程序设计天梯赛-练习集

//需要结构体的存储一般可以拆成多个vector来操作，但涉及到依据某一项来整体排序就不能分别存储，结构体起到了打包排序的效果

struct Node{int a;bool operator<(const Node& other)const{return a < other.a;}
};

//精度要求高：

警惕考虑小数的问题：用double存储，且注意，两个int相除自动按int存储，要用double强转才能变成double

//int与double做乘法，得到double（向精度更高的转化）

L2-004 这是二叉搜索树吗？ - 团体程序设计天梯赛-练习集！重

//特殊：独腿二叉树，如pre = {2，3，4}，递归函数用if(root == tail) return；无法识别这种二叉树，需改用if(root<tail)return ;
// 用ismirror来将一般二叉树和镜像二叉搜索树的情况对应操作放在同一个函数中（详见总结博客）

二叉树三种遍历的常用性质

前序遍历

• 根节点优先访问：前序遍历顺序是根节点、左子树、右子树，所以序列中第一个元素就是根节点的值，本题就是利用这一性质确定根节点，再根据二叉搜索树的性质划分左右子树。
• 子树顺序性：前序遍历序列中，在根节点之后，先出现的是左子树节点值，后出现的是右子树节点值，二叉搜索树据此可找到左右子树的分界点。

中序遍历

• 二叉搜索树的有序性：在二叉搜索树的中序遍历序列中，节点值是按照从小到大的顺序排列的。在判断一个二叉树是否为二叉搜索树等问题中，可通过检查中序遍历序列是否有序来判断。
• 定位节点位置：结合前序或后序遍历，可以确定节点在树中的位置。如已知前序遍历找根节点，再通过中序遍历确定根节点左右子树的节点范围。

后序遍历

• 根节点最后访问：后序遍历顺序是左子树、右子树、根节点，所以序列中最后一个元素是根节点的值。在根据遍历序列构建二叉树等问题中，可据此确定根节点。
• 左右子树完整性：在后序遍历序列中，根节点的左右子树的节点值是连续出现的，且先左后右。可以利用这个特性来划分左右子树，进而递归处理。

一般已知一种序列不能唯一确定另一种序列，但结合二叉树的某些特殊性质可以

比如满二叉树，完全二叉树，二叉搜索树等

L2-005 集合相似度 - 团体程序设计天梯赛-练习集

遍历语句： for(int num : A) cout<<num// 可以方便地遍历常见迭代器中的元素

时间优化：set会对存进来的元素进行排序，因此相对较慢，不需要这一点是可以用unordered_set;

不熟：容器嵌套 vector<unordered_set<int>>sets;

L2-006 树的遍历 - 团体程序设计天梯赛-练习集 //已知后和中序构建二叉树，然后层序遍历

// Node(int x): val(x), left(nullptr), right(nullptr){} //struct Node中
// Node* cur_node = new Node(value);                  //调用

二叉树结构体定义！不熟！

struct Node{int val;Node* left;Node* right;Node(int x): val(x), left(nullptr), right(nullptr){}
};
Node* t_node = new Node(cur_value);

//已知二叉树,进行层序遍历：queue先存进根节点，取queue.front()为cur_node,然后边访问其值，边先后存进左右节点（非空）
//  递归的核心：大问题化成规模较小的同类型问题，套用相同操作，直到遇到终止条件
//  本题：开始已知中&后续，不断找到左右子树的中后续，套用相同操作，直到遇到空节点
//  从中序找到根节点，根节点左边就是左子树的中序遍历，得到其长度len，则后序中前len个刚好就是左子树的后序遍历，由此调整区间，重复操作

L2-008 最长对称子串 - 团体程序设计天梯赛-练习集

//防惯性：长度的最小值不是0，而是1！

对称问题不止可以用stack！从一点出发初步判断（与后一个相同或者后面第二个相同，则由此向两边展开继续判断）

L2-009 抢红包 - 团体程序设计天梯赛-练习集

题目本身不难，但在for循环嵌套中命名重复，（即for(int i){for(int i)}）

关于定义同时自带成员初始化和运算符重载的结构体：

注意养成给定义函数参数带上初始值的习惯（也可以i不带，但是调用的时候记得传参，不然会报错）

惊天发现！运算重载符对sort和priority_queue的排序效果完全相反！而且sort对应的排序定义更符合常识

比如要依据id从小到大排

sort ： return  id < other.id;

pq:       return id > other.ed;

ps:对于从一开始存放的vector，要注意排序时不能把第0号元素加进去一起排！

struct Node{int id, num_bao;double sum_qian;Node(int x = 0): id(x), num_bao(0), sum_qian(0){}bool operator<(const Node& other)const{if(sum_qian != other.sum_qian) return sum_qian < other.sum_qian;//大小else if(num_bao != other.num_bao) return num_bao < other.num_bao;//大小else return id>other.id;//小大}
};

L2-011 玩转二叉树 - 团体程序设计天梯赛-练习集

 //写完代码首先检查main是否打成mian！这个后面编译比较难查出来 
//实现镜像操作，可以直接在构建二叉树的时候，将左右子树的赋值互换即可
//已知先序&中序，构建二叉树不熟练：确定先序遍历讨论区间，要去掉第一个元素（其为cur_val），然后再计算len_lf：root->lf = dfs(dfs, st_in, idx-1, st_first+1, st_first+len_lf);

// Node(int x): val(x), lf(nullptr), rt(nullptr){}

L2-012 关于堆的判断 - 团体程序设计天梯赛-练习集

//建立小顶堆的过程：接收一个，就插入一个！

for (int i = 1; i <= N;i++){//建立小顶堆:记住，边插边建！cin >> vec[i];int k=i;while(k>1 && vec[k]<vec[k/2]){swap(vec[k],vec[k/2]);k/=2;}}

//int idx = str.find（to_find, start）

注意：是从start开始向后查找，且包含start位置本身！

//ps: rfind(tofind, start)函数是从是从start开始向前查找，且同样包含start位置本身！

注意：没有找到返回-1，但是if（-1）会被判断为true，所以应该用 if (str.find(to_find) == -1)表示查找失败

//字符串转整数：stoi（str）

//误：兄弟节点的判断：兄弟 ！= 存储位置差为1，因为后者有可能并非同属于一个父亲

对于完全二叉树，用 idx1 / 2 == idx2 / 2来判断

L2-013 红色警报 - 团体程序设计天梯赛-练习集

//解题反思：把问题想复杂了，觉得下面的方法复杂性偏高，一直在纠结更好的解决思路，实际上下面简单的算法就已经能够实现题目要求了
//思路简单，略显粗暴bushi，不必强求低复杂性的算法
//AC代码的思路：在开始时和每一次攻占后重新用DFS来计算联通区域个数
//看看联通区域个数是否与之前的有差异

L2-050 懂蛇语 - 团体程序设计天梯赛-练习集

关于字典的使用

查找某个键是否已经存在于字典中，返回迭代器，注意用auto接受

auto it = map.find(key);
if(it != map.end()) cout<<"存在"；
else cout<<"不存在"；

值得重看！L2-052 吉利矩阵 - 团体程序设计天梯赛-练习集

题目分析：并不是真的要将构建好的矩阵的所有元素都存下来，而是要找到唯一生成题目要求矩阵的逻辑，每跑通一次逻辑，就相当于生成一个矩阵。

此时，我们只要保证生成的过程是“单方向的”，也就是通过递归函数中for的单方向给每个元素赋值，就保证了生成矩阵的唯一性。从而：跑通的次数 = 矩阵的种类数

关于完善代码：尝试在细节的地方加入一些判断，有可能就会补上之前逻辑中的漏洞

比如一开始，笔者用最后一行元素总和为L来进行判断矩阵符合要求，但是总和为L不能保证每一个元素都在【0，L】的范围里面，可见完善代码的过程中不厌其烦地加入判断是必要的。

！！注意递归函数对一般位置的处理和特殊位置的处理

特殊位置有特殊性质（初始位置& 边界位置）：

• 最后一行的元素，都是“由该列已经生成的元素决定的，值唯一为L-sum(该列其他)”；

• 每行最右边的元素： 值都是由该行左边所有元素之和决定的，值唯一为L-sum_left

递归函数编写顺序：按照执行的先后顺序来编写，而不是按照代码的先后顺序来编写

也就是，先保证起始部分的代码，接着对边界位置进行处理，最后写结束部分的处理，注意不同模块之间的衔接

递归思路：从左上角开始，逐行进行，每行从左到右，每次对一个元素进行操作