「WTF」铁锅乱炖-实现篇

编译出错

版本问题

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

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

迷之重名

  • 经典的“隐形”库函数 y0(double), y1(double), yn(int,double); j0(double), j1(double), jn(int,double)，这几个小混蛋都在 cmath 里面，存在于编译器的 include 文件夹里的 math.h 里面。

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

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

    去查了一下，发现 j.() 表示的是第一类贝塞尔函数，y.() 表示的是第二类贝塞尔函数。

初始化疑云

这里集中了一些由于不当初始化而导致的编译问题。

在 Compiler Explorer 上以 -std=c++17 编译，所以汇编码应该对应的是 Intel x86-64 的 CPU。

  • 经典错误一：使用大括号初始化数组：

    如果是平凡地直接使用大括号括起来，全部清空，那么初始化不会出问题：

    struct QwQ {
    // something  
};

int a[100000] = {};
QwQ b[100000] = {};

    无论使用内置类型或自定义类型。

    但是，如果在大括号里面初始化了某些位置的值，那么会导致大括号被展开成完整的初始化列表（补上空白）。一个直接的表现就是编译出来的可执行文件非常大。当数组很大的时候效果尤其明显：

    int a[10000000] = { 1, 2 };

// with a large *.exe appearing

  • 经典错误二：错误地使用结构体初始化：

    如果在结构体或类的初始化中对非内置类型数组进行初始化，无论如何赋初值，如下：

    struct Rubbish {
    int rub[1000];
    
    Rubbish(): rub{} {}
    // safe operation
};

struct RubbishBin {
    Rubbish a[1000];
    
    RubbishBin(): a{} {}
    // DANGEROUS operation
};

RubbishBin rb;

    只要对这样的类型进行实例化，那么在汇编码中，构造函数会被完全展开。在上面的这段代码中，实际效果就是对于 a 中每个对象都调用 Rubbish :: Rubbish()。直接看一下汇编码的样子：

    asm.png

    外在的表现就是编译时间变长，但是可执行文件大小正常，嗯。

    实际上，由于全局变量会自动清空（汇编码里面会有一个 .zero 的指令）所以写成：

    struct Rubbish {
    int rub[1000];
    
    Rubbish(): rub{} {}
    // safe operation
};

struct RubbishBin {
    Rubbish a[1000];
    
    RubbishBin()/*: a{}*/ {}
    // Fine
};

RubbishBin rb;

    也可以达到清空的效果，并且不会出问题。

多组不清空

  • [CF1383E]Strange Operation

    同一变量多次重复使用，中间没有清空，直接暴毙：

    int lst = N + 1;
for( int i = N ; ~ i ; i -- )
{
    nxt[i][1] = lst;
  if( S[i] == '1' ) lst = i;
}
//这里本应该清空 lst 的
for( int i = N ; ~ i ; i -- )
{
    if( S[i] == '1' || S[i + 1] == '0' ) nxt[i][0] = lst;
    if( S[i] == '0' ) lst = i;
}

  • 对于判定性问题，如果我们一旦搜索到符合要求的结果就退出，那么在多次搜索的情况下，一定要注意在退出之前有没有将公共内存清空。无论是使用 return 结束语句还是使用 throw 跳转都需要注意这个问题。

  • 「UR #21」 挑战最大团

    注意分治过程中，公共数组的清空，特别是在改写法的时候，不要忘了加上被修改结构的清空过程。

注意边界

  • 预处理应该按照值域为范围来清，结果只清到了点数范围。

  • 模拟赛中出现的 typo 。按理说应该是很常见的问题，我居然还在犯。

    遍历 \(n\times m\) 的平面的时候，弄混了 \(n\) 和 \(m\) 的关系，于是写错了循环边界，成功地挂分了：

    for( int i = 1 ; i <= n ; i ++ )   //这里的 n 应该是 m 
  ...

