分类 默认分类 下的文章

C++ reference

__builtin

__builtin_clz(x)
返回x的二进制前导0的个数。
__builtin_ctz(x)
返回x的二进制末尾0的个数。
__builtin_popcount(x)
返回x的二进制中1的个数。
以上函数的long long版本:
__builtin_clzll
__builtin_ctzll
__builtin_popcountll

<cmath>

ceil(x) x向上取整
floor(x) x向下取整
fmod(x, y) x / y的浮点数余数

pow(x, y) x的y次幂
exp(x) e的x次幂
sqrt(x) x的平方根
cbrt(x) x的立方根
log(x) x以e为底的对数
log10(x) x以10为底的对数
log2(x) x以2为底的对数

atan2(y, x) y/x的反正切值,即点(x, y)与x轴正方向的夹角(返回值范围$[-\pi, \pi)$),atan2(0, 0) = 0
hypot(x, y) 返回直角三角形斜边的长度:$\sqrt{x^2 +y^2}$)

<random>

mt19937 mt_rand(time(0)); 初始化随机数生成器
mt_rand() 返回一个随机的unsigned int值(0 ~ 4294967295)
mt19937 mt_rand(chrono::steady_clock::now().time_since_epoch().count()); 快速更新种子(适合对拍)

<cctype>

isalnum(c) 如果参数是字母或数字,该函数返回true
isalpha(c) 如果参数是字母,该函数返回true
isdigit(c) 如果参数是数字,该函数返回true
islower(c) 如果参数是小写字母,该函数返回true
isupper(c) 如果参数是大写字母,该函数返回true
isxdigit(c) 如果参数是十六进制的数字,即0~9、a~f、A~F,该函数返回true
tolower(c) 如果参数是大写字符,则返回其小写,否则返回该参数
toupper(c) 如果参数是小写字母,则返回其大写,否则返回该参数

<algorithm>

max_element(a, a + n)
返回序列中最大值的地址。
min_element(a, a + n)
返回序列中最小值的地址。
nth_element(a, a + k, a + n)
将第k大元素放到它该放的位置上,左边元素都小于它,右边元素都大于它。O(n)。
count(a, a + n, x)
返回序列中x的出现次数。
fill(a, a + n, x)
将序列中的元素全部初始化为x。
copy(a, a + n, b)
将序列a中的n个元素复制到b中。
reverse(a, a + n)
翻转一个n个元素的序列。
shuffle(a, a + n, mt_rand)
随机打乱一个n个元素的序列。
unique(a, a + n)
去除序列中相邻的重复元素,返回去重后的尾地址。
next_permutation(a, a + n)
prev_permutation(a, a + n)
把序列看作一个排列,求这些元素构成的全排列中,字典序排在下一个/上一个的排列,并直接在序列上更新。
若不存在字典序更靠后/靠前的排列,则返回false(但此时也会更新),否则返回true。
next_permutation({4, 3, 2, 1}) = {1, 2, 3, 4}
binary_search(a, a + n, x)
查找有序序列中是否存在元素x,找到返回1,否则返回0。
lower_bound(a, a + n, x)
返回有序序列中能插入x的最小地址。
upper_bound(a, a + n, x)
返回有序序列中能插入x的最大地址。

<numeric>

accumulate(a, a + n, 0)
返回数组a中元素的和。
partial_sum(a, a + n, sum) // sum[0] = a[0], sum[i] = sum[i - 1] + a[i]
计算数组a中元素的前缀和存入数组sum中(支持原地更新)。
adjacent_difference(a, a + n, diff) // diff[0] = a[0], diff[i] = a[i] - a[i - 1]
计算数组a中元素的差分存入数组diff中(支持原地更新)。
iota(a, a + n + 1, 0)
相当于for (...) a[i] = i;

<string>

s.find(s1) / s.rfind(s1)
返回字符串s1在s中第一次/最后一次出现的位置,如果没有找到,则返回-1。
s.substr(i, len)
返回字符串s中下标从i开始长度为len的子串。
s.c_str()
返回字符串s的C风格字符指针。
stoi(s) // string->int
stoll(s) // string->long long
stoi(s, 0, 16) / stoll(s, 0, 16) // 把s看成16进制,支持2-36进制
stoull(s) // string->unsigned long long
stod(s) // string->double
stold(s) // string->long double
把字符串s转换成数值。
to_string(x)
把数值x转换为字符串。

<bitset>

~s:对s按位取反
&, |, ^:按位与、或、异或
<<, >>:左移、右移
==, !=:比较两个bitset是否相等
s[k]:s的第k位(最低位是第0位)。
s.count()
返回s中有多少位为1。
s.any() / s.none()
若s所有位都为0,则s.any()返回false,s.none()返回true。
若s至少一位为1,则s.any()返回true,s.none()返回false。
s.set() / s.reset() / s.flip()
把s的所有位变为1 / 变为0 / 取反。
s.to_string() / s.to_ulong() / s.to_ullong()
返回s的字符串/unsigned long/unsigned long long表示。

<queue>

struct Node {
    int x, y;
    double val;
    bool operator < (const Node &b) const { return val < b.val; }
};
priority_queue<Node> q;

