Skip to content

Latest commit

 

History

History
170 lines (120 loc) · 4.14 KB

解题技巧.md

File metadata and controls

170 lines (120 loc) · 4.14 KB

1. 解题技巧

1.1. 思维篇

1.1.1. 编程前

  • 简化逻辑的充分条件是：在编写代码前充分思考
  • 必须考虑到所有的约束条件，同时考虑到所有的无约束条件
  • 必须考虑时间复杂度和空间复杂度
  • 一般认为，1 秒钟可以处理 1e8 次操作

1.1.2. 编程中

  • 算法题要求效率优先：
    • 不要吝啬大括号！不要吝啬大括号！不要吝啬大括号！
    • 不要在语法上找捷径！这是算法题，不是语法题！
    • 及时转变思路，重写代码！
  • 变量声明的原则：哪里需要，哪里声明
  • 优先用 double
  • 总是为循环注释，以明晰到底在循环什么

1.1.3. 测试

  • 数据均非法的输入
  • 边界数据
  • 含 0 的数据
  • 不仅要考察输入，还要考察特殊的输出，比如没有输出时的情况

1.2. 语法篇

1.2.1. 理解指针：钥匙类比法

  • 指针：钥匙
  • 指针保存的变量：钥匙对应的房间
  • 指针变量：保管钥匙的盒子
  • 按值传递指针：复制一把钥匙
  • 按引用传递指针：借出该钥匙

1.2.2. 避免浮点数误差：引入极小数 eps

经验来看，在浮点数比较大小时，带上区间的比较是稳妥的，可以参考以下方案：

#define Equ(a, b) ((fabs((a)-(b)))<(eps))
#define More(a,b) (((a)-(b))>(eps))
#define Less(a,b) (((a)-(b))<(-eps))
#define MoreEqu(a,b) (((a)-(b))>(-eps))
#define LessEqu(a,b) (((a)-(b))<(eps))

const double eps = 1e-8;  // 经验来看，该值最好

1.2.3. 多点测试：while/EOF

未知输入量时，用 while/EOF 方法：

while(scanf() != EOF)  // scanf 返回正确接受输入的个数，遇到文件尾时返回 EOF
// 或
while (cin >> coe >> exp)  // cin 返回 istream& 类型的 cin 自身，遇到文件尾时返回 0

1.2.4. 输入与输出

1.2.4.1. 误读 \n

// 输入字符型变量时，可以这样避免读入 '\n'：
scanf("\n%c %c %d", &s, &e, &w);
// 或者这样
scanf("%*c%c %c %d", &s, &e, &w);  // %*c 用于省略一个输入项，用处更广泛
// cin 或 scanf 不会消除行末的 '\n'；getline 会消除
// 因此用 getline 时要防止前面的未消除的换行，比如用 getchar() 消除
// PAT 不再支持 <cstdio>：gets()，可以用cin.getline() 来替代。此两个函数都是遇到 '\n'停止读取
cin.getline(c_str, max_length);  // getline 用法

1.2.4.2. sscanf 与 sprintf

// 以下函数均在 stdio 中

scanf("%d", &n);  // 方向：—→
printf("%d", n);  // 方向：←—

// 约等于

sscanf(screen, "%d", &n);  // 方向：—→
sprintf(screen, "%d", n);  // 方向：←—

C 语言中的文件操作

// 使用 r+ 可以同时读写

// open file
FILE *fp = fopen(path, "r");

// read file
fscanf(fp, "%d", &n);

// print file
fprintf(fp, "%d", n);

// close file
flose(fp);

1.2.5. 函数

函数 说明 包
strcmp(a, b) 返回 a - b 的值（一种理解记忆返回值的方法） <string.h>
cmp() 返回类型可以定义为 int，但必须用 bool 返回 自定义
reverse() 反转一个序列 <algorithm>
next_permutation() 得到下个全排列，结合 do...while 输出全部全排列 <algorithm>
fill() <algorithm>
memset() <string.h>
lower_bound(first, last, val) 和 upper_bound(first, last, val) [first, last) 中返回第一个大于等于（大于）val 的索引 <algorithm>

1.2.6. 结构体：赋初值

struct {
    char name[MAXC], id[MAXC];
    int grade;
} best={"", "", 0}, worst={"", "", 100};

1.2.7. 优美书写：利用逗号运算符

printf(cnt-1 ? "%s " : "%s\n", words[cnt-1]), cnt--;

1.2.8. 编译错误

  • 不明确的符号：多是因为定义的变量符号与 std 命名空间中的变量名冲突了

1.2.9. STL

// 使用带自定义比较结构体的 priority_queue

struct cmp {
    bool operator () (Node* a, Node* b)
    {
        return a->data > b->data;
    }
};

priority_queue<Node*, vector<Node*>, cmp> node_q;

1.3. 底层篇

1.3.1. 数据的存储

  • 正溢出，和非正；负溢出，和非负