分治
分治专题 分治初步 归并排序求逆序对 Sol：在归并排序过程中，本身就是分治思想，递归的对左区间排序，右区间同理。对于已经有序两段进行合并只需要O(n)O(n)O(n)的时间，递归共log2nlog_{2}{n}log2n层，时间复杂度为O(nlog2n)O(nlog_{2}{n})O(nlog2n) debug:1.对于没有到达边界的一段也需要放入临时数组，并且继续统计答案 2，先审核一遍代码，出现了没有调用函数，只打个括号的情况，没有报错，需要注意 1234567891011121314151617181920212223242526272829int solve(int l,int r){ if(l==r)return 0; int mid=(l+r)>>1; int res=solve(l,mid)+solve(mid+1,r); int pl=l,pr=mid+1; int...
Codeforces Round 790 (Div. 4)
Codeforces Round 790 (Div. 4) D:题意：给定一个国际象棋棋盘，每个点都有权值，求在哪放置象，能使得象能攻击到的位置和最大。 Solution：由于数据范围很小，我们考虑最简单的暴力实现。对于每一个点，我们向四个攻击方向去走直到到达边界，定义方向数组即可。 123456789101112131415161718192021222324252627int dx[5]={1,1,-1,-1};int dy[5]={-1,1,1,-1};void solve(){ cin>>n>>m; vector<vector<int>>v(n,vector<int>(m)); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>v[i][j]; } } int ans=0; for(int...
CSP认证模板
CSP认证模板 切换中英文键修改，语法风格vs，主题vs，输入内容才能保存生效，关闭保存自动格式化，改格式化快捷键shift+alt+f 编译选项 1-Wall -Wextra -DLOCAL -std=c++17 -g -O2 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758#include <bits/stdc++.h>using i128 = __int128;using namespace std;#ifdef LOCAL#define deb(x) cerr<<"L"<<__LINE__<<": "<<#x<<" = "<<(x)<<endl#else#define deb(x)#endif#define ll long long//#define...
从启发式合并到Dsu on Tree
从启发式合并到Dsu on Tree 传统启发式合并 [HNOI2009] 梦幻布丁 题目描述 nnn 个布丁摆成一行，进行 mmm 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。 例如，颜色分别为 1,2,2,11,2,2,11,2,2,1 的四个布丁一共有 333 段颜色. 输入格式 第一行是两个整数，分别表示布丁个数 nnn 和操作次数 mmm。 第二行有 nnn 个整数，第 iii 个整数表示第 iii 个布丁的颜色 aia_iai。 接下来 mmm 行，每行描述一次操作。每行首先有一个整数 opopop 表示操作类型： 若 op=1op = 1op=1，则后有两个整数 x,yx, yx,y，表示将颜色 xxx 的布丁全部变成颜色 yyy。 若 op=2op = 2op=2，则表示一次询问。 ...
字典树专题
01 trie 找序列中任意两数的最大异或和 123456789101112131415161718192021222324252627282930313233343536int n, m;int a[N];int idx=0;int ch[N*31][2];void insert(int x){ int p=0; for(int i=30;i>=0;i--){ int u=(x>>i)&1; if(!ch[p][u])ch[p][u]=++idx; p=ch[p][u]; }}int query(int x){ int p=0;int ans=0; for(int i=30;i>=0;i--){ int u=(x>>i)&1; if(ch[p][!u]){ p=ch[p][!u]; ans+=1<<i; } else p=ch[p][u]; } return ans;}void...
关于2024省赛的总结和我的当下问题和训练
关于本次省赛的总结和我的当下问题和未来训练侧重 ...
后缀数组SA
后缀数组SA 简述：花费O(nlogn)用倍增+基数排序花费O(nlogn)用倍增+基数排序花费O(nlogn)用倍增+基数排序构建H数组完成对后缀排序。 思想在于calabashboy，实现细节和方法看dxsf。 注意细节：传入字符串0base，内部会修改成1base，传的是引用。值域都在1-n之间 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182struct SA { int n; // 存储字符串的长度 vector<int> sa, rk, lc; // sa: 后缀数组, rk: 排名数组, lc: 最长公共前缀数组 (LCP) SparseTable<int> qmn; SA(string& s)...
报告
编译命令 1234bison -d parser.y -o parser.tab.c> flex -o lexer.c lexer.lgcc -o parser lexer.c parser.tab.c ast.c main.c dot –Tpdf ast2.dot –o graph2.pdf
Border树
Border树 对于一个字符串S，n = |S|，它的Border 树（也叫next 树）共有n+1 个节点：0, 1, 2, . . . , n。 0 是这棵有向树的根。对于其他每个点1 ≤ i ≤ n，父节点为next[i]。 123456789101112131415161718192021222324252627struct KMP { vector<int> nxt; string tt; int len; KMP() {} KMP(string t) { len = t.size(); t = " " + t; tt = t; nxt.resize(len + 1); nxt[1] = nxt[0] = 0; init(tt); } void init(string t) { for (int i = 2; i <= len;...
输入输出处理(1)
1.io优化 1234const char endl = '\n'; //另外，请使用'\n'而不是 endl ，因为endl默认会增加刷新操作，而导致输出缓冲失效，降低效率。cin.tie(0);ios::sync_with_stdio(false); cin.tie(0) 和 ios::sync_with_stdio(false) 是 C++ 中用于优化输入输出的语句。 cin.tie(0) 的作用是取消 cin 与 cout 的绑定，默认情况下，当使用 cin 进行输入操作时，会先执行 cout 的缓冲输出。使用 cin.tie(0) 可以将 cin 和 cout 解绑，让它们可以独立地进行操作，从而提高输入输出的效率。 ios::sync_with_stdio(false) 则是取消 C++ 标准库输入输出流和 C 标准库输入输出流之间的同步。 默认情况下，C++ 标准库的输入输出流与 C 标准库的输入输出流是同步的，这就意味着在混合使用 C++ 的 cin/cout 和 C 的 scanf/printf...