VSCode C++ 配置与模板
设置¶
settings.json¶
{
// 删除文件不确认
"explorer.confirmDelete": false,
// 移动文件不确认
"explorer.confirmDragAndDrop": false,
// 添加希望被忽略的文件,这样一些文件虽然存在于当前工作目录下,但是不会被显示在左侧的文件浏览器里
"files.exclude": {
// dSYM 文件具有调试信息,普通使用的话不看到它就可以了
"**/*.exe": true,
"**/*.out": true,
".cph": true,
".clang-format": true,
},
// 启用 code-runner 快捷键
"workspaceKeybindings.code-runner.enable": true,
"code-runner.executorMap": {
/* ------ 编译、运行只有一个文件的cpp文件 ------ */
// 注：路径中有空格不会出现问题
"cpp": "clang++ $fullFileName -o $workspaceRoot/main.out -W -Wall -O2 -std=c++20 -stdlib=libc++ -I$workspaceRoot/lib && $workspaceRoot/main.out",
// 其中 $fullFileName 是绝对路径，是主文件
// 自己决定是否加入 && rm $dir\"$fileNameWithoutExt\"\".out\"（也可以添加"files.exclude"）
/* ------ 编译、运行多个cpp文件 ------ */
// "cpp": "g++ $fullFileName <file_to_link> -o $dir\"$fileNameWithoutExt\"\".out\" -W -Wall -O2 -std=c++17 && $dir\"$fileNameWithoutExt\"\".out\"",
// <file_to_link>的写法：
// 一般的，你也可以直接写绝对路径
// \"/path/xxxx.cpp\"
// 如果你链接的cpp文件和主文件在一个目录下：
// $dir\"xxxx.cpp\"
// 更一般的，如果你链接的cpp文件不和主文件在一个目录下，需要从当前VSCode的工作目录补充相对路径从而形成绝对路径：
// $workspaceRoot\"relative/path/xxxx.cpp\"
/* ------ 编译c文件 ------ */
"c": "clang $fullFileName -o $workspaceRoot/main.out -W -Wall -O2 -std=c11 && $workspaceRoot/main.out",
// "c": "gcc $fullFileName <file_to_link> -o $dir\"$fileNameWithoutExt\"\".out\" -W -Wall -O2 -std=c17 && $dir\"$fileNameWithoutExt\"\".out\"",
},
// Whether to clear previous output before each run (default is false):
"code-runner.clearPreviousOutput": true,
// Whether to save all files before running (default is false):
"code-runner.saveAllFilesBeforeRun": false,
// Whether to save the current file before running (default is false):
"code-runner.saveFileBeforeRun": true,
// Whether to show extra execution message like [Running] ... and [Done] ... (default is true):
"code-runner.showExecutionMessage": true, // cannot see that message is you set "code-runner.runInTerminal" to true
// Whether to run code in Integrated Terminal (only support to run whole file in Integrated Terminal, neither untitled file nor code snippet) (default is false):
"code-runner.runInTerminal": true, // cannot input data when setting to false
// Whether to preserve focus on code editor after code run is triggered (default is true, the code editor will keep focus; when it is false, Terminal or Output Channel will take focus):
"code-runner.preserveFocus": false,
// Whether to ignore selection to always run entire file. (Default is false)
"code-runner.ignoreSelection": true,
// 本地 clangd 路径
// "clangd.path": "/usr/bin/clangd",
// "clangd.arguments": [
// // "--header-insertion=never", // 是否重复插入头文件，用万能头的话设置成never
// "--query-driver=/usr/bin/clang++", // 将编译的所有工具链都添加进 LSP
// "--log=verbose"
// ],
// 没有找到 compile_commands.json 时默认的编译器参数是什么
"clangd.fallbackFlags": [
"-W",
"-Wall",
"-O2",
"-std=c++20",
"-stdlib=libc++",
"-I/root/cpp/lib",
],
"C_Cpp.intelliSenseEngine": "disabled",
"lldb.launch.expressions": "native",
}
launch.json¶
{
// One of the key features of Visual Studio Code is its great debugging support.
// VS Code's built-in debugger helps accelerate your edit, compile and debug loop.
// VS Code keeps debugging configuration information in a launch.json file
// located in a .vscode folder in your workspace (project root folder).
"version": "0.2.0",
"configurations": [
{
"type": "lldb", // lldb 表示使用 CodeLLDB 来调试
"request": "launch", // 启动调试
"name": "C++ Debug", // launch 配置的名字
"preLaunchTask": "clang++ compile", // 启动调试任务前先执行 task.json 的 "clang++ compile"
"program": "${workspaceFolder}/main.out", // 调试的程序
"args": [], // 程序参数
"env": {}, // 环境变量
"cwd": "${workspaceFolder}",
"stopOnEntry": false, // 调试开始时在 main 函数中停止
"terminal": "integrated", // 使用 vscode 自带的终端进行调试
}
]
}
task.json¶
{
// Tasks in VS Code can be configured to run scripts and start processes
// so that many of these existing tools can be used from within VS Code
// without having to enter a command line or write new code.
// Workspace or folder specific tasks are configured from the tasks.json file in the .vscode folder for a workspace.
"version": "2.0.0",
"tasks": [
{
// The task's label used in the user interface.
// Terminal -> Run Task... 看到的名字
"label": "clang++ compile",
// The task's type. For a custom task, this can either be shell or process.
// If shell is specified, the command is interpreted as a shell command (for example: bash, cmd, or PowerShell).
// If process is specified, the command is interpreted as a process to execute.
"type": "shell", // shell: 输入命令
// The actual command to execute.
// 因为g++已经在环境变量中了，所以我们这里写命令就行不用写g++的绝对路径
"command": "clang++",
"args": [
"${file}", // 表示当前文件（绝对路径）
// 在这里添加你还需要链接的.cpp文件
"-o",
"${workspaceFolder}/main.out",
"-W",
"-Wall",
"-g",
"-std=c++20",
"-stdlib=libc++",
"-I",
"${workspaceFolder}/lib",
"-fstandalone-debug",
],
// Defines to which execution group this task belongs to.
// It supports "build" to add it to the build group and "test" to add it to the test group.
// Tasks that belong to the build/test group can be executed by running Run Build/Test Task from the Command Palette (sft cmd P).
// Valid values:
// "build",
// {"kind":"build","isDefault":true},
// "test",
// {"kind":"test","isDefault":true},
// "none".
"group": {
"kind": "build",
"isDefault": true, // Defines if this task is the default task in the group.
},
// Configures the panel that is used to present the task's output and reads its input.
"presentation": {
// Controls whether the executed command is echoed to the panel. Default is true.
"echo": true, // 打开可以看到编译的命令，把命令本身输出一次
// Controls whether the terminal running the task is revealed or not. Default is "always".
// always: Always reveals the terminal when this task is executed.
// silent: Only reveals the terminal if the task exits with an error or the problem matcher finds an error.(会显示错误，但不会显示警告)
// never: Never reveals the terminal when this task is executed.
"reveal": "silent", // 控制在集成终端中是否显示。如果没问题那我不希望终端被切换、如果有问题我希望能看到编译过程哪里出错，所以选silent(可能always会好一些)
// Controls whether the panel takes focus. Default is false.
"focus": false, // 我的理解是：是否将鼠标移过去。因为这个是编译任务，我们不需要输入什么东西，所以选false
// Controls if the panel is shared between tasks, dedicated to this task or a new one is created on every run.
"panel": "shared", // shared:不同任务的输出使用同一个终端panel（为了少生成几个panel我们选shared）
// Controls whether to show the `Terminal will be reused by tasks, press any key to close it` message.
"showReuseMessage": true, // 就一句话，你想看就true，不想看就false
// Controls whether the terminal is cleared before executing the task.
"clear": false, // 还是保留之前的task输出信息比较好。所以不清理
},
// Other two choices: options & runOptions (cmd I to use IntelliSense)
"options": {
// The current working directory of the executed program or script. If omitted Code's current workspace root is used.
"cwd": "${workspaceFolder}", // 默认就是这个，删掉也没问题
},
// problemMatcher: 用正则表达式提取g++的输出中的错误信息并将其显示到VS Code下方的Problems窗口
// check: https://code.visualstudio.com/docs/editor/tasks#_defining-a-problem-matcher
"problemMatcher": {
"owner": "cpp",
"fileLocation": "absolute",
"pattern": {
"regexp": "^(.*):(\\d+):(\\d+):\\s+(warning|error):\\s+(.*)$",
"file": 1,
"line": 2,
"column": 3,
"severity": 4,
"message": 5,
},
},
// 官网教程 https://code.visualstudio.com/docs/cpp/config-clang-mac#_build-helloworldcpp
// 提到了另一种problemMatcher，但试了之后好像不起作用，甚至还把我原本的电脑搞出了一些问题……
},
]
}
.clang-format¶
BasedOnStyle: LLVM
UseTab: Never
IndentWidth: 4
TabWidth: 4
BreakBeforeBraces: Allman
AllowShortIfStatementsOnASingleLine: false
IndentCaseLabels: false
ColumnLimit: 0
AccessModifierOffset: -4
NamespaceIndentation: All
FixNamespaceComments: false
算法模板¶
使用教程：
- 在 VSCode 工作区的 .vscode 文件夹下创建 XXX.code-snippets 文件，其中 XXX 表示工作区的名字，例如 cpp 工作区，就创建 cpp.code-snippets。
- 复制下列内容，粘贴进去。
- 使用 prefix 字段的快捷键就可以呼出代码模板，例如 tpdsu 就可以输出并查集模板。
- 快速生成新模板，参考 snippet generator
{
"C语言默认代码模板": {
"prefix": "cyy",
"body": [
"#include <stdio.h>",
"#include <string.h>",
"",
"$0",
"",
"int main()",
"{",
" return 0;",
"}"
],
"description": "C语言默认代码模板"
},
"C++默认代码模板": {
"prefix": "cpp",
"body": [
"#include <iostream>",
"",
"using namespace std;",
"$1",
"int main()",
"{",
"\t$0",
" return 0;",
"}"
],
"description": "C++默认代码模板"
},
"重定向标准输入到文件": {
"prefix": "tpfreopen",
"body": [
"freopen(\"in.txt\", \"r\", stdin);",
],
"description": "重定向标准输入到文件"
},
"cin快读": {
"prefix": "tpcin",
"body": [
"ios::sync_with_stdio(false);",
"cin.tie(nullptr);"
],
"description": "cin快读"
},
"并查集": {
"prefix": "tpdsu",
"body": [
"class DSU",
"{",
"public:",
" explicit DSU(int n) : parent_or_size(n, -1) {}",
"",
" int merge(int a, int b)",
" {",
" int x = leader(a), y = leader(b);",
" if (x == y)",
" return x;",
" if (-parent_or_size[x] < -parent_or_size[y])",
" swap(x, y);",
" parent_or_size[x] += parent_or_size[y];",
" parent_or_size[y] = x;",
" return x;",
" }",
"",
" int leader(int a) { return parent_or_size[a] < 0 ? a : parent_or_size[a] = leader(parent_or_size[a]); }",
"",
" bool same(int a, int b) { return leader(a) == leader(b); }",
"",
" int size(int a) { return -parent_or_size[leader(a)]; }",
"",
"private:",
" vector<int> parent_or_size;",
"};"
],
"description": "并查集（按秩合并）"
},
"并查集(group)": {
"prefix": "tpdsu",
"body": [
"class DSU",
"{",
"public:",
" explicit DSU(int n) : parent_or_size(n, -1) {}",
"",
" int merge(int a, int b)",
" {",
" int x = leader(a), y = leader(b);",
" if (x == y)",
" return x;",
" if (-parent_or_size[x] < -parent_or_size[y])",
" swap(x, y);",
" parent_or_size[x] += parent_or_size[y];",
" parent_or_size[y] = x;",
" return x;",
" }",
"",
" int leader(int a) { return parent_or_size[a] < 0 ? a : parent_or_size[a] = leader(parent_or_size[a]); }",
"",
" bool same(int a, int b) { return leader(a) == leader(b); }",
"",
" int size(int a) { return -parent_or_size[leader(a)]; }",
"",
" vector<vector<int>> group()",
" {",
" int n = parent_or_size.size();",
" std::vector<int> leader_buf(n), group_size(n);",
" for (int i = 0; i < n; i++)",
" {",
" leader_buf[i] = leader(i);",
" group_size[leader_buf[i]]++;",
" }",
" std::vector<std::vector<int>> result(n);",
" for (int i = 0; i < n; i++)",
" result[i].reserve(group_size[i]);",
" for (int i = 0; i < n; i++)",
" result[leader_buf[i]].push_back(i);",
" result.erase(",
" std::remove_if(result.begin(), result.end(),",
" [&](const std::vector<int> &v)",
" { return v.empty(); }),",
" result.end());",
" return result;",
" }",
"",
"private:",
" vector<int> parent_or_size;",
"};"
],
"description": "并查集(支持group)"
},
"扩展欧几里得": {
"prefix": "tpexgcd",
"body": [
"pair<LL, LL> exgcd(LL a, LL b)",
"{",
" if (b == 0)",
" return {1, 0};",
" auto [x, y] = exgcd(b, a % b);",
" return {y, x - a / b * y};",
"}",
"",
"LL inv(LL a, LL p)",
"{",
" auto [x, y] = exgcd(a, p);",
" if (x < 0)",
" x += p;",
" return x;",
"}"
],
"description": "扩展欧几里得"
},
"树状数组": {
"prefix": "tpfenwick",
"body": [
"template <typename T>",
"class FenwickTree",
"{",
"public:",
" FenwickTree(int n) : n(n), t(n + 1) {}",
"",
" void add(int x, T k)",
" {",
" for (; x <= n; x += lowbit(x))",
" t[x] += k;",
" }",
"",
" int lower_bound(T k) const",
" {",
" int x = 0;",
" T sum = 0;",
" for (int i = 1 << __lg(n); i; i >>= 1)",
" {",
" if (x + i > n || sum + t[x + i] >= k)",
" continue;",
" x += i;",
" sum += t[x];",
" }",
" return x + 1;",
" }",
"",
"private:",
" int n;",
" vector<T> t;",
"",
" int lowbit(int x) const { return x & -x; }",
"};"
],
"description": "树状数组"
},
"TreapSet普通平衡树": {
"prefix": "tptreap",
"body": [
"template <typename K, typename CMP = less<K>>",
"class TreapSet",
"{",
"public:",
" void insert(K val)",
" {",
" auto [x, temp] = split_by_val(root, val - 1);",
" auto [y, z] = split_by_val(temp, val);",
" if (y != nullptr)",
" y->inc();",
" else",
" y = new Node(val);",
" root = merge(merge(x, y), z);",
" }",
"",
" void erase(K val)",
" {",
" auto [x, temp] = split_by_val(root, val - 1);",
" auto [y, z] = split_by_val(temp, val);",
" y->dec();",
" if (y->cnt == 0)",
" {",
" delete y;",
" y = nullptr;",
" }",
" root = merge(merge(x, y), z);",
" }",
"",
" int rank(K val) const",
" {",
" auto [x, y] = split_by_val(root, val - 1);",
" int ans = get_size(x) + 1;",
" root = merge(x, y);",
" return ans;",
" }",
"",
" K kth_element(int k) const",
" {",
" auto [x, y] = split_by_rank(root, k);",
" int ans = x->max_son();",
" root = merge(x, y);",
" return ans;",
" }",
"",
" K prev_element(K val) const",
" {",
" auto [x, y] = split_by_val(root, val - 1);",
" K ans = x->max_son();",
" root = merge(x, y);",
" return ans;",
" }",
"",
" K next_element(K val) const",
" {",
" auto [x, y] = split_by_val(root, val);",
" K ans = y->min_son();",
" root = merge(x, y);",
" return ans;",
" }",
"",
" void debug() const",
" {",
" auto print = [](auto &self, Node *p) -> void",
" {",
" if (p == nullptr)",
" return;",
" self(self, p->lch);",
" for (int i = 0; i < p->cnt; i++)",
" cout << p->val << ' ';",
" self(self, p->rch);",
" };",
" print(print, root);",
" cout << endl;",
" }",
"",
"private:",
" struct Node",
" {",
" K val;",
" int pri;",
" int size = 1, cnt = 1;",
" Node *lch = nullptr;",
" Node *rch = nullptr;",
"",
" Node(int v) : val(v), pri(gen_priority()) {}",
"",
" static int gen_priority()",
" {",
" static mt19937 gen(random_device{}());",
" static uniform_int_distribution<> dis;",
" return dis(gen);",
" }",
"",
" void push_up() { size = cnt + get_size(lch) + get_size(rch); }",
"",
" void inc()",
" {",
"",
" size++;",
" cnt++;",
" }",
"",
" void dec()",
" {",
" size--;",
" cnt--;",
" }",
"",
" int max_son() const",
" {",
" const Node *p = this;",
" while (p->rch != nullptr)",
" p = p->rch;",
" return p->val;",
" }",
"",
" int min_son() const",
" {",
" const Node *p = this;",
" while (p->lch != nullptr)",
" p = p->lch;",
" return p->val;",
" }",
" };",
"",
" CMP less;",
"",
" static int get_cnt(Node *p) { return p == nullptr ? 0 : p->cnt; }",
"",
" static int get_size(Node *p) { return p == nullptr ? 0 : p->size; }",
"",
" mutable Node *root = nullptr;",
"",
" // 返回的左子树小于等于 val",
" pair<Node *, Node *> split_by_val(Node *p, K val) const",
" {",
" if (p == nullptr)",
" return {nullptr, nullptr};",
" if (less(p->val, val))",
" {",
" auto [x, y] = split_by_val(p->rch, val);",
" p->rch = x;",
" p->push_up();",
" return {p, y};",
" }",
" else if (less(val, p->val))",
" {",
" auto [x, y] = split_by_val(p->lch, val);",
" p->lch = y;",
" p->push_up();",
" return {x, p};",
" }",
" else",
" {",
" Node *y = p->rch;",
" p->rch = nullptr;",
" p->push_up();",
" return {p, y};",
" }",
" }",
"",
" // 返回的左子树至少有 k 个元素",
" pair<Node *, Node *> split_by_rank(Node *p, int k) const",
" {",
" if (p == nullptr)",
" return {nullptr, nullptr};",
" int lch_size = get_size(p->lch);",
" int mid_cnt = get_cnt(p);",
" if (lch_size + mid_cnt < k)",
" {",
" auto [x, y] = split_by_rank(p->rch, k - lch_size - mid_cnt);",
" p->rch = x;",
" p->push_up();",
" return {p, y};",
" }",
" else if (lch_size >= k)",
" {",
" auto [x, y] = split_by_rank(p->lch, k);",
" p->lch = y;",
" p->push_up();",
" return {x, p};",
" }",
" else",
" {",
" Node *y = p->rch;",
" p->rch = nullptr;",
" p->push_up();",
" return {p, y};",
" }",
" }",
"",
" Node *merge(Node *x, Node *y) const",
" {",
" if (x == nullptr)",
" return y;",
" if (y == nullptr)",
" return x;",
" if (x->pri < y->pri)",
" {",
" x->rch = merge(x->rch, y);",
" x->push_up();",
" return x;",
" }",
" else",
" {",
" y->lch = merge(x, y->lch);",
" y->push_up();",
" return y;",
" }",
" }",
"};"
],
"description": "TreapSet"
},
"Treap文艺平衡树": {
"prefix": "tptreap",
"body": [
"class Treap",
"{",
"public:",
" Treap(int n)",
" {",
" stack<Node *> st;",
" for (int i = 1; i <= n; i++)",
" {",
" Node *x = new Node(i);",
" while (!st.empty() && st.top()->pri >= x->pri)",
" {",
" st.top()->push_up();",
" st.pop();",
" }",
" if (st.empty())",
" {",
" x->lch = root;",
" root = x;",
" }",
" else",
" {",
" Node *y = st.top();",
" x->lch = y->rch;",
" y->rch = x;",
" }",
" st.push(x);",
" }",
" while (!st.empty())",
" {",
" st.top()->push_up();",
" st.pop();",
" }",
" }",
"",
" void reverse(int l, int r)",
" {",
" auto [temp, z] = split_by_rank(root, r);",
" auto [x, y] = split_by_rank(temp, l - 1);",
" flip(y);",
" root = merge(merge(x, y), z);",
" }",
"",
" void debug()",
" {",
" auto print = [](auto &self, Node *p) -> void",
" {",
" if (p == nullptr)",
" return;",
" p->push_down();",
" self(self, p->lch);",
" cout << p->val << ' ';",
" self(self, p->rch);",
" };",
" print(print, root);",
" cout << endl;",
" }",
"",
"private:",
" struct Node",
" {",
" int val, pri;",
" int size = 1;",
" bool flag = false;",
" Node *lch = nullptr;",
" Node *rch = nullptr;",
"",
" Node(int v) : val(v), pri(gen_priority()) {}",
"",
" static int gen_priority()",
" {",
" static mt19937 gen(random_device{}());",
" static uniform_int_distribution<> dis;",
" return dis(gen);",
" }",
"",
" void push_up() { size = 1 + get_size(lch) + get_size(rch); }",
"",
" void push_down()",
" {",
" if (flag)",
" {",
" flip(lch);",
" flip(rch);",
" flag = false;",
" }",
" }",
"",
" void reverse()",
" {",
" swap(lch, rch);",
" flag ^= true;",
" }",
" };",
"",
" static int get_size(Node *p) { return p == nullptr ? 0 : p->size; }",
"",
" static void flip(Node *p)",
" {",
" if (p != nullptr)",
" {",
" p->flag ^= 1;",
" swap(p->lch, p->rch);",
" }",
" }",
"",
" mutable Node *root = nullptr;",
"",
" // 返回的左子树有 k 个元素",
" pair<Node *, Node *> split_by_rank(Node *p, int k) const",
" {",
" if (p == nullptr)",
" return {nullptr, nullptr};",
" p->push_down();",
" int lch_size = get_size(p->lch);",
" if (lch_size + 1 == k)",
" {",
" Node *y = p->rch;",
" p->rch = nullptr;",
" p->push_up();",
" return {p, y};",
" }",
" else if (lch_size + 1 < k)",
" {",
" auto [x, y] = split_by_rank(p->rch, k - lch_size - 1);",
" p->rch = x;",
" p->push_up();",
" return {p, y};",
" }",
" else",
" {",
" auto [x, y] = split_by_rank(p->lch, k);",
" p->lch = y;",
" p->push_up();",
" return {x, p};",
" }",
" }",
"",
" Node *merge(Node *x, Node *y) const",
" {",
" if (x == nullptr)",
" return y;",
" if (y == nullptr)",
" return x;",
" if (x->pri < y->pri)",
" {",
" x->push_down();",
" x->rch = merge(x->rch, y);",
" x->push_up();",
" return x;",
" }",
" else",
" {",
" y->push_down();",
" y->lch = merge(x, y->lch);",
" y->push_up();",
" return y;",
" }",
" }",
"};"
],
"description": "Treap文艺平衡树"
},
"Trie树": {
"prefix": "tptrie",
"body": [
"struct Trie",
"{",
" struct Node",
" {",
" unordered_map<char, Node *> ne;",
" bool end;",
"",
" Node *at_or_new(char ch)",
" {",
" auto it = ne.find(ch);",
" if (it == ne.end())",
" it = ne.insert({ch, new Node()}).first;",
" return it->second;",
" }",
"",
" Node *at(char ch) const",
" {",
" auto it = ne.find(ch);",
" return it == ne.end() ? nullptr : it->second;",
" }",
" };",
"",
" Node *root = new Node();",
"",
" void insert(const string &s)",
" {",
" Node *p = root;",
" for(auto ch : s)",
" p = p->at_or_new(ch);",
" p->end = true;",
" }",
"",
" string search(const string &s)",
" {",
" Node *p = root;",
" for(auto ch : s)",
" {",
" p = p->at(ch);",
"",
" }",
" }",
"};"
],
"description": "Trie树"
},
"AC自动机": {
"prefix": "tpac",
"body": [
"struct AC",
"{",
" struct Node",
" {",
" unordered_map<char, Node *> ne;",
" vector<Node *> edge;",
" Node *fail;",
" vector<int *> pattern_ans;",
" int cnt = 0;",
"",
" Node *at_or_new(char ch)",
" {",
" auto it = ne.find(ch);",
" if (it == ne.end())",
" it = ne.insert({ch, new Node()}).first;",
" return it->second;",
" }",
"",
" Node *at(char ch)",
" {",
" auto it = ne.find(ch);",
" if (it == ne.end())",
" it = ne.insert({ch, fail->at(ch)}).first;",
" return it->second;",
" }",
" };",
"",
" Node *root = new Node();",
"",
" void insert(int *ans_ptr, const string &s)",
" {",
" Node *p = root;",
" for (auto ch : s)",
" p = p->at_or_new(ch);",
" p->pattern_ans.push_back(ans_ptr);",
" }",
"",
" void search(const string &s)",
" {",
" Node *now = root;",
" for (auto ch : s)",
" {",
" now = now->at(ch);",
" now->cnt++;",
" }",
"",
" auto dfs = [&](auto &self, Node *u) -> int",
" {",
" for (auto v : u->edge)",
" u->cnt += self(self, v);",
" for (auto p : u->pattern_ans)",
" *p += u->cnt;",
" return u->cnt;",
" };",
"",
" dfs(dfs, root);",
" }",
"",
" void build()",
" {",
" queue<Node *> q;",
" for (char ch = 'a'; ch <= 'z'; ch++)",
" {",
" auto it = root->ne.find(ch);",
" if (it != root->ne.end())",
" {",
" q.push(it->second);",
" it->second->fail = root;",
" root->edge.push_back(it->second);",
" }",
" else",
" root->ne[ch] = root;",
" }",
" while (!q.empty())",
" {",
" Node *u = q.front();",
" q.pop();",
" Node *f = u->fail;",
" for (auto [ch, v] : u->ne)",
" {",
" Node *f_ch = f->at(ch);",
" v->fail = f_ch;",
" f_ch->edge.push_back(v);",
" q.push(v);",
" }",
" }",
" }",
"};"
],
"description": "AC自动机"
},
"无权图": {
"prefix": "tpgraph",
"body": [
"struct Graph",
"{",
" int n;",
" vector<vector<int>> edge;",
"",
" Graph(int n) : n(n), edge(n) {}",
"",
" void add(int u, int v) { edge[u].push_back(v); }",
"};"
],
"description": "无权图"
},
"有权图": {
"prefix": "tpgraph",
"body": [
"struct Graph",
"{",
" struct Edge",
" {",
" int to, cost;",
" };",
"",
" int n;",
" vector<vector<Edge>> edge;",
"",
" Graph(int n) : n(n), edge(n) {}",
"",
" void add(int u, int v, int w) { edge[u].push_back({v, w}); }",
"};"
],
"description": "有权图"
},
"Dijkstra最短路": {
"prefix": "tpdijkstra",
"body": [
"template <typename T>",
"struct Graph",
"{",
" struct Edge",
" {",
" int to, cost;",
" };",
"",
" int n;",
" vector<vector<Edge>> edge;",
"",
" Graph(int n) : n(n), edge(n) {}",
"",
" void add_edge(int u, int v, int w) { edge[u].push_back({v, w}); }",
"",
" vector<T> dijkstra(int s) const",
" {",
" struct Node",
" {",
" int u;",
" T d;",
" bool operator>(const Node &other) const { return d > other.d; }",
" };",
"",
" vector<T> dis(n, numeric_limits<T>::max());",
" dis[s] = 0;",
" priority_queue<Node, vector<Node>, greater<Node>> heap;",
" heap.push({s, 0});",
" while (!heap.empty())",
" {",
" auto [u, d] = heap.top();",
" heap.pop();",
" if (d > dis[u])",
" continue;",
" for (auto [v, w] : edge[u])",
" {",
" if (d + w < dis[v])",
" {",
" dis[v] = d + w;",
" heap.push({v, dis[v]});",
" }",
" }",
" }",
" return dis;",
" }",
"};"
],
"description": "Dijkstra最短路"
},
"网络最大流": {
"prefix": "tpdinic",
"body": [
"struct Network",
"{",
" struct Edge",
" {",
" int to, flow, rev_idx;",
" };",
"",
" int n;",
" vector<vector<Edge>> edge;",
"",
" Network(int n) : n(n), edge(n) {}",
"",
" void add_edge(int u, int v, int w)",
" {",
" int ui = edge[u].size();",
" int vi = edge[v].size();",
" edge[u].push_back({v, w, vi});",
" edge[v].push_back({u, 0, ui});",
" }",
"",
" int dinic(int s, int t)",
" {",
" vector<int> dep(n);",
" vector<size_t> cur(n);",
"",
" auto bfs = [&]() -> bool",
" {",
" dep.assign(n, -1);",
" cur.assign(n, 0);",
" dep[s] = 0;",
" queue<int> q;",
" q.push(s);",
" while (!q.empty())",
" {",
" int u = q.front();",
" q.pop();",
" int d = dep[u];",
" for (auto e : edge[u])",
" {",
" int v = e.to;",
" if (e.flow && dep[v] == -1)",
" {",
" dep[v] = d + 1;",
" q.push(v);",
" }",
" }",
" }",
" return dep[t] != -1;",
" };",
"",
" auto dfs = [&](auto &self, int u, int in) -> int",
" {",
" if (u == t)",
" return in;",
" int out = 0;",
" for (size_t &i = cur[u]; i < edge[u].size(); i++)",
" {",
" Edge &e = edge[u][i];",
" int v = e.to;",
" if (dep[v] == dep[u] + 1 && e.flow)",
" {",
" Edge &r = edge[v][e.rev_idx];",
" int res = self(self, v, min(in, e.flow));",
" e.flow -= res;",
" r.flow += res;",
" in -= res;",
" out += res;",
" if (!in)",
" break;",
" }",
" }",
" return out;",
" };",
"",
" int ans = 0;",
" while (bfs())",
" ans += dfs(dfs, s, numeric_limits<int>::max());",
" return ans;",
" }",
"};"
],
"description": "网络最大流"
},
"最小费用流": {
"prefix": "tpmcmf",
"body": [
"template <typename Cost = int>",
"class Network",
"{",
"public:",
" Network(int n) : n(n), edge(n), h(n, MAX_COST) {}",
"",
" void add_edge(int u, int v, int f, Cost c)",
" {",
" int ui = edge[u].size();",
" int vi = edge[v].size();",
" edge[u].push_back({v, f, c, vi});",
" edge[v].push_back({u, 0, -c, ui});",
" }",
"",
" // spfa",
" void init(int s)",
" {",
" h[s] = 0;",
" queue<int> q;",
" q.push(s);",
" while (!q.empty())",
" {",
" int u = q.front();",
" q.pop();",
" Cost d = h[u];",
" for (auto e : edge[u])",
" {",
" int v = e.to;",
" if (e.flow && d + e.cost < h[v])",
" {",
" h[v] = d + e.cost;",
" q.push(v);",
" }",
" }",
" }",
" }",
"",
" pair<Cost, int> slope(int s, int t)",
" {",
" vector<Cost> dis(n, MAX_COST);",
" vector<Edge *> from(n);",
"",
" auto dijkstra = [&]() -> bool",
" {",
" struct Node",
" {",
" int u;",
" Cost d;",
" bool operator>(const Node &other) const { return d > other.d; }",
" };",
"",
" dis.assign(n, MAX_COST);",
" dis[s] = 0;",
" priority_queue<Node, vector<Node>, greater<Node>> heap;",
" heap.push({s, 0});",
" while (!heap.empty())",
" {",
" auto [u, d] = heap.top();",
" heap.pop();",
" if (d > dis[u])",
" continue;",
" for (auto &e : edge[u])",
" {",
" int v = e.to;",
" Cost c = e.cost + h[u] - h[v];",
" if (e.flow && d + c < dis[v])",
" {",
" dis[v] = d + c;",
" heap.push({v, dis[v]});",
" from[v] = &e;",
" }",
" }",
" }",
" return dis[t] != MAX_COST;",
" };",
"",
" if (!dijkstra())",
" return {0, 0};",
"",
" Cost mincost = 0;",
" int maxflow = 0;",
" for (int u = 0; u < n; u++)",
" h[u] += dis[u];",
" int flow = numeric_limits<int>::max();",
" for (Edge *p = from[t]; p;)",
" {",
" flow = min(flow, p->flow);",
" int v = p->to, rev_idx = p->rev_idx;",
" Edge *r = &edge[v][rev_idx];",
" p = from[r->to];",
" }",
" for (Edge *p = from[t]; p;)",
" {",
" int v = p->to, rev_idx = p->rev_idx;",
" Edge *r = &edge[v][rev_idx];",
" p->flow -= flow;",
" r->flow += flow;",
" p = from[r->to];",
" }",
" mincost += h[t] * flow;",
" maxflow += flow;",
" return {mincost, maxflow};",
" }",
"",
" pair<Cost, int> mcmf(int s, int t)",
" {",
" init(s);",
" Cost mincost = 0;",
" int maxflow = 0;",
" while (true)",
" {",
" auto [cost, flow] = slope(s, t);",
" if (flow == 0)",
" break;",
" mincost += cost;",
" maxflow += flow;",
" }",
" return {mincost, maxflow};",
" }",
"",
"private:",
" const Cost MAX_COST = numeric_limits<Cost>::max();",
"",
" struct Edge",
" {",
" int to, flow;",
" Cost cost;",
" int rev_idx;",
" };",
"",
" int n;",
" vector<vector<Edge>> edge;",
" vector<Cost> h;",
"};"
],
"description": "最小费用流"
},
"莫队查询排序": {
"prefix": "tpmo",
"body": [
"struct Query",
"{",
" int l, r, b, id;",
" bool operator<(const Query &other) const { return b != other.b ? b < other.b : (r == other.r ? false : ((b & 1) ^ (r < other.r))); }",
"};"
],
"description": "莫队查询排序"
},
"布尔矩阵": {
"prefix": "tpmatrix",
"body": [
"const int N = $0;",
"using RowVec = bitset<N>;",
"",
"class Matrix",
"{",
"public:",
" RowVec &operator[](int i) { return a[i]; }",
" const RowVec &operator[](int i) const { return a[i]; }",
"",
" Matrix operator*(const Matrix &y) const;",
"",
"private:",
" array<RowVec, N> a;",
"};",
"",
"RowVec operator*(const RowVec &v, const Matrix &m)",
"{",
" RowVec res;",
" for (int j = 0; j < N; j++)",
" if (v[j])",
" res |= m[j];",
" return res;",
"}",
"",
"Matrix Matrix::operator*(const Matrix &y) const",
"{",
" Matrix res;",
" for (int i = 0; i < N; i++)",
" res[i] = a[i] * y;",
" return res;",
"}",
"",
"Matrix qpow(Matrix a, LL b)",
"{",
" Matrix res;",
" for (int i = 0; i < N; i++)",
" res[i][i] = 1;",
" while (b)",
" {",
" if (b & 1)",
" res = res * a;",
" b >>= 1;",
" a = a * a;",
" }",
" return res;",
"}"
],
"description": "布尔矩阵"
},
"manacher算法": {
"prefix": "tpmanacher",
"body": [
"int manacher(const string &s, char ch)",
"{",
" int n = s.size();",
" int m = 2 * n + 1;",
" string t(m, ch);",
" for (int i = 0, j = 1; i < n; i++, j += 2)",
" t[j] = s[i];",
" vector<int> d(m);",
" int ans = 0;",
" for(int i = 0, l = 0, r = -1; i < m; i++)",
" {",
" int k = i > r ? 1 : min(d[l+r-i], r-i+1);",
" while(i-k >= 0 && i + k < m && t[i-k] == t[i+k])",
" k++;",
" d[i] = k;",
" ans = max(ans, 2 * k - 1);",
" if(i + k - 1 > r)",
" {",
" r = i + k - 1;",
" l = i - k + 1;",
" }",
" }",
" return ans / 2;",
"}"
],
"description": "manacher算法"
},
}
最后更新:
2025-05-26
创建日期: 2024-12-30
创建日期: 2024-12-30