教你如何在做题时见祖宗

NewbieZZZ · 2024-09-21 20:01:05 · 个人记录

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second

int n, m;
string s[3003];
pair<char, char> a[3003];

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1; i<=n; ++i){
        cin >> s[i];
        s[i] = ' ' + s[i];
        a[i].fi = 'z' + 1, a[i].se = 'a' - 1;
        for(int j=1; j<=m; ++j){
            a[i].fi = min(a[i].fi, s[i][j]);
            a[i].se = max(a[i].se, s[i][j]);
        }
    }
    for(int i=1; i<=n; ++i){
        bool flag = 1;
        for(int j=1; j<=n; ++j){
            if(j != i && a[j].se <= a[i].fi){ // max < min
                flag = 0; break;
            }
        }
        cout << flag;
    }
    return 0;
}

这里集合了本人所有（非）知识性错误，以供参考。“正赛”栏目中，会有比赛注意事项。

后跟的数字是出现次数。粗体为频繁出现/极为致命的错误。

日常

知识性

二分

这个玩意给了我非常多不好的回忆。S2024T2 的爆 0，vp ICPC 贡献的 4 发罚时（甚至是队友帮忙才过的），以及现在都不太记得清的模板……

DP/计数

• 转移时记得要取模就模，模数不要写错。若数据范围较大，勤取模，小心爆了。
• 如果需要，记得 memset 整个数组为正无穷或负无穷。不要漏写或写错边界条件。
  • memset 成负无穷时注意不要 0xcf，建议 -0x3f（当然 0xc0 也是对的）。
• 想清楚转移方程是否正确，最好证出来，证不出来也要拍出来。
  • 如果想到了复杂度并不保证正确的 DP，不要放弃这个思路，也许可以优化。
• 树形 DP 有时要特判叶子节点。
• 算好空间。一般来说，滚动数组能开就开，压维能压就压。
• 记得特判无解。

数据结构

• 空间要开够。线段树 4 倍空间，主席树 Q \log N。

• 注意不要 pushup 或者 pushdown 叶子节点。

• 标记下传记得处理多个标记叠加。

• ST 表要预处理 log。

• 还有并查集要注意合并的是祖先而不是结点本身。

  错误：

  fa[x]=y;

  正确：

  fa[find(x)]=find(y);

  图论

• 看清有向图无向图。

• 无向图空间要开够。

• 最短路注意有没有负边权，有的话要用 SPFA。记得判负环。

• 注意最短路初始化距离数组为正无穷。

• 欧拉路要特判回路。

• Floyd 三层循环顺序是 k，i，j。

• 拓扑排序需要满足是 DAG。若可以拓扑，请记得缩点。

• 树上 DFS 记得不要从儿子 DFS 回父亲。

• 树剖链修改或链查询记得是 if(dep[top[x]]<dep[top[y]]) swap(x,y); 而不是 if(dep[x]<dep[y]) swap(x,y)。

数学

• 组合数学中求 C^m_n or n \choose m 要特判 n<m 返回 0。
• 预处理阶乘算组合数时要注意 0!=1。
• 快速幂如果模数平方爆 long long 要写龟速乘。注意此时快速幂复杂度为 O(\log^2 n)。

STL

• 定义超过 3 \times 10^5 个 queue/stack/deque 基本上一定会爆空间。

• map 常数很大，一般来说数据规模到 10^6 就可以放弃了。

• vector 的 insert 和 erase 可能会被卡到 O(n)。

• map 系列和 set 系列是 O(\log n) 的。特别地，别用 unordered_map，会被卡。

• map 判断是否存了一个数的时候要用 mp.count(x)，而不是 mp[x]（因为可能存了 0 你却当没有）。

• set 中 lower_bound 要用 s.lower_bound(x)。upper_bound 同理。

• 还有 set 重载小于号的时候要写上所有关键字。去重的标准是 !(a<b||b<a)。

  错误：

  struct node
  {
    int fi,se;
  };
  bool operator<(node x,node y)
  {
    return x.fi<y.fi;
  }

  正确：

  struct node
  {
    int fi,se;
  };
  bool operator<(node x,node y)
  {
    return x.fi!=y.fi?x.fi<y.fi:x.se<y.se;
  }

• multiset 删一个用 s.erase(s.find(x))，删全部用 s.erase(x)。

非知识性

• 多测不清空：1；
• 不删调试：1；
• 未开 long long：2；

比赛

common

• 记错结束时间，忘记提交：1；

正赛

• 调试时修改 freopen 打开的文件名，并忘记改回：2；
• 不在 Linux 虚拟机上尝试编译，导致 CE：1；
• 不删调试：3；