如题所述，专门记录自己在各类考试、做题中出现的花式错误。

算法思想

• 分块相关算法写挂的：

  • [Ynoi2019模拟赛] Yuno loves sqrt technology II

    写莫队发现自己没有排序，T 飞了。

    大致可以描述为：

    void Init()
    {
        //对 Q 数组进行排序 
    }
    
    int main()
    {
        Init();
        ......
        //读入 Q
        return 0;
    }
    

    处理方式：一定要将数据读入完之后再预处理 。

  • 题目见上。
    写分块的时候对边角块处理不当......

    void UpdateBlock( int id, int l, int r, ... ); //块内处理
    void UpdateAll( int L, int R ); //全局处理
    {
        if( 左边有边角块 ) UpdateBlock( 块编号, L, R, ... );
        ......
    }
    

    事实上应该将左右边界限制在块的范围内。

• 数据结构写挂的：

  • [ARC097F]Monochrome Cat

    使用了俩优先队列的 " 可删堆 " ，结果在 push 和 erase 的时候都没有清除多余元素，于是堆中冗余元素就超多，结果 TLE 了：

    typedef priority_queue<int, vector<int>, greater<int> > Heap;
    
    struct RHeap
    {
    	Heap q, rub;
    	void Push( const int v ) { q.push( v )/*这里需要 Maintain 一下*/; }
    	void Erase( const int v ) { rub.push( v )/*这里需要 Maintain 一下*/; }
    	int Size() { Maintain(); return q.size() - rub.size(); }
    	int Top() { Maintain(); return q.empty() ? 0 : q.top(); }
    	RHeap() { while( ! q.empty() ) q.pop(); while( ! rub.empty() ) rub.pop(); }
    	void Maintain() { while( ! q.empty() && ! rub.empty() && q.top() == rub.top() ) q.pop(), rub.pop(); }
    }
    

  • [CF817D]Imbalanced Array

    这道题用单调栈维护所有位置的最值的和的时候，细节很多。尤其注意的是，每个点管辖的区间实际上是从栈内的上一个元素开始的，也就是 \((stk_{i-1},i]\) ，而不能将自己作为自己那一段的终点。请参考以下这段代码：

    while( top1 && a[stk1[top1]] > a[i] )
    	mn -= 1ll * ( a[stk1[top1]] - a[stk1[top1 - 1]] ) * ( i - stk1[top1 - 1] - 1 ), top1 --;   
    	// 这里不能写 i-stk[top1] ，不然就会少算一些位置
    mn += 1ll * ( a[i] - a[stk1[top1]] ) * ( i - stk1[top1] - 1 ) + a[i], stk1[++ top1] = i;
    
    

• 图论算法写挂的：

  • [AT4569]Connecting Cities

    使用 Boruvka 算法的时候，一定要注意，找出的是点，对应的是连通块，并查集维护的根与连通块的编号没有任何关系，千万不要用混了！

• 思考不全面的：

  • [AGC034C] Tests

    发呆想了半天才发现枚举的那一天可以放在钦定的前 \(k\) 个里面。

    处理方法：思路一定要全，分清问题的主从关系。

• 其它算法各种乱七八糟铁锅乱炖导致写挂的：

  • [AGC002D] Stamp Rally

    关于整体二分的写法问题。

    这里由于我们不能简单地修改要求，所以在进入右区间的时候，我们必须保证左区间的边已经被加入。

    如果写法是在离开区间时删除新加入的边，且在进入右区间之前将所有的左边的边加入，那么没有问题。

    但是如果写法是在叶子的位置加入边，并且之后不删除，那么就必须保证叶子可以到达（现在外层相当于是遍历线段树的过程）。因此如果：

    void Divide( const int qL, const int qR, const int vL, const int vR ){	if( vL > vR || qL > qR ) return ;    ...}
    

    那么就有问题（因为很有可能询问区间为空就返回，没有到叶子节点）。

实现细节

• 编译过程出错的：

  • 由于 g++ 的版本与现行版本不一致，库的包含关系就不完全相同。这个时候如果缺少头文件也有可能会本地通过编译，但是提交后可能会 CE。

    典型例子就是 Dev-C++ 上 cmath 还包含在 algorithm 里面。如果仅包含 algorithm 并且使用 cmath 内部的函数，在新版的 g++ 下编译就会报错。

  • 经典的“隐形”库函数 x1(),y1(),j0(),j1()，这几个小混蛋都在 cmath 里面。

    问题是，它们几乎找不到踪迹。如果去 C++ reference 里面查你根本找不到它们。

    如果在 Windows 环境下使用 9.3.0 版本的 g++ 编译也不会检查出问题，但是，但是，一旦包含 cmath 并且自定义了重名的变量/函数，那么在 Linux 环境下编译的时候才会 CE。