文章来源: http://thunderfyc.wordpress.com.cn

算法 数据结构 问题 程序的关系

  问题由模型作为内核，用替换方式将抽象概念具体化，形成描述来包装内核
  模型由数据和解决方法构成，每个问题不同情况的表现组成成数据，通过统一的解决方法得到解决
  算法是解决问题的一般化方法
  数据结构是数据的组织形式
  程序是用计算机语言，在数据结构上操作算法，利用计算机解决问题

数据结构
  数据结构是独立于数据而存在，具有一定逻辑结构，支持在上面进行被允许的操作，如插入、删除、查找等

  主要有 单元节点、散列、线性表、树、图

单元节点/元素
  最基本元素，储存数据的直接单位

散列
  元素相互独立，没有直接关系的结构 集合
  唯一关系 元素在集合内

  操作 插入 删除 查找某元素
  集合的实现 数组 BST

  Hash表
    考虑集合的数组表示a[x]为x是否在集合中，这是一一对应的关系
    Hash表将x用特征值t来表示 对于不同的x可能对应同一个t（即冲突），根据t来查找x
    f(x) = t 的函数是hash函数， t为x的hash值
    因为可能存在冲突 有不同的处理方法 通常用链表来存储不同的x
    操作 插入 删除 查找
    先计算f(x) 在对应的链表中操作， 好的hash函数可以让链表尽可能短， 达到理想效果

    典型应用：记录庞大数字、字符串等，字典的实现

线性表
  线性表中，元素线性排列，相邻元素有前驱后继的关系

  操作 插入 删除 查找某元素 遍历 查找第k小
  线性表实现 数组 链表

  有序表
    元素顺序排列，可以用二分查找某个元素，可以直接获取第k小，插入删除困难，适用于排序之后的静态操作

  栈
    先进后出，用于人工模拟递归操作，表达式处理，递归过程中获取解答和模拟类题目

  队列
    先进先出，用于宽度优先搜索

  映射
    在线性表上加以集合构造 a[]是一个数组,已经具备某种逻辑关系A。
    b[i]表示b[]第i个元素在a中的位置，初始b[i]=i，通过对a[b[i]]的排序得到对应数组a’[]具有逻辑关系B，a[]中元素位置未改变过

  指针操作
    对于一个序列，在上面进行简单的指针移动，获得完全遍历求最优解

字符串
  匹配
    RK 将模式串用数字表示(hash)，然后通过移动将当前匹配单位的hash值计算出来，相等的时候，逐个判断
   
    KMP P为模式串 S为正文，用R[p]表示最大的k 使得P[1..k] = P[m-k+1..m]，这样如果在p+1处匹配失败，可以直接移动k个单位，匹配的过程实际为O(n+m)
        获得R[]的过程，对于R[p]，k = R[p-1]+1 如果P[k]不等于P[p]，k移动到R[k-1]上，继续匹配，否则R[p]=k，k右移

文章来源: http://thunderfyc.wordpress.com.cn 

==================================================================================

1 对0..65535范围内的数字进行O(N)复杂度的排序

  用t[i]表示等于i的元素有多少个 从0开始往后数即可

2 有一串数，找到两个的商最接近t的

  将数排序之后 用两个指针l, r 如果a[l]/a[r] < t， 那么a[l+1]/a[r]可能更接近t， 至少比a[l]/a[r+1]接近；
  反之亦然。最后l和r从1遍历到n之后，中途遇到的最优解即可

3 表达式处理

  表达式 = 表达式 符号 表达式。只有当表达式为优先级最高的时候，才能把它转化为数字，替换，这个就是典型递归过程，
  但是串的处理是顺序的，所以用栈操作，每次判断新压入栈的符号是否更高级，如果更高级 将前面的基础表达式计算。

==================================================================================

