爱飞鱼的blog

title: 二分图最大权完美匹配 categories: ICPC tags: null abbrlink: c4b70c65 date: 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; ...

title: 01trie专题 categories: ICPC tags: null abbrlink: 778408ed date: 2023-04-08 00:00:00 01trie特训2 题意：给定一个含有 n 个元素的数组 Ai，你可以选择两个不相交的子段。求出这两个子段内的数的异或和的差值的最大值。 Sol：考虑枚举两段的分界点，对于较短的两段来说可能会有多个分界点但这样我们求的是答案的超集，一定会包括答案的。对于一个分界点，我们先考虑如果要求以左边区间必须包含分界点，那么我们只需要异或前缀和后找一个位置和它异或最大或最小，这是经典的01trie的应用。再考虑右边，我们需要做后缀异或和，做跑一遍trie。注意实际上可以不以分界点为选取的子段的端点，我们需要需要维护异或后结果的前缀最大值，后缀最小值，剩下同理。 debug：我自己实现不好写的原因是没开第二个后缀异或和，在那一直用前缀和偏移位置，边界不好处理。 //trie树 + 前缀异或和 + 枚举 #include<bits/stdc++.h> #define endl...

title: 树分治 点分治 categories: ICPC tags: null abbrlink: fdbd89dd date: 2023-04-08 00:00:00 给定一棵有 nnn 个点的树，询问树上距离为 kkk 的点对是否存在。 第一行两个数 n,mn,mn,m,n个点。 第 222 到第 nnn 行，每行三个整数 u,v,wu, v, wu,v,w，代表树上存在一条连接 uuu 和 vvv 边权为 www 的路径。 接下来 mmm 行，每行一个整数 kkk，代表一次询问。 对于每次询问输出一行一个字符串代表答案，存在输出 AYE，否则输出 NAY。 对于 100%100\%100% 的数据，保证 1≤n≤1041 \leq n\leq 10^41≤n≤104，1≤m≤1001 \leq m\leq 1001≤m≤100，1≤k≤1071 \leq k \leq 10^71≤k≤107，1≤u,v≤n1 \leq u, v \leq n1≤u,v≤n，1≤w≤1041 \leq w \leq...

title: stl的妙用 categories: ICPC tags: null abbrlink: 294436d6 date: 2023-04-03 00:00:00 stl的妙用 关于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 =...

title: 离线+并查集 categories: ICPC tags: null abbrlink: e2382ff9 date: 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++)...

title: 可持久化线段树（主席树） categories: ICPC tags: null abbrlink: d1a237fb date: 2023-04-02 00:00:00 给定 n 个整数构成的序列 a，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值。 题目一开始的离散化复杂度为O(nlog⁡n)O(n\log n)O(nlogn)，构建基础主席树复杂度为O(nlog⁡n)O(n\log n)O(nlogn)，统计并插入的复杂度是O(nlog⁡n+nlog⁡n)=O(nlog⁡n)O(n\log n + n\log n)=O(n\log n)O(nlogn+nlogn)=O(nlogn)，询问的复杂度是O(mlog⁡n)O(m\log n)O(mlogn)。复杂度总和就是O((m+n)log⁡n)O((m+n)\log n)O((m+n)logn)。 #define N 200005 #define lc(x) tr[x].l #define rc(x) tr[x].r struct node{ int l,r,s;...

title: starrycoding周赛 categories: ICPC tags: null abbrlink: 1828b237 date: 2023-04-01 00:00:00 E题：题意：给定一个数组，你有两个操作，第一个操作是对任意前缀减去一个数，第二个操作是对任意后缀减去一个数。现在希望你用这两个操作将这两个数都变成0，要求操作次数最少，无解情况需要判断。 ...

title: 经典数据结构问题 categories: ICPC tags: null abbrlink: cecfa4d9 date: 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,...

title: 最短路Floyd categories: ICPC tags: null abbrlink: efc5e5e7 date: 2023-03-21 00:00:00 void 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: ICPC tags: null abbrlink: 3cbbbc13 date: 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...