给出中序和按层遍历，求该树的先序遍历，后序遍历，叶子结点。
title: 给出中序和按层遍历，求该树的先序遍历，后序遍历，叶子结点。 categories: ICPC tags: null abbrlink: d24e30de date: 2024-10-10 00:00:00 一切的核心是怎么利用中序和按层遍历构建二叉树？ 1.优化空间很大，可以提前预处理记录每个数对应的位置，还可以vis数组记录这个点是不是已经作为根了。 2.我们考虑到每次找到当前中序要处理区间，里面的数记为集合mid，我们从前到后看层序遍历中的哪个数最先出现在mid中。那么这个数就是当前中序处理区间的根，这个新根的左边是左子树，右边是右子树，我们可以递归处理。 3.对于叶子节点，就是当他作为根的时候，没有左右节点，也就无法进行进一步深搜，flag记一下就可以了。 #include<stdio.h> #include<vector> #include<map> #include<algorithm> #include <algorithm> #include...
二进制拆位
title: 二进制拆位 categories: ICPC tags: null abbrlink: 3bbf550e date: 2024-10-09 00:00:00 二进制拆位 题意：给定一个数组，求所有子区间的区间异或和的sum Sol：先做异或前缀和，原问题则变成求数组中任意两个数的异或，然后全部相加起来的结果。我们考虑每个元素每位的贡献，只需要统计前面（偏序计数）有多少个数的本位与自己不同。 //这个题目显然应该作为模板题，似乎没有找到直白的在原数组上作拆位前缀和 //本题先通过异或前缀和预处理，来将问题转化为两两之间的异或和， //如果不转化，就需要计算贡献次数 void solve(){ cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)a[i]^=a[i-1]; vector<int>c0(len+2,1),c1(len+2,0); int ans=0; for(int...
矩阵乘法
title: 矩阵乘法 categories: ICPC tags: null abbrlink: 4ad33c6a date: 2024-10-04 00:00:00 int n, m; int k; struct matrix{ int c[101][101]; matrix(){memset(c,0,sizeof c);} }; matrix operator*(matrix &a,matrix &b){ matrix t; for(int i=1;i<=n;i++){ for(int j=1;j<=k;j++){ for(int g=1;g<=m;g++){ t.c[i][j]+=a.c[i][g]*b.c[g][j]; } } } return t; } void...
Codeforces Round 960 (Div. 2)A E
title: Codeforces Round 960 (Div. 2)A E categories: ICPC tags: null abbrlink: 2095917c date: 2024-09-30 00:00:00 Codeforces Round 960 (Div. 2)A-E A题意：公平博弈。给定一个数组n个数，每个数只能用一次。给一个mxmxmx。每次轮到自己操作的时候就选一个数组里的数，满足a[i]>=mxa[i]>=mxa[i]>=mx,然后令mx=a[i]mx=a[i]mx=a[i].双方轮流做直到一方无法操作，则另一方取胜。 Sol:赛时1min猜了个错解，只看最大值，只看最大值的出现次数，回来发现wa了。如果最大值出现偶数次，但次大值出现奇数次，先手也能win。递归考虑这个过程我们发现只需要统计所有数出现次数的奇偶性。只要出现一个奇数先手就能win，策略是从最大的出现奇数次开的数开始拿。 void solve(){ cin>>n; ...
wqs二分
title: wqs二分 categories: ICPC tags: null abbrlink: e73487b5 date: 2024-09-28 00:00:00 https://zhuanlan.zhihu.com/p/340514421 https://blog.csdn.net/Emm_Titan/article/details/124035796 https://www.cnblogs.com/TianMeng-hyl/p/14972355.html https://www.cnblogs.com/Liang-sheng/p/15182786.html
双指针具有单调性
title: 双指针具有单调性 categories: ICPC tags: null abbrlink: 631fa1fb date: 2024-09-28 00:00:00 双指针的题目往往是看起来需要O（n),我们一般枚举一个指针，然后我们发现另一个指针不走回头路，不论是哪个方向，这样我们的时间复杂度就是O(n). 从例题来看: 给定一个字符串，我们希望找到最短长度区间能包含所有字母类型。 ###核心：对于左端点固定的时候，我们找到最小的r，然后我们考虑i右移动一位，这时候我们的j是一定不会回头的，因为不回头，都已经少了一个字母且当前假设已经不包含所有字母了，。 所以i和j都是单调移动的 https://codeforces.com/contest/701/problem/C // Problem: C. They Are Everywhere // Contest: Codeforces - Codeforces Round 364 (Div. 2) // URL:...
Atcoder Beginner Contest 373
title: Atcoder Beginner Contest 373 categories: ICPC tags: null abbrlink: 2c72ca3 date: 2024-09-27 00:00:00 完全背包改编，背包体积3000，3000个物品，物品价值系数viv_{i}vi,选cntcntcnt个物品iii会获得cnt×(vi−cnt)价值cnt \times(v_{i}-cnt)价值cnt×(vi−cnt)价值 ，最大化背包价值
牛客周赛 Round 11
title: 牛客周赛 Round 11 categories: ICPC tags: null abbrlink: a421f0b4 date: 2024-09-23 00:00:00 https://ac.nowcoder.com/acm/contest/64593 A题签到 B题值得说得是对非降序的理解：非降序表示数组中的前一个数要<=下一个数 C题也算dp，因为需要注意遍历顺序，计算的是所有子串的的权重，我们知道枚举所有子串需要O(n2)O(n^2)O(n2)的复杂度，按照本题数据范围显然不能O(n3)O(n^3)O(n3)，我们只能在枚举过程中去维护计算每个字串的权重。 本题的特点是一个str的起点一旦确定，它变换的最终形态也就确定。所以我们考虑枚举起点，再枚举终点，对于每个起点终点确定的子串我们考虑假设起点是0的话我们需要变换c0次，起点是1的话我们需要操作c1次，两者取最小值就是当前子串的权重。 ...
树上换根dp
title: 树上换根dp categories: ICPC tags: null abbrlink: b2414559 date: 2024-09-15 00:00:00 树上换根dp 换根dp: 换根dp往往需要处理去掉一个子树这样的问题，我们可以使用前后缀和的方法来优化复杂度 Problem - 543D -...
SPFA
title: SPFA categories: ICPC tags: null abbrlink: 33b8c865 date: 2024-09-04 00:00:00 SPFA 最短路:保证数据不存在负环的情况下，求1-n最短路 struct edge { int v, w; }; void solve() { int n, m; cin >> n >> m; vector<vector<edge>> e(n + 1); for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; e[u].push_back({v, w}); } vector<int> dis(n + 1, inf); auto spfa =...