noip笔记

经验

• 复杂状态可以map套vector

• vector默认字典序排序

• 判断元素是否存在于map中，不要使用 []==，要用find，因为调用[]会在map中生成一个节点
  多次判断存在会使长度非常大

• 注意卡时用clock的效果更好。clock的返回值不能直接用（不同系统下的返回值代表含义不一样），需要转为double然后 /CLOCKS_PER_SEC，毫秒用小数，一般要留出200ms的空余，4e6的数据卡1.8s实际运行1.9s
  最大限度的使用给定的时间，可能多点分，还能避免tle

• 统计一个数在指定区间出现次数，可以把这个数出现的位置放到这个数的vector里，然后用upper/lower_bound查找给定的r和l再相减，就可以求得

• 搜索时慎用map判重！会带来负优化

• 如果有题目需要开long long，那么赋最大值或最小值的时候应该使用 0x3f3f3f3f3f3f3f3f（8个）
  double数组初始化正无穷用127，经测试floyed不会爆负数，且比1e10还要大
  负无穷可以赋值 memset(a,-0x3f,sizeof(a))

• 增大栈大小 -Wl,-stack=134217728 （12810241024，类似sizeof）

算法相关

• 分解质因数的时候，首先使用筛法预处理出质数来，然后依次判断每个质数是不是给定数的因子
  如果是的话，一定要不断除掉这个质数直到除尽，得到的数再进行判断
  这样可以显著降低时间复杂度

• 拓扑+贪心，一般都是在反图上拓扑
  正图上拓扑出来一般都是字典序最优

• n 18到22适合状态压缩dp

• 知道一个序列的弹栈和压栈顺序，可以构造出一个树来（dfs过程就是压栈弹栈的过程）

• 将一个DAG转为强联通分量，需要满足所有点的出度不为0且入度也不为零（第二个往往被忽略）