记清楚变量的含义，尤其是常见易混变量 \(n,m,x,y\) 之类的。

  • 挑战多项式

    这次在预处理逆元的时候，恰好处理到了 \(2^{18}-1\) 的范围，但是实际调用时使用到了 \(2^{18}\) 的逆元，然后就爆炸了......

    处理方法：一定要注意，使用任何函数/循环/数组内存时，是否会越界或超出有效范围；此外，在对复杂度影响不大时也可以适当使用快速幂/exgcd 求逆元；

  • 「Gym102979L」Lights On The Road

    第一次写 K 短路，结果被坑到了两个地方：

    • 建图都建错了，头尾两个虚点不能连在一起，而 \(n=1\) 的时候我会连起来。这个写的时候确实没想到；

    • 当 \(n=1\) 的时候，最短路树上没有非树边，这个时候堆为空。将空节点插进去做 K 短路就会 RE......

      这个问题更大一些，写的时候想到了这一点，但是没有想到堆会成为空，没有判。

      处理方法：注意边界情况，不要被细节卡了。

  • 某道计数题。

    数据范围明确给出：

    mistake.png

    这就说明，输入数据可以有 \(n。但是我的程序，如果不特判 \(n 就会干出奇奇怪怪的事情，导致各种 WA。

  • 保证下标或指针指向的是有效的空间。

    这里主要关注如何控制下标或指针不会越界，而不考虑空间开小了的情况。

    例如 「模板」最小表示法，如果给定的串是 aaa...aa 的形式，则需要判断长度指针 \(k\) 是否到达了 \(|S|\)，否则会访问到有效的空间之外。

    又注：对于下标进行运算的时候也要注意是否会越界。例如，进行减法的时候需要确认是否会越过下界，进行加法的时候需要确认是否会超出上界。尤其是下标从 0 开始计算的时候尤其容易算错！！！

  • 经典错误：如果用 vector 实现多项式，那么在写加法的时候，很容易忘记边界，将任意位置的计算都写成 F[i]+G[i]。但实际上，如果 i 取遍所有有效位，那么下标很有可能越界，导致 UB，返回一些乱七八糟的值。

  • 阳间边界问题：左移超出边界是 Undefined Bahaviour，比如不能算 1llu << 64，不然返回什么东西谁也说不清楚。

  • 某道联测题目：

    在转移的时候，本应在所有数据计算完之后再对不合法数据进行清理，结果边清理边计算，导致较小的不合法数据影响了之后的结果。

    处理方法：注意操作的顺序，不止是在 DP 的转移中，写的时候就应该注意到顺序的问题。

实现有误或不精细

  • [HDU6334]Problem C. Problems on a Tree

    画蛇添足，本身不需要用 map 的地方偏偏使用了，导致程序及其慢， map 占用了将近 \(\frac 1 3\) 的时间。

    补充：可以使用 clock() 检查运行时间。

  • [CF446C]DZY Loves Fibonacci Numbers
    分块写法，清理标记的时候，没有判断有没有标记：

    void Normalize( int id )
{
    //这里缺少了是否存在标记的判断
    for( int k = lef[id] ; k <= rig[id] ; k ++ )
        //......
}

    最开始以为分块的标记和线段树类似，现在才意识到，分块下放标记的时间是 \(O(T)\) 的，所以不判掉就会特别慢......

  • 求欧拉路一定要用当前弧优化。

  • 对于编码方式比较复杂的问题，一定要注意各种编码是否正确转换了。

    比如，二分图匹配的时候，经常会犯忘了特殊处理右部点标号的问题。

  • 注意，邻接表建图后，遍历边的顺序是与输入顺序相反的。

  • 「Gym102268」Best Subsequence

    只要可以离散化，都建议写离散化之后再写线段树。权值线段树实在是太慢了......

    当年冰火战士也有这个诡异的坑点。

  • 「CEOI2006」 ANTENNA

    保证复杂度的剪枝写太弱了，导致复杂度是错的。

    需要注意写下来的代码（比如剪枝）是否和所想的相同。本质上还是在问思路是否清晰。

    在洛谷上居然还可以卡过去，实在是误人子弟。

  • 「UOJ671」诡异操作

    nmd 这个东西是真的诡异。大一点的高维数组寻址奇慢无比，自带满打满算 x2 常数。

    警告：写比较大的高维数组的时候一定要谨慎，如果可以就开内存池，真的可以有效降低常数。

  • 对某个数组进行平移（或者其它下标变换）时，并没能做到对于每个用到数组的位置都去修改下标，最终导致错误访问。

    这个问题解决起来比较麻烦，最好的方法还是一开始就确定好如何定下标，避免以后再去修改。

数据杂糅

  • 「CF916D」Jamie and To-do List

    题目本身并不难，但是要注意，由于我们将值存储在 Trie 的末尾，所以被删除了的节点本质上就是变成了空节点。因此，空节点存储的值应该等于被删除了的值。例如，如果空节点值为 0，那么被删除的节点的值也应该是 0。

    否则，Trie 的结构就可能导致将空节点判断为有值的节点的错误出现（例如，插入一个较长串，并查询它的前缀）。

    处理方式：同类标记尽量统一。

  • 线段树（以及任何静态结构）上，如果需要删除结点，那么在维护最值的时候我们一般会将要删除的结点赋成一个极值。

    但是一定要注意，这里的极值应当区分初始化的极值，尤其是在需要同时取出极值所在的位置的时候。这里就需要明确：初始化所赋的极值是可以取的，但是删除所赋的极值就是为了避免取到的。

运算

变量类型

  • 「LOJ 6207」米缇

    整除分块的时候，使用中间变量记录取整除的值，但这个中间变量没有开 long long：

    for( long long l = 1, r ; l <= n ; l = r + 1 ) {
    int val = n / l; // 就是这里！！！应该开 long long！！！
}

  • 「SPOJ」MAXOR

    答案的范围是 \([0,2^{31})\)，所以计算 \(L,R\) 的时候，如果中途不取模可能会爆 int。

    处理方式：涉及到的变量如果非常之大，每一步都取模是必要的；对拍的时候也应该造完全极限的数据。

  • [BJWC2010]次小生成树

    最终求出来的次小生成树的答案可以达到 \(10^{14}\)，但是最大值只开到了 \(10^9\)。

    处理方法：注意，不同的数据类型应该单独设计最大值，最大值尽量不要多个数据类型通用。

  • 「CF1442D」Sum

    最开始，给每个数组开一个 vector，里面存的是真实值，所以范围是 \([0,10^8]\)，用 int 完全装得下。

    后来，发现不应该装真实值，应该装前缀和，所以就改了内容，没改类型，范围变成了 \([0,10^{14}]\)，int 就会爆炸。

    这样的问题应该在最初编写期就解决，这说明思考还不完全就着急写代码了。

取模安全

其实就是计算过程中，尤其是取模，很容易写着写着就忘记取模了。

简单的加减乘除还比较容易记住，但是进行像自加、自减、赋字面量这样的运算的时候很容易忘记取模。

比较安全的做法是：

  • 封装几个函数替代常用的运算，然后在函数内部取模。运算时强制使用它们；
  • 封装模域类，然后只用这个类运算。这个对于多模数的情况比较友好；

常见的问题有：

  • 注意特殊的模数，尤其是题目输入模数的时候，注意模数是否可能为 1。

    例如，有的题目取模的模数是单独输入的，特别注意模数可否为 1，特别注意赋的初始值是否落在正确的范围内，不确定可以取一下模；

    没有把握就在输出取模，虽然这看起来也只是权益之计。

浮点数

  • 「Gym102798E」So Many Possibilities...

    实数概率 DP，因为 \(\epsilon\) 设得太大，导致用它判空状态的时候将有效状态也判成空，漏了不少结果，答案偏小......

    用实数算 DP 的时候，没有必要用上 \(\epsilon\)。需要用来卡常的时候，算好可能的系数量级，然后反推 \(\epsilon\) 的大小；宁可设得小一点，也不要漏掉有效状态。不要再出现这样不知所谓还被卡了半天的错误！

  • 模拟赛题目。

    需要对浮点数进行 \(10^6\) 组运算，每组运算 +,-,*,/ 都齐了。

    结果就不出意外地爆掉了 double 的精度，只有开 long double 才能通过。

    注意 double 在大数小数混合运算时的精度问题！！！

  • 注意任何数学运算是否安全。

    例如 「POI2011 R1」避雷针 Lightning Conductor 这一题，需要注意的细节是，实值函数 \(a_j+\sqrt{|i-j|}\) 才具有单调性。虽然实际求答案的时候，\(a_j+\sqrt{|i-j|}\) 和 \(a_j+\lceil\sqrt{|i-j|}\rceil\) 是一样的，但是前者是实值函数，后者是整值函数。而在整值函数上单调性已经被破坏了，因此只要涉及到与决策有关的比较，都必须用实值而非整值。

STL 的奇妙特性

  • 众所周知，为了使操作更麻烦简化操作，STL 的 set 和 map 等关联容器内部基本上都提供了 reverse_iterator 这种迭代器。

    从字面意思就可以知道，这种迭代器是逆向访问容器的。比如 set 默认使用 < 比较，如果用 reverse_iterator 来访问它则会从大到小遍历 set 的元素。相应地，容器也会有 rbegin() 和 rend() 这样的函数，一看就懂了。

    问题是，reverse_iterator 的运算也是和 iterator 呈镜像对称。比如 ++ reverse_iterator，那么从 set 原本的顺序来看，就相当于向变小的方向移动，反过来也类似。

    如果和 iterator 混用就很容易弄错，比如今天上午我就调了 0.5 h。

    此外，一般来说容器的 erase() 都只会接受 iterator。既不可以往里面丢 reverse_iterator，也并不存在 rerase() 这样的函数。

  • 对于 vector 这样使用 random access iterator 的容器，一般来说使用迭代器访问的效率低于下标访问。

    另外，如果用 for( x : y ) 这样的循环，那么内部是使用迭代器实现的，因此需要注意大数据下的运行效率。

  • set 如果删除不存在的元素，那么它不会 RE，而是会直接略过这一次操作。相当于是它会自己检查元素是否存在。

  • vector 的 resize() 只会对新添加的元素执行构造函数（或者进行指定的初始化，如果存在第二个参数的话），不会修改已有的元素。

读题有误

  • 「SGU176」Flow Construction

    有点奇怪。题目里面说 There is no pipe which connects nodes number 1 and N，但是它的真正含义是不存在从 1 流向 \(n\) 的管道，但是可以存在从 \(n\) 流向 1 的管道。这个时候就会出现环流，因此需要建立新的源点与汇点，避免“源”和“汇”出现环。

    思考的时候要细致一点，每个方面都要想到；同时对于题目理解要清晰到位，结合好题目前提与背景。

其它

  • 「POJ3155」Hard Life

    奇妙的题目。构造割的时候，如果源点的出边全部满流了，那么一种割就是 \(\newcommand\set[1]{\{#1\}}[s,V\setminus \set{s}]\)，然而这显然不是我们想要的。

    为了避免这种情况，我们必须调整答案，使得源点的出边略有剩余容量；具体操作起来就是让答案变小一点，而后从 \(s\) 开始遍历寻找一组割。

  • 任何时候，使用 DFS 传回 bool 信息表示某个过程是否已经结束时，应该在任何一次递归调用结束之后，查询返回值并判断是否应该结束过程。否则会导致各种乱七八糟的问题。

  • 多组数据，注意输出换行!!!

    不是开玩笑，尤其是在用 cout 输出的时候。由于不常用，就很容易忘记输出 endl。

  • [CF1408E]Avoid Rainbow Cycles

    最大生成树，运算符直接重载为了小于。

  • 【UR #2】跳蚤公路

    循环变量用上了不常用的名字，结果之后就写错名字：

        for( 对 i 循环 )
        for( int u = 1 ; i <= n ; u ++ ) //......

    处理方式：尽量规避奇怪的循环变量名称。

学习杂记

相关

标签