分治
title: 分治categories: - ICPCtags: - nullabbrlink: 99c0330adate: 2023-08-04 00:00:00分治专题分治初步归并排序求逆序对Sol：在归并排序过程中，本身就是分治思想，递归的对左区间排序，右区间同理。对于已经有序两段进行合并只需要$O(n)$的时间，递归共$log_{2}{n}$层，时间复杂度为$O(nlog_{2}{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...
Codeforces Round 790 (Div. 4)
title: Codeforces Round 790 (Div. 4)categories: - ICPCtags: - nullabbrlink: 83b41c34date: 2023-07-27 00:00:00Codeforces 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...
CSP认证模板
title: CSP认证模板categories: - ICPCtags: - nullabbrlink: 88b51642date: 2023-07-21 00:00:00CSP认证模板 切换中英文键修改，语法风格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...
从启发式合并到Dsu on Tree
title: 从启发式合并到Dsu on Treecategories: - ICPCtags: - nullabbrlink: 2926421ddate: 2023-07-19 00:00:00从启发式合并到Dsu on Tree传统启发式合并[HNOI2009] 梦幻布丁题目描述$n$ 个布丁摆成一行，进行 $m$ 次操作。每次将某个颜色的布丁全部变成另一种颜色的，然后再询问当前一共有多少段颜色。 例如，颜色分别为 $1,2,2,1$ 的四个布丁一共有 $3$ 段颜色. 输入格式第一行是两个整数，分别表示布丁个数 $n$ 和操作次数 $m$。第二行有 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个布丁的颜色 $a_i$。接下来 $m$ 行，每行描述一次操作。每行首先有一个整数 $op$ 表示操作类型： 若 $op = 1$，则后有两个整数 $x, y$，表示将颜色 $x$ 的布丁全部变成颜色 $y$。 若 $op =...
字典树专题
title: 字典树专题categories: - ICPCtags: - nullabbrlink: 5f205474date: 2023-07-15 00:00:0001 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...
关于2024省赛的总结和我的当下问题和训练
title: 关于2024省赛的总结和我的当下问题和训练categories: - ICPCtags: - nullabbrlink: d75bced8date: 2023-07-03...
后缀数组SA
title: 后缀数组SAcategories: - ICPCtags: - nullabbrlink: ffcfed1fdate: 2023-06-28 00:00:00后缀数组SA简述：$花费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(); // 初始化字符串的长度 sa.resize(n + 1); // 调整 sa 的大小为 n + 1 ...
报告
title: 报告categories: - ICPCtags: - nullabbrlink: 3a22db16date: 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
Border树
title: Border树categories: - ICPCtags: - nullabbrlink: e3b02275date: 2023-06-17 00:00:00Border树对于一个字符串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); } void...
输入输出处理(1)
title: 输入输出处理(1)categories: - ICPCtags: - nullabbrlink: 5913264adate: 2023-06-05 00:00:001.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...