复试准备

sort

1
2
3
4
5
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]

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

空间换取时间:(散列)

  • 查找集合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] ++;

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

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

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

最大公约数用辗转相除法

1
2
gcd(a, b) = gcd(b, a%b);
gcd(a, 0) = a

最小公倍数的计算

1
lcm(a, b) = (a/ gcd(a, b)) * b;

分数表示

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

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

求素数的方法:

  • 方法一:
    • 如果n对i, (i 属于[2,sqrt(n)]) 有约数(余数为0),则n不是素数
    • 如果n对i, (i 属于[2,sqrt(n)]) 没有约数(余数不为0),则n是素数
  • 方法二:
    • 最小的素数的倍数肯定不是素数
    • 2是素数
    • 循环筛选

      求质因子的方法

      质因子要么全部在[2,sqrt(n)], 要么只有一个在[sqrt(n), n]。将前面的小于sqrt(n)的质因子全部除掉,剩下的如果!=1,那就是大于sqrt(n)的唯一的质因子

vector是一个边长数组

  • set是一个内部自动有序(递增)且不含重复元素的容器
  • set只能通过迭代器来访问, set::iterator it // 通过* it访问内容
  • multiset可以处理元素不唯一的情况
  • unordered_set 处理只去重但不排序的需求,速度比set快得多

除了vector和string之外的STL都不支持*(it + i)这种形式,只能通过图iteratorBianli.png形式来访问,

其他STL的各种操作都要通过迭代器来实现

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

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

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

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

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

    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的元素的位置,返回指针或迭代器

    求联通分量的个数或者树的个数用并查集

错排公式

F(n) = (n-1)*F(n-1) + (n-1)*F(n-2)

主要数据结构的实现

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

ans += a + b;

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