[TOC]

阅读理解程序

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

注意：

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

技巧：

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

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

二分

标志：
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)
1
2
3
4
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 个排列并输出?