二分图最大权完美匹配
title: 二分图最大权完美匹配categories: - ICPCtags: - nullabbrlink: c4b70c65date: 2023-04-09 00:00:00#时间复杂度为Θ(n^3) const int inf =0x3f3f3f3f; const int N=505; long long w[N][N]; long long la[N],lb[N]; bool va[N],vb[N]; long long match[N]; long long n,m,upd[N]; long long last[N]; bool dfs(int x,int fa) { va[x]=1; for(int y = 1; y<=n; y++) { if(!vb[y]) { if(la[x]+lb[y]-w[x][y]==0) { vb[y]=1; ...
01trie专题
title: 01trie专题categories: - ICPCtags: - nullabbrlink: 778408eddate: 2023-04-08 00:00:0001trie特训2题意：给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。Sol：考虑枚举两段的分界点，对于较短的两段来说可能会有多个分界点但这样我们求的是答案的超集，一定会包括答案的。对于一个分界点，我们先考虑如果要求以左边区间必须包含分界点，那么我们只需要异或前缀和后找一个位置和它异或最大或最小，这是经典的01trie的应用。再考虑右边，我们需要做后缀异或和，做跑一遍trie。注意实际上可以不以分界点为选取的子段的端点，我们需要需要维护异或后结果的前缀最大值，后缀最小值，剩下同理。debug：我自己实现不好写的原因是没开第二个后缀异或和，在那一直用前缀和偏移位置，边界不好处理。//trie树 + 前缀异或和 + 枚举 #include<bits/stdc++.h> #define endl...
树分治 点分治
title: 树分治 点分治categories: - ICPCtags: - nullabbrlink: fdbd89dddate: 2023-04-08 00:00:00给定一棵有 $n$ 个点的树，询问树上距离为 $k$ 的点对是否存在。第一行两个数 $n,m$,n个点。第 $2$ 到第 $n$ 行，每行三个整数 $u, v, w$，代表树上存在一条连接 $u$ 和 $v$ 边权为 $w$ 的路径。接下来 $m$ 行，每行一个整数 $k$，代表一次询问。对于每次询问输出一行一个字符串代表答案，存在输出 AYE，否则输出 NAY。 对于 $100%$ 的数据，保证 $1 \leq n\leq 10^4$，$1 \leq m\leq 100$，$1 \leq k \leq 10^7$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^4$。 #时间复杂度O（nmlogn) const int N=10005; const int INF=10000005; struct node{int...
stl的妙用
title: stl的妙用categories: - ICPCtags: - nullabbrlink: 294436d6date: 2023-04-03 00:00:00stl的妙用关于mutiset的应用的几个题G - Minimum Xor Pair Query题意：你可以进行以下操作 加入一个数 删除一个数 输出任意两个数异或最小值 思路：首先我们要知道一个性质(重要!)：两个数差值越小，异或值也越小。 那么我们要求异或最小值，那么答案一定在排序后相邻两个数中产生。 为了便于写，防止在set里面找不到的情况出现，我们手动插入下界和上界。 考虑我们的操作： 对于加入一个数，我们的答案有什么影响呢？ 假设我们插入的值是x。 假设我们的情况是：l x r 首先如果l和r都存在，那么显然此时l和r的异或值不可能成为答案，我们把它删去 然后在答案里面加入x^l和 x^r(前提是l，r存在) void add(ll x) { s.insert(x); multiset<ll>::iterator it1 = s.find(x),...
可持久化线段树（主席树）
title: 可持久化线段树（主席树）categories: - ICPCtags: - nullabbrlink: d1a237fbdate: 2023-04-02 00:00:00给定 n 个整数构成的序列 a，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值。 题目一开始的离散化复杂度为$O(n\log n)$，构建基础主席树复杂度为$O(n\log n)$，统计并插入的复杂度是$O(n\log n + n\log n)=O(n\log n)$，询问的复杂度是$O(m\log n)$。复杂度总和就是$O((m+n)\log n)$。 #define N 200005 #define lc(x) tr[x].l #define rc(x) tr[x].r struct node{ int l,r,s; //s:节点值域中有多少个数 }tr[N*20]; int root[N],idx; int n,m,a[N]; vector<int> b; void build(int &x,int l,int...
离线+并查集
title: 离线+并查集categories: - ICPCtags: - nullabbrlink: e2382ff9date: 2023-04-02 00:00:00离线+并查集LCA&DSU&MST - jzcrq - 博客园 (cnblogs.com) 多次询问两点间的瓶颈路，也就是u到v所有路径中边权的最小值最大。 Sol：考虑先将所有询问离线。考虑建立最大生成树的过程，设联通块s1和s2要被边权为w的边连通。对于存在点u在s1,v在s2的询问的答案就是w。为了保证时间复杂度我们考虑启发式合并，注意判断大小的时候只需要交换u和v本身。把询问的对应点和编号挂在点上，每次把size小的部分的点拿出来更新答案和询问。无法回答的插入新的根中。 void solve() { int n, m; cin >> n >> m; vector<array<int, 3>> edg(m + 1); for (int i = 1; i <= m; i++)...
starrycoding周赛
title: starrycoding周赛categories: - ICPCtags: - nullabbrlink: 1828b237date: 2023-04-01...
经典数据结构问题
title: 经典数据结构问题categories: - ICPCtags: - nullabbrlink: cecfa4d9date: 2023-03-31 00:00:00经典数据结构问题静态区间颜色数 void solve() { int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; int m; cin >> m; int mx = *max_element(alls(a)); vector<vector<pii>> q(n + 1); for (int i = 1; i <= m; i++) { int l, r; cin >> l >> r; q[r].push_back({l, i}); ...
最短路Floyd
title: 最短路Floydcategories: - ICPCtags: - nullabbrlink: efc5e5e7date: 2023-03-21 00:00:00void floyd() { for (int k = 1; k <= n; k ++ ) for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } init(){ for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= n; j ++ ) if (i == j) d[i][j] = 0; else d[i][j] = INF; } 存边方式： d[a][b] =...
笛卡尔树
title: 笛卡尔树categories: - ICPCtags: - nullabbrlink: 3cbbbc13date: 2023-03-18 00:00:00笛卡尔树struct DKR { int n; vector<int> l, r; int root; stack<int> st; DKR(int nn) : n(nn), l(nn + 1), r(nn + 1), root(0) {} // 默认为小根堆，维护最小值所在区间 // dkr.built(a,less<int>());大根堆 int built(const vector<int>& a, function<bool(int, int)> cmp = greater<int>()) { while (!st.empty()) st.pop(); // 清空栈 for (int...