自定义比较运算符的priority_queue(val从大到小)。

struct cmp {
    bool operator () (const Node &x, const Node &y) { return x.val > y.val; }
};
priority_queue<Node, vector<Node>, cmp> q;

自定义比较运算符的priority_queue(val从小到大)。

<set>

struct Node {
    int id, val;
    friend bool operator < (const Node &x, const Node &y) {
        return x.val < y.val;
    }
};
set<Node> st;

自定义比较运算符的set(val从小到大)。

struct cmp {
    bool operator () (const Node &x, const Node &y) { return x.val > y.val; }
};
set<Node, cmp> st;

自定义比较运算符的set(val从大到小)。
st.erase(x)
删除multiset中所有的x。
st.erase(st.find(x))
删除multiset中的一个x。

header

  • OJ评测时不会输出debug信息
  • 本地测试时使用#undef qdd屏蔽debug信息
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef qdd
#define dbg(x...) do { cerr << #x << " = "; ringo.w(x); cerr << endl; } while (0)
#else
#define dbg(...)
#endif

struct Debug {
    template<class T, class... U> void w(T x, U... y) { w(x); cerr << ", "; w(y...); }
    template<class T> void w(T x) { cerr << x; }
    template<template<class...> class T, class t> void w(T<t> v) {
        int f = 1; cerr << '{';
        for (auto x : v) { if (!f) cerr << ", "; f = 0; w(x); }
        cerr << '}';
    }
} ringo;
// -----------------------------------------------------------------------------

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    return 0;
}

快速编译运行

#!/bin/bash
g++ $1.cpp -o $1 -O2 -Wall -Dqdd && ./$1

CMakeLists.txt (for CLion)

set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -O2 -Wall -Dqdd")

macro(go A)
    add_executable(${A} ${A}.cpp)
endmacro()

go(A)
go(B)
go(C)

vimrc

syntax on
set nu
set cindent
set tabstop=4
set shiftwidth=4
set softtabstop=4
set expandtab
set mouse=a

Fib

#include <iostream>
using ull = unsigned long long;
const ull N = 1e6;
// stack test
ull f(ull x) {
    static ull F[N] = {1, 1};
    return F[x] ? F[x] : F[x] = f(x - 1) + f(x - 2);
}
// speed test
// f(2e9 - 1) = 2697763845588227525
ull f(ull x) {
    ull a = 1, b = 1, c = 0;
    for (ull i = 2; i <= x; i++) {
        c = b;
        b = a;
        a = b + c;
    }
    return a;
}
int main() {
    std::cout << f(N - 1) << '\n';
    return 0;
}

热身赛要测的东西

  • 热身赛也要带板子
  • 如果现场机器的时间不正确,尝试调整
  • 打印
  • 提问
  • 代码长度限制
  • OJ返回值:CE(是否罚时,有没有CE信息), RE, TLE, MLE, PE/OLE
  • cerr会不会WA
  • Java环境
  • Python环境
  • 读整行
  • 栈大小 -O2
  • 输出格式问题(%lld, %Lf, 行末空格和回车)
  • 本地机器速度
  • 评测机速度
  • __int128
  • C++11(auto, range-for, lambda)
  • pb_ds

您好这边建议您再WA一次呢

读题

  • 确认题意 确认题意 确认题意(e.g. 模数 要求字典序最小/最大 严格递增/不严格)
  • 读完题之后必须看一遍clarification

想题

  • 复杂度很奇怪的题($n \log ^ 3 n, n \sqrt n \log n$)可以试一下暴力
  • 猜结论的题尽量打表验证

写题

  • 难写的题不要急着上机 先在纸上列个框架
  • 对题目没把握不要硬上 上机=队伍人数--
  • 表示点/坐标不要用x1 y1 写xx yy
  • stack queue priority_queue取值前先判空
  • 排序时注意结构体的所有属性是不是考虑了
  • 想清楚到底是要multiset还是set
  • 预处理组合数 2倍上限
  • 数据结构注意数组大小(2倍,4倍,logn倍)
  • 二分答案估算一下上界 不要直接开1e18
  • 树链剖分/dfs 序,初始化或者询问不要忘记dfn
  • 确定不能用long long再开double / long double
  • 输入数据1e6以上考虑读入优化
  • 空间够开数组 不要用map / set
  • 中途出答案也要读完

调题

  • 1LL << k
  • n m i j 打反 两重 i++
  • n m k 等定义成全局变量时注意是否有同名局部变量
  • cout << (a ? b : c) << ...
  • while (!q.empty()) 不要忘记 pop
  • 欧拉降幂小心指数变成负数
  • 字符串数据集 01, 大 / 小写, 大小写 c-'0' c-'A' c-'a'
  • 多次运行结果不同 / WA样例:检查一下初始化和数组越界
  • TLE先考虑能不能少个log 再考虑常数优化
  • 求最优解时不要忘记更新当前最优解

交题

  • 看一遍clarification
  • 删除freopen和debug信息
  • 看一下数据范围,测一下边界
  • 检查一遍初始化 (如果有T Case, 必须有T>=2的样例)
  • 看一下有没有无解的情况 如果无解要输出什么
  • 构造题看一下是否要先输出ans.size()
  • 打印代码