Hash
  f_hash(x: dataType): int;
 
  find(x: dataType): node;
  {
    t = f_hash(x);
    s = hash[t];
    while (s.data <> x)
    {
      s = s.next;
      if (s = nil)
        return nil;
    }
    return s;
  }

  ins(x: dataType);
  {
    t = f_hash(x);
    s = hash[t];
    if (s = nil)
    {
      new(hash[t]);
      hash[t].data = x;
      hash[t].next = nil;
      return;
    }
    while (s.next <> nil)
      s = s.next;
    new(s.next);
    s = s.next;
    s.next = nil;
    s.data = x;
  }

  del(x: dataType);
  {
    if (find(x) = nil)
      return;
    t = f_hash(x);
    s = hash[t];
    if (s.data = x)
    {
      hash[t] = s.next;
      return;
    }
    p = s;
    s = s.next;
    while (s.data <> x)
    {
      p = s;
      s = s.next;
    }
    p.next = s.next;
    delete(s);
  }

RK
  RK(p:string, s:string): int;
  {
    pt = 0;
    m[0] = 1;
    for i <- 1 to p.len do
    {
      pt = (pt*26+p[i]) mod 29999;
      m[i] = m[i-1]*26;
    }
    st = 0;
    for i <- 1 to p.len do
    {
      st = (st*26+s[i]) mod 29999;
    }
    for i <- p.len+1 to s.len do
    {
      st = ((st - m[p.len]*s[i-p.len])*26+s[i]) mod 29999;
      if (st = pt)
      {
        check one by one;
        if ok
          return i;
      }
    }
    return -1;
  } 

KMP
  pre(p: string);
  {
    j = 1;    k = 0;    next[1] = 0;
    while (j < p.len)
    {
      if (k = 0 or p[j] = p[k])
      {
         j+1; k+1;
         if (p[j] <> p[k])
           next[j] = k
         else
           next[j] = next[k];
      }
      else
        k = next[k];
    }
  }

  KMP(p: string, s: string);
  {
    i = 1;  j = 1;
    while (j <= p.len and i <= s.len)
    {
      if (j = 0 or s[i] = p[j])
      {
        i+1; j+1;
      }
      else
        j = next[j];
    }
    if (j > t.len)
      return i;
    else
      return -1;
  }

文章来源: http://thunderfyc.wordpress.com.cn

文章来源: http://thunderfyc.wordpress.com.cn

初赛
  选择
    数学问题（集合 真值表）
    数据结构（队列 栈 Hash 查找 排序的操作）
    计算机知识（硬件 软件 网络）
    编程原理（语言类别 编译原理 历史）

  数学
    排列组合
    概率等

  阅读
    2小2大的类型
    胡乱变量相互操作 变量表的记录
    指针操作 指向内存改变和内存记录的改变
    递归类 将递归每层都记录下来
    循环类 每次循环都作一个二维的变量表

    注意将大的程序段划分
    对于若干子的小程序 记忆程序功能
    可在对输入数据操作的时候 不需要再看程序操作 可以加速
    注意输出的格式

  填空
    终止条件
    循环范围
    递归语句
    输入输出部分
    主要计算部分

    读入题目之后 自己先构思一个程序
    将自己的程序和给出的程序进行比较
    可以判断填空部分需要的内容
    然后先填入 再阅读
    进行调整

文章来源: http://thunderfyc.wordpress.com.cn

程序设计
  读题
    确定抽象模型 判断问题规模

  建模
    根据问题规模确定适用的解决方法

  算法
    将粗略程序框架构建出来

  代码
    将每个粗略的子程序 分块写出
    子程序之间用变量交换信息
    结构化程序设计

    变量命名注意唯一性
    注意全局变量和局部的区别
    注意传值参变量是否允许修改
    变量注释

    注意程序的宽度拉伸
    在符号两边有空格
    4格缩进
    语句注释
   
    长度拉伸
    一行一句话
    不同功能子程序之间空行
    子程序注释

  测试
    可以在程序中添加调试代码
    临时输出一些变量
    注意备份程序

    对于要优化的程序
    写一个随机生成数据程序 生成小数据
    写一个保证正确的低效率程序
    通过不断的重复测试 找到WA的数据 调试

    白箱测试
    反复阅读代码
    判断可能出现的问题

  调试
    输出临时信息帮助判断
    信息过多可另写程序帮助判断

    分步调试
    逐个排除子程序的问题
    在子程序中找错误语句

    白箱调试
    判断是否完全符合题意
    所有情况都考虑到

