爱飞鱼的blog

title: 分治 categories: ICPC tags: null abbrlink: 99c0330a date: 2023-08-04 00:00:00 分治专题 分治初步 归并排序求逆序对 Sol：在归并排序过程中，本身就是分治思想，递归的对左区间排序，右区间同理。对于已经有序两段进行合并只需要O(n)O(n)O(n)的时间，递归共log2nlog_{2}{n}log2​n层，时间复杂度为O(nlog2n)O(nlog_{2}{n})O(nlog2​n) debug:1.对于没有到达边界的一段也需要放入临时数组，并且继续统计答案 2，先审核一遍代码，出现了没有调用函数，只打个括号的情况，没有报错，需要注意 int 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...

title: Codeforces Round 790 (Div. 4) categories: ICPC tags: null abbrlink: 83b41c34 date: 2023-07-27 00:00:00 Codeforces Round 790 (Div. 4) D:题意：给定一个国际象棋棋盘，每个点都有权值，求在哪放置象，能使得象能攻击到的位置和最大。 Solution：由于数据范围很小，我们考虑最简单的暴力实现。对于每一个点，我们向四个攻击方向去走直到到达边界，定义方向数组即可。 int 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...

title: CSP认证模板 categories: ICPC tags: null abbrlink: 88b51642 date: 2023-07-21 00:00:00 CSP认证模板 切换中英文键修改，语法风格vs，主题vs，输入内容才能保存生效，关闭保存自动格式化，改格式化快捷键shift+alt+f 编译选项 -Wall -Wextra -DLOCAL -std=c++17 -g -O2 #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 int...

title: 从启发式合并到Dsu on Tree categories: ICPC tags: null abbrlink: 2926421d date: 2023-07-19 00:00:00 从启发式合并到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，则表示一次询问。 ...

title: 字典树专题 categories: ICPC tags: null abbrlink: 5f205474 date: 2023-07-15 00:00:00 01 trie 找序列中任意两数的最大异或和 int 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...

title: 关于2024省赛的总结和我的当下问题和训练 categories: ICPC tags: null abbrlink: d75bced8 date: 2023-07-03 00:00:00 关于本次省赛的总结和我的当下问题和未来训练侧重 ...

title: 后缀数组SA categories: ICPC tags: null abbrlink: ffcfed1f date: 2023-06-28 00:00:00 后缀数组SA 简述：花费O(nlogn)用倍增+基数排序花费O(nlogn)用倍增+基数排序花费O(nlogn)用倍增+基数排序构建H数组完成对后缀排序。 思想在于calabashboy，实现细节和方法看dxsf。 注意细节：传入字符串0base，内部会修改成1base，传的是引用。值域都在1-n之间 struct SA { int n; // 存储字符串的长度 vector<int> sa, rk, lc; // sa: 后缀数组, rk: 排名数组, lc: 最长公共前缀数组 (LCP) SparseTable<int> qmn; SA(string& s) { n = s.length(); // 初始化字符串的长度 ...

title: 报告 categories: ICPC tags: null abbrlink: 3a22db16 date: 2023-06-20 00:00:00 编译命令 bison -d parser.y -o parser.tab.c > flex -o lexer.c lexer.l gcc -o parser lexer.c parser.tab.c ast.c main.c dot –Tpdf ast2.dot –o graph2.pdf

title: Border树 categories: ICPC tags: null abbrlink: e3b02275 date: 2023-06-17 00:00:00 Border树 对于一个字符串S，n = |S|，它的Border 树（也叫next 树）共有n+1 个节点：0, 1, 2, . . . , n。 0 是这棵有向树的根。对于其他每个点1 ≤ i ≤ n，父节点为next[i]。 struct 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); } ...

title: 输入输出处理(1) categories: ICPC tags: null abbrlink: 5913264a date: 2023-06-05 00:00:00 1.io优化 const 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++...