积分和每日一题镇楼

1 初出茅庐的python练习生

文科专业需要用python处理数据，学了一些python的基本语法，想来力扣加强一下代码能力，顺便打一下周赛。最初可以说是漏洞百出，比如建立一个二维列表，[[0] * m] * n发现结果怎么都不对，也找不到bug在哪，才知道得写作[[0] * m for _ in range(n)]，类似的错误可以说太多了，极其折磨，不过过了这个阶段就顺风顺水了。

2 迈向瓜店

2.1 DP专项练习

由于我几年前有一些C++基础(现在忘得差不多了)，学过一些基础的算法和数据结构，上Knight感觉比较容易，基本会了语法，了解一些数据结构就可以上，但是名次经常400-900徘徊，差不多就停留在了2000分。那么我是如何突破到瓜店的呢？这里向大家推荐一个力扣的学习计划题单，即动态规划的基础和进阶。

众所周知，力扣的T3 T4 DP是常客，而这个题单囊括了力扣常见的DP套路，只要独立完成，苦思冥想一道题想1-2h是常态，实在不会就看题解，然后隔几天再写写。逆序对和状压DP给我留下了深刻的印象，这不只是的一个题型或者算法，学会后感觉思维都获得了显著的提升。

2.2 灵神题单针对性查漏补缺

如果遇到一些题型总是做不出来，可以打开灵神的题单如何高效刷题。

灵神贡献了各个知识点的相关题目整理，以及众多高质量的题解。我的数位DP就是完全跟着灵神学习的，对于数位DP薄弱的同学也可以B站搜索数位DP，前排就有灵神的视频。

3 上瓜需要哪些算法基础

坦白来讲我会的也并不多，如二分图匹配，马拉车，KMP与Z函数（一看就会，不用就忘，我至少学过3次）基本都不太会（尽管类似题目肯定也AC过，但是现在让我写估计能写几小时），有很多容器也不太会用，比如有序列表（一些题目可以作弊般的简化），我基本掌握的算法有以下这些，我觉得这些足够在力扣上瓜。

数据结构: 顺序表、链表（周赛用不上，但是该学还是得学）、栈（python可以用列表模拟）、（双端）队列、集合、字典（哈希表）、树（二叉树、以图形式表示的无根树）、图、树状数组（我学过后基本没用，一般都用的线段树，但是如果遇到卡时间的题目可能只能用树状数组）、线段树（力扣的常客，最基本的最值、和值区改区查的必须要会，写好数组的和动态开点的模板，周赛可以省时间）。

设计类题目就是数据结构全家桶，只有灵活掌握各种数据结构才能AC。算法方面，我主要学了以下这些。

贪心: 贪心可以说是最难的算法之一，正确性很难证明，且题目不同方法也完全不同，我完全不敢说我会贪心，只能说简单的贪心题目可以猜出来。
动态规划: 给出的两个题单刷完，掌握，吃透，我觉大部分周赛2400以下的DP都可以搞定，再难的可能就得去刷点CF洛谷的DP锻炼思维了。数位DP、状压DP还是建议大家啃一下，因为一出就是T4，而且这两类题目很容易识别，做法也比较板，学会了很容易得分。值得注意的是记忆化搜索的时间复杂度计算，灵神讲过，是用函数参数里的状态全部乘起来，再乘上函数内部的时间复杂度，有很多题目记忆化搜索比递推方便很多，一个擦车(cache)顶10行代码。必须递推的话，可以把递归翻译为递推，而时间复杂度如果需要进一步优化时，一般是优化最内层循环(前缀和、二分)。所以比较难的DP可以这样写：写出递归、翻译成递推、尝试优化掉最内层循环。
bfs和dfs: 这个很基础也很重要，在树和图中的应用非常广泛，而dfs也可以和DP结合如换根DP。
基础图论: 拓扑排序、最短路、并查集。一些进阶的我也不会，如割点割边的（遇到学了会几天，平时不刷就忘了）
字符串哈希: 一些题目可能要用KMP的，用字符串哈希贴个板子可以不动脑子过。
常用数论: 加减乘除(逆元)运算遇到模运算的性质，质数筛选(线性筛)，各种GCD、LCM问题。其实这个我很薄弱，没有专门学过，都是刷题中零散的掌握一些知识。
二分: 这个没什么好说的，大家都会，注意细节就可以，需要注意的是二分答案，有些时候有奇效。
位运算: 状压枚举，状压DP中必用，至少得理解每种位运算的含义。而单纯的位运算题目可以很难，只是应对周赛的话可以只把位运算题单刷一刷，学好还是很难的，我感觉我位运算很烂。
字典树: 考的不多，但也得会。

可以看到，我并不会任何比较难的算法，但是要上瓜要学的还是比较杂的，常用的数据结构和算法还是得过一遍，在掌握基础前，不用在意分数。

4 总结

总体来讲，灵神题单只要吃透（我没有全刷，大家可以针对自己弱项刷，节约时间），虚拟周赛个20场，找到弱项，相信大家都是可以上瓜的，目前我的分数肯定有水分，因为有些语法和容器不会用时有问ChatGPT，尽管我不会的题目他从来没帮我做出来过，我会的题目让他写他也写不对，但是在编码过程中，他还是能帮助我不少。加强代码能力，尽量不依赖板子、搜索引擎、帮助文件、ChatGPT才可以做到独立闭卷完成周赛。

5 一点心得

不要太在意分数，更要注重从周赛中发现自己的短板，这样即使在下分，在能力上却上分。可以尝试一些困难题教ChatGPT做，教会他做出一道困难有时候比自己做还要难很多，只有把困难题拆分成若干道简单题，并且清晰描述实现的逻辑和细节，才可以让GPT做出来，这个过程可以让我们思路更清晰，而不是瞎写一通面向错误用例编码。我尝试了一些大厂的笔试面试题目，大部分时候可以AK，尽管我不转码，但是开始挺开心的。刷力扣从功利角度来讲没多大用，收获就是可以看到AC这种即时反馈带来的快乐吧。