混分
  边界条件输出

  打表输出
    逐个用低效算法计算存储后输出

  贪心
    用直观算法贪心计算
    通过不同的贪心策略来取最优

  输出定值

文章来源: http://thunderfyc.wordpress.com.cn

文章来源: http://thunderfyc.wordpress.com.cn

递推
  f(x) = f(x-1)+f(x-2)
  M = ((0,1),(1,1))
  ((f(x)), (f(x+1))) * M = ((f(x+1)), (f(x+2)))
 
  ((f(x)), (f(x+1))) = ((f(1)), (f(2)))*M^(x-1)

  集合划分
    n个元素划分到k个集合里
    f(n,k) = f(n-1, k-1) + k*f(n-1, k)
    n-1个元素放在k-1个集合里 剩下一个单独成集合
    或者n-1个元素在k个集合里 剩下一个放置在其中任何一个

  错装信封
    第i封信不在第i个信封里
    假设i在n上 n在i上 剩下n-2个错排 所以有f(n-2)*(n-1)个 i枚举从1到n
    假设i不在n上 n在i上 那么去掉n后 n-1个位置对应n-1个数的错排(i考虑为n) 那么有f(n-1)*(n-1)个
    f(n) = (f(n-1)+f(n-2))*(n-1)

数论
  gcd(a, b) = gcd(b, a mod b)

  互素的数的个数
  Phi(n) = n(1-1/p1)(1-1/p2)…(1-1/pi)

  a^b mod n
    b的二进制表示<bk,bk-1,…,b0>
    从左到右 d = (d*d) mod n 如果bi=1 d = (d*a) mod n

高精度
排列组合
  求排列为第几位
    从第一个位置到最后一个 求比当前位置的数更小的数且不和前面相同的可能数 累加
    例如 13245 0*4! + 1*3! + 0*2! + 0*1! + 0 = 6  (12345 12354 12435 12453 12534 12543 13245)
         41352 3*4! + 0*3! + 1*2! + 1*1! = 75

  求某位排列
    从第一位开始确定 用x!的倍数来确定是在前面未出现的数中排列第几的数

  求后继
    找到一个一直延伸到末尾的递减序列 然后将前一个值和递减数列中恰大于它的值互换后 将递减序列排序为递增
解方程
  Newton迭代
    求导之后 作切线 得到和x轴交点作为新的x 求导 作切线 不断逼近

计算函数解析式
  Lagrange插值公式
    已知n个点坐标 求过这些点的方程
    f(x) = sigma(f(ai) Pi(x-aj[j<>i])/Pi(ai-aj[j<>i]))

不定方程
  Euclid
  gcd(a, b) = ax + by 有解
  (d’,x’,y’) = ext_gcd(b, a mod b)  (d,x,y) = (d’, y’, x’-[a/b]y’)

  Pythagoras
  a^2+b^2=c^2
  假设 x = a/c;  y = b/c;
     x^2+y^2=1
     y^2=(1-x)(1+x)=> y/(1+x) = (1-x)/y
  设 t = y/(1+x)
   tx-y=-t;  x+ty=1;
  另 t = u/v   [t为有理数]
   a/c = (v^2 - u^2)/(u^2+v^2)
   b/c = (2uv)/(u^2+v^2)
   u,v互素 且有一个奇数 v>u, a = v^2 - u^2; b = 2uv c = u^2 + v^2

  Pell
  x^2-ay^2 = 1
  xn = ((x1+d^0.5*y1)^n+(x1-d^0.5*y1)^n)/2
  yn = ((x1+d^0.5*y1)^n-(x1-d^0.5*y1)^n)/2d^0.5
  xn = x1xn-1 + dy1yn-1
  yn = y1xn-1 + x1yn-1

