Loading 问题求解指导 - 编程技巧篇
layout:true <div class="remark-footer">Tianyun Zhang</div> --- class: remark-title # 问题求解指导 - 编程技巧篇 <div style="display: flex; justify-content: center; text-align: center;" id="qrcode"></div> <div class="my-3">https://doowzs.com/slides/2020-03-21-problem-solving-coding-cheats/</div> <hr class="fade my-3"/> Last modified at 2020-04-10 19:27 CST --- ## 指导思想 - 写代码要快，但是不能写$hit code（不是参加ICPC手速大赛） - CodeForces的出题理念和对出题人的要求很好（我某次读到别人的博客） - 一行只做一件事情，别搞什么逗号分隔语句 - 加括号，加大括号`{ }`，`if for while`别只换行（迟早被坑） - 按照这个方法写代码的目的是 - 写OJ变得更加快捷（但题目难度并不会变得简单……） - 提高写代码的速度 - 并不适用于写工程代码，也不适用于求职使用 -- ## 头文件 如果你是gcc用户，那么你可以享受豪华的all-in-one头文件 ```C++ #include <bits/stdc++.h> using namespace std; ``` 如果你是clang用户（macOS），很遗憾没得用。 --- ## Keep It Simple and Stupid 如何交换两个数`a`和`b`呢？ ```C++ int tmp = a; a = b; b = tmp; ``` -- ```C++ a = a ^ b; // one-liner: a^=b^=a^=b; b = a ^ b; a = a ^ b; ``` -- ```C++ swap(a, b); ``` -- ```C++ printf("%d %d", b, a); ``` --- ## 漂亮的代码是你减少bug的第一步 漂亮的代码可以帮助你和别人清晰的定位每一块语句的作用域和功能，进而将整个程序拆散依次阅读。 而糟糕的代码是必定会带来bug的……~~（很想很想很想放同学代码实录）~~ ```C++ for (int i = 0; i < n; ++i) ++input; ++answer; // 一个IDE自动格式化就能发现的问题 ``` 喜欢什么样式的代码不重要，至少要达到统一。 CLion在Windows下可以直接按`Ctrl+Alt+L`进行格式化，其他**现代IDE**也都有。 -- ## 别瞎用宏 写个问求OJ能有多少字符，别连个`for`循环还要整个宏，非常不建议新手这么玩，别人看的都晕了。 --- ## 不要全都塞在`main`里 对于一些简单的题目，一个简短的`main`函数就能解决。 但是对于一些复杂，特别是涉及多组输入、递归等算法的题目，推荐你把程序拆开来处理： ```C++ void init() { // 预处理 } void solve(...) { // 求解一次，可以在函数内输出，也可以把答案作为返回值 } int main() { // 处理读入 init(); solve(); // 求解并输出（按照自己喜好处理） return 0; } ``` --- ## 输入输出 对于输入输出量不大的题目，我建议使用`cin`、`cout`。 对于完成OJ和CodeForces等平台的题目，`scanf`是你会用到的最快的读入了，没有必要研究读入外挂。 ```C++ #include <bits/stdc++.h> #define _ \ /* 关闭缓冲区同步 */ cin.sync_with_stdio(false); \ cout.sync_with_stdio(false); \ cin.tie(NULL), cout.tie(NULL); using namespace std; int main() { _ // ...... return 0; } ``` --- ## 正经的代码缩进 ### DO ```C++ int main() { cin >> n; for (int i = 0; i < n; ++i) { cin >> a >> b; cout << a + b << endl; } return 0; } ``` ### DON'T ```C++ int main() { cin >> n; for(int i=0;i <n;i ++) cin >> a >>b; cout<<a+b<<endl;} // WTF?? ``` --- ## 正经的变量名 ### DO ```C++ int main() { cin >> T; while (T--) { // solve a test case } return 0; } ``` ### DON'T ```C++ int main() { cin >> _; for (; _; _--) solve(); } ``` --- ## 我内存还蛮大的 ### DO ```C++ int array[1000006] = {}; ``` ### DON'T ```C++ int a[1000006]; // 养成随手初始化的好习惯 ``` ```C++ int a[100006] = {}; // 经典错误 ``` ```C++ int a[1000000] = {}; // 多分配几个保平安 ``` --- ## STL, YES! ### DO ```C++ #include <vector> # 数组 #include <pair> # 坐标 #include <stack> # 栈 #include <queue> # 队列和优先队列（堆），另有双端队列<deque> #include <set> # 集合，另有哈希表<unordered_set> #include <multiset> # 可重复集合 #include <map> # 映射，另有<unordered_map> ``` ~~就做个问求OJ，用不到pbds这种鬼畜的东西。~~ 什么？你说你STL都不会用？[用到的时候看手册学一下呗](https://en.cppreference.com/w/) ### MAYBE... ```C++ int stack[MAXN] = {}; // STL未必慢多少，真的没必要 ``` --- ## Sorting ### DO ```C++ sort(a, a + n); // 数组 sort(v.begin(), v.end()); // 容器 ``` 面对需要以不同标准进行排序时，可以有以下几种方式： - 重载小于运算符`<` - 写一个比较类，重载函数调用运算符`()` - 写一个比较函数，或使用lambda表达式 ### DON'T ```C++ qsort(a, a + n); // qsort虽然叫quick，但实际上…… ``` --- ## 处理复杂的结构 推荐使用类`class`而不是结构体`struct`，虽然在做OJ的时候差别不大。 ```C++ class Node { public: int pos, val; bool operator<(const Node &rhs) const { return val < rhs.val; // 按照val关键字升序 } }; ``` 通过重载小于运算符，类`Class`可以用于： - 普通的比较 - 调用标准库排序函数 - 创建`map`、`priority_queue`等需要偏序关系的容器 --- ## In Case of Emergency 当你遇到了一个怎么都de不出来的bug时： - 喝杯Java 走一走 歇一歇 - 跪求大佬帮帮你看看代码 - 推倒重写（非 常 有 效） -- ## Get Out of Box 如果遇到了C/C++难以解决的问题…… 你还有Java和~~计算器~~Python3和其他一揽子语言（很遗憾问求OJ并不支持）可以选 --- class: remark-title # Thanks