文章目录

阅读理解程序一些算法，数据结构的标志及技巧二分链表最短路最小生成树 一些常见函数变量名的意义（不是一定仅供参考）函数变量 一些常见程序块的意义复杂度分析一些常见的复杂度(分析) 完善程序方法 解题方法总结

阅读理解程序

三分靠模拟，七分靠猜 搞懂或者猜出变量的意思是非常重要的，例如 sum 是求

注意：

语法和逻辑上的坑点常用算法有大体上类似的写法通过特殊语句判断程序意图长程序：分成部分的子功能，从主函数开始看

技巧：

数东西时如果看着挺对称的就用二分

一些算法，数据结构的标志及技巧

二分

标志： while(l != r) 或 while(l <= r) mid = (l+r)/2 [l,mid] [mid+1,r]

链表

标志： 观察插入、删除的代码 有时会有各种数组指针（经常是比较复杂的数组嵌套，例如 a[b[c]]），可以画图找方向

最短路

判断标准： Dijkstra：priority_queue 复杂度分为 O(nlogn)和 n*n 两种 n*n 的算法每次都要找最小值 SPFA：queue Floyd：三重 for 循环

最小生成树

标志： 函数名为 MST（正常人都会用。。。） 算法：Kruskal, Prim

一些常见函数变量名的意义（不是一定仅供参考）

函数

getPermutation 获取排列 STL 方法: getNextPermutation（用于获取下一个排列）mergesort 归并排序getRoot 标准并查集magic 可能是hash 加密编码LPS 给一个字符串，找出它的最长的回文子序列的长度。详见：LPS

变量

sum 求和res 统计结果ret 返回值dad(d) 父亲节点visit(v) 访问过

一些常见程序块的意义

求最长回文子序列长度(LPS) if (seq[i] == seq[j])hanshudeyiyi return lps(seq, i + 1, j - 1) + 2; len1 = lps(seq, i, j - 1); len2 = lps(seq, i + 1, j);

复杂度分析

了解各种算法的复杂度 注意单次操作的运行次数（有时候不会触发） 注意循环层数（有时候不会满） 注意分治（有时候是假的分治）例如：线段树只递归未分治

一些常见的复杂度(分析)

分治复杂度分析：看递归然后用主定理线段树 O(nlogn)

完善程序

给出一个具体的算法问题和程序，要求填空 仔细读题，理解思路和算法、输入输出 常规填空题，需要大概摸清楚程序意图 理解变量，猜意思，例如 sum 表示求和 （可选：先不看程序，自己想怎么做） 理清程序片段作用，考虑使用的算法（常在上下文给出类似语句参考） 理解填空的位置的需要什么 （可选：自造样例验证） 注意： 链表格式固定 很多算法格式固定

方法

找规律数学推算用常见的算法带入看是否符合题意

解题方法总结

直觉 灵感和扎实的基础能看出是什么算法：直接猜，不要管细节程序复杂度不太高：模拟又不知道如何快速解题，又不知道如何模拟： 趁早放弃！！！！！有时候要注意程序中的一些细节防坑有很多算法写的格式固定要多背/理解一些算法的标准写法 如： 高精度除以单精度的写法很固定，所以以前自己写过的会做得快

我不理解的：幻方，逆序对，从某个排列开始，往后再数 t 个排列并输出?