文章来源: http://thunderfyc.wordpress.com.cn

=================================================================================

猫的帽子里总有n个小猫，小猫又有小小猫，小猫的高度是猫的1/(n+1)，
最小的猫高为1，已知最大的猫高度和最小的猫数，求除了最小猫的数量和所有猫的高度和

H0 = (N+1)^dep;
workNum = N^dep;
ln(H0) = dep*ln(N+1); ln(workNum) = dep*lnN;
ln(H0)/ln(workNum) = ln(N+1)/ln(N); [此方程y -> 1 精度会有问题]

ln(H0)/ln(H0/workNum) = ln(N+1)/ln((N+1)/N) = ln(N+1) / ln(1 + 1/N)
y = ln(N+1) / ln(1+ 1/N)  [增函数]
用Newton-Raphson 牛顿迭代法解（随便一个初始值，从函数上此点作切线，和x轴交点为新的值）
x = x0 - f(x0)/f’(x0) 迭代几次就可以了

notWorkNum = 1 + N + N^2 + … + N^(dep-1) = (N^dep - 1)/(N-1) = (workNum - 1)/(N-1);
HSum = 1 + (N+1)+(N+1)^2 + … + (N+1)^dep = ((N+1)^(dep+1) - 1)/N = (H0*(N+1) - 1)/N;

求数a b 满足1+2+..+a-1 = a+1+…+b

做方程a*(a-1) = (a+t+1+a+1)*(t+1)  x^2-2y^2 = 1
x = 2t+2a+3  y = 2a
用Pell方程求解
xn = x0*xn-1 + 2*y0*yn-1
yn = x0*yn-1 + y0*xn-1

=============================================================================

Bignum Plus(a,b:Bignum)
{
  for i <- 0 to maxn
  {
    c[i] = a[i]+b[i];
    c[i+1] += c[i] div 1000;
    c[i] = c[i] mod 1000;
  }
  return c;
}

Bignum Minus(a,b:Bignum)
{
  if (less(a,b))
    return Minus(b, a);
  for i <- 0 to maxn
  {
    if (b[i] < a[i])
    {
      b[i+1]-1;
      b[i]+1000;
    }
    c[i] = b[i]-a[i];
    c[i+1] += c[i] div 1000;
    c[i] = c[i] mod 1000;
  }
  return c;
}

Bignum Multi(a,b:Bignum)
{
  for i <- 0 to maxn
  {
    c = 0;
    for j <- 0 to maxn
    {
      c[i+j] = a[i]*b[j];
      c[i+j+1] += c[i+j]  div 1000;
      c[i+j] = c[i+j] mod 1000;
    }
    d = Plus(d, c);
  }
  return d;
}

文章来源: http://thunderfyc.wordpress.com.cn

文章来源: http://thunderfyc.wordpress.com.cn

递归
  将问题转为子问题 解决 降低编程复杂度使用

搜索
  DFS
    每层递归枚举一个选择 然后继续递归 得到所有解

  BFS
    将队首的节点扩展之后放入队尾 然后继续扩展 直到没有节点为止

    Floodfill
      要判断一个格点盘上连通的格点标记
      从一个格点开始 将其放入队首 扩展周围邻居格点 如果没访问过 放入队尾 然后继续扩展 直到不可扩展为止

搜索优化
  Hash判重
    判重的时候利用Hash可以O(1)判定是否访问过

  搜索顺序
    有的时候从小到大 有的时候从大到小 有的时候根据选择评估得到解得可能性

  双向BFS
    将初始状态扩展 目标状态扩展 两者重合时结束 得到一条路径

  分支定界
    扩展节点对于超过可行范围的砍掉
