复试

  1. sort

    bool ZuSort(testee t1, testee t2) {
    if(t1.score == t2.score) return t1.id < t2.id;
    return t1.score > t2.score;
    }
    sort(result, result + resultPos, ZuSort); // result[MAX]

  2. 时间、日期等周期性数据应该从最小位自加,逐步控制更高一层的周期

  3. 空间换取时间:(散列)

    • 查找集合N 中的元素在集合M{2,6,7}中是否出现以及出现的次数

      可以用bool M[MAX], M[2] = true; M[6] = true; M[7] = true;

      求出现的次数时,可以用int M[MAX], M[2] ++; M[6] ++; M[7] ++;

  4. 老哥,一定要记得多组数组共享变量的清零

  5. 利用printf(“%.2f\n” ,ans);格式化输出保留小数点两位

  6. 所有单调性函数求解问题都可以用二分法

  7. 最大公约数用辗转相除法

    1
    2
    gcd(a, b) = gcd(b, a%b);
    gcd(a, 0) = a
  8. 最小公倍数的计算

    1
    lcm(a, b) = (a/ gcd(a, b)) * b;
  9. 分数表示

    1
    2
    3
    struct franction {
    long long up, down;
    }

    我们约定,若分母(down)小于0,则令分子,分母为本身的相反数
    约分即是分子分母同除以他们的最大公约数
    若分子为0,则令分母为1
    带分数:整数部分是up/down, 分子是abs(up)%down, 分母是down

  10. 求素数的方法:
    方法一:

    • 如果n对i, (i 属于[2,sqrt(n)]) 有约数(余数为0),则n不是素数
    • 如果n对i, (i 属于[2,sqrt(n)]) 没有约数(余数不为0),则n是素数

      方法二:

    • 最小的素数的倍数肯定不是素数
    • 2是素数
    • 循环筛选
  11. 求质因子的方法
    质因子要么全部在[2,sqrt(n)], 要么只有一个在[sqrt(n), n]。将前面的小于sqrt(n)的质因子全部除掉,剩下的如果!=1,那就是大于sqrt(n)的唯一的质因子

  12. vector是一个边长数组
    set是一个内部自动有序(递增)且不含重复元素的容器
    set只能通过迭代器来访问, set::iterator it // 通过* it访问内容

    multiset可以处理元素不唯一的情况
    unordered_set 处理只去重但不排序的需求,速度比set快得多

  13. 除了vector和string之外的STL都不支持*(it + i)这种形式,只能通过图iteratorBianli.png形式来访问,
    其他STL的各种操作都要通过迭代器来实现

  14. map可以通过it->first来访问键,it->second 来访问值。并且map内部会自动按键从小到大排列,

    unordered_map 用来处理只映射而不排序的需求(用散列代替map中的红黑树)

  15. queue在top/pop前要先判断是否为空,

  16. pair可以将两个元素绑在一起合成一个新的元素

    • 需要include 或者
    • 可以使用p.first p.second来访问
    • 可以用作二维排序,一维相等时比较第二维
    • pair可以用作map的插入键值对
  17. algorithm头文件下的有用函数

    • max(x,y) min(x,y)
    • abs(x) // 对整数求绝对值
    • fabs(x) // 对浮点数求绝对值
    • swap(x,y) //交换xy的值
    • find(x,y,c) // [x,y)查找元素c
    • reverse(it,it2) //将数组指针或者迭代器在[it,it2)之间的数组元素或者容器元素进行反转(逆序)
    • next_permutation(&begin, &end) // 给出序列[begin,end)在全排列中的下一个序列
    • fill() // 可以把容器或数组某一段区间赋为某个相同的值
    • 对容器进行sort时,参数类型用容器的类型就好(对容器里面的元素进行排序),实参一般要用迭代器
    • lower_bound(first, last, value) // 寻找数组或容器的[first, last)范围内第一个值大于或等于 value的元素的位置,返回指针或迭代器
    • upper_bound(first, last, value) // 寻找数组或容器的[first, last)范围内第一个值大于 value的元素的位置,返回指针或迭代器
  18. 求联通分量的个数或者树的个数用并查集

  19. 错排公式
    1
    F(n) = (n-1)*F(n-1) + (n-1)*F(n-2)

主要数据结构的实现

  1. 哈夫曼树
    1
    priority_queue<int , vector<int> , greater<int> > Q;

哈夫曼代价

1
ans += a + b;

  1. 最小生成树可以用并查集实现
  2. BFS
    • 一般用来求解最优解问题
    • 将n元问题建模为n+1(自变量加结果)元问题的状态变化,通常需要一个n+1元结构体来做状态寄存;和一个原数据存储变量
      一般每个样本点只用处理一次,注意处理次数和样品条件的剪枝
  3. DFS
    • 一般用来求解是否有解
    • 是按层进行搜索和便历,故参数应该传层,递归的时候应该是层数加一,数据应该是本层数据取值i