随机化
  利用随机打乱输入限制 尽可能得到平均效率

  生成随机序列
    对于P[i] 将P[i+1]到P[n]中随机找一个 和P[i]交换

  搜索过程中随机选择
 

  QuickSort随机选择中枢点

文章来源: http://thunderfyc.wordpress.com.cn

DP
  把问题分化为子问题之后 取之最优解 从底向上 或用递归从上往下再往上

  最优子结构
    能从最优的子问题解答中解答主问题
    最优子结构的解需要独立 一个问题的解不会影响到另外一个问题

  重叠子问题
    两个大问题的若干子问题中 有相同的
    注意存储子问题的解 以提高效率

  重建最优解
    在解决子问题的时候 记录取得最优解的选择 可以从根回溯到解

  记忆化
    从主问题递归子问题 子问题返回的解记忆下来 以后再子问题的时候可以直接调用
    既延续从底开始的不需重复计算的优点 也避免了从底开始会进行很多不必要计算的缺点

记忆化搜索
  在搜索过程中 记录下子问题的解 然后如果搜索到这一步骤 就直接取得解
  DP的一种表现形式

=====================================================================
8皇后
   记录覆盖线的编号 斜边按中间为0 两边为正负的方法记录
   利用对称性

Castle
  已知图上城堡用颜色染色 然后判断有多少城堡 最大城堡多大
  Floodfill

8数码
  一个9宫格上8个数字 有一个空格 每次可以把一个数字移到空格上  要把它排成预定样子
  A* 或者双向BFS
矩阵连乘的计算代价可以用结合律的方法来减小 求最少计算代价 计算代价为乘法的次数
      结合的种类数为 Pn = Σ(Pk*P_n-k) P1 = 1
      用opt[i][j]表示从i到j的计算代价 opt[i][j] = min{opt[i][k] + opt[k+1][j] + pi-1*pk*pj} p表示列
      另外可用s[i][j]表示取得最优解的k
      用从底向上的方法计算的话 就是 for l = 2 to n; for i = 1 to n-l+1; j=i+l-1; for k = i to j-1;
      l是枚举当前处理的区间长度 i是左端点 j是右端点 k是最优解选择 很显然 opt[i][k] opt[k+1][j]因为区间长度小于opt[i][j] 所以必然已经解出

已知两序列 求最长的公共子序列(不一定连续)
      如果xm = yn zk=xm=yn 而且z(1..k-1)是xm-1 ym-1的LCS
      如果xm<>yn 如果zk=xm 那么Z是X和Yn-1的LCS 如果zk=yn 那么Z是Xm-1和Yn的LCS
     
      以c[i][j]表示X到第i Y到第j的最长长度  c[i][j] = c[i-1][j-1]+1 [xi=yj] c[i][j] = max{c[i][j-1], c[i-1][j]} [xi <> yj]
      可以用b[i][j]表示是从哪个串过来的 回溯的时候 就可以判断是返回b[i][j-1]还是b[i-1][j]还是b[i-1][j-1]

      也可以不用b[][]数组 因为c[][]数组的计算规则能够帮助我们决定b 而c可以利用滚动数组 只记录相邻两行即可

Optimal Binary Search Tree
      BST中从根到关键字的路径长度为代价 又知每个关键字的访问概率 求使得期望访问代价最小的BST
      每一棵最优BST的子树都是最优BST 然后可以知道左子树一定都小于根 一定都小于右子树 那么在一个有序序列中 确定根的位置 就可确定左右子树范围 通过递归到叶子 就可解决问题
      opt[i][j]表示有序表i~j形成的树的最小访问代价 w[i][j]表示访问概率之和 opt[i][j] = min{opt[i][k-1]+opt[k+1][j]+w[i][j]}
      可用mid[i][j]表示取最优值时的根

      mid[i][j]的取值区间为mid[i][j-1]到mid[i+1][j] 利用这个条件(四边形不等式) 可以将复杂度降为O(n^2)

Planning a Company Party
      公司的人事结构形成树 派对中 直接上下级关系不能同时参加 每个人有个高兴值 要求列出合法名单使高兴值最大
      以opt[i][0/1]表示 以i为根的树的最大高兴值 0为i参加 1为i不参加
      opt[i][0] = Σ(max{opt[k][0],opt[k][1]}) k为i的孩子
      opt[i][1] = Σ(opt[k][0])
      结果为max{opt[1][0], opt[1][1]}
      方案不用存 只要从最优值出发 如果为1 则下属均不参加 如果为0 判断下属的0和1哪个大 即可

Edit Distance
      已知一个字符串X 要变成字符串Y 操作过程将X从左至右扫描 合法操作有 1继续 2更改当前字符 3删除当前字符 4插入新字符 5交换下两个字符 6结束 每个操作的代价已知 求最少代价方法
      用opt[i][j]表示字符串X[1..i]转换到Y[1..j]的最小代价 从opt[i-1][j] opt[i-1][j-1] opt[i][j-1]向后推得 利用oper[i][j]表示用了何种操作

文章来源: http://thunderfyc.wordpress.com.cn

文章来源: http://thunderfyc.wordpress.com.cn

枚举
  状态的简单枚举
    可以简单表示的单参数状态，对每个状态计算得到结果判断是否相等

  状态压缩表示
    将状态压缩表示 如一组数 选择与不选用0和1表示 然后枚举

  对已知答案集的枚举
    知道答案的范围 然后对答案进行枚举判断是否符合条件

  步长叠进枚举
    知道答案 并且答案对情况的影响连续变化 通过大步寻找小范围 然后小步寻找答案的方法解 通常为几何问题

贪心
  和DP类似 满足最优子结构 同时满足最优选择 即能导出最优子结构的选择唯一可判定

分治 二分
  将问题分解为子问题 子问题共同对问题产生贡献
  答案二分 单调决策序列二分

  归并排序
    将序列拆为一个元素长的若干序列 然后合并的时候将相邻的序列合并 最后合并为一个大的

  快速排序
    选定一个轴将小的放在左边 大的放在右边 然后分别继续处理两边

  二分解方程
    确定一个范围 满足f(l) f(r)异号 然后计算mid=(l+r)/2 找到f(l) f(r)中和f(mid)异号的 缩小范围 继续

  LIS的二分优化
    找到一个序列中的最长不下降序列
    记录t[x]为长度为x的LIS的最后一个元素大小 要尽可能的小 可见t[]是有序的数组
    每插入一个a[i] 如果a[i]比某个t[k]小 比t[k-1]大 那么a[i]替换这个t[k] 满足条件 如果比t[x]要大 t[x+1]为a[i] 整个序列的LIS拉长一位

文章来源: http://thunderfyc.wordpress.com.cn

=============================================================================

8×8棋盘上八皇后摆放 棋盘每格有分数 最后八皇后占据格子分数最大
求出所有摆放方案 枚举方案 计算

三个食物有不同的营养成分 选取每个食物的份数 最后让营养成分成要求的比例
枚举每个食物的份数 计算

已知若干线段 找一点 连接到这线段上某一点 使得距离和最小
连续变化 用大步长确定范围 小步长确定位置

若干活动 知道起始时间 求不冲突活动的最大个数
按结束时间排序 然后如果m在i之后开始 j前结束 的结束时间最小的 那么m必选 i m之间没有其他活动

若干活动 知道起始时间 求安排所有活动的最少礼堂数
将开始和结束时间并在一个表里排序 开始的时候找到一个空闲的礼堂插入 如果未使用过 礼堂数+1 结束的时候把该礼堂设置为空闲 放入空闲礼堂对首

序列AB 要求Pi(ai^bi)最大的排序方案
降序排列  bi>=bj ai>=aj ai^(bi-bj) >= aj^(bi-bj) ai^bi*aj^bj >= ai^bj*aj^bi

文章来源: http://thunderfyc.wordpress.com.cn