门户网站建设关系到wordpress 网址 代码

门户网站建设关系到,wordpress 网址 代码,公司简介范本,黑龙江建设工程网在我之前的几篇博客中整理了树状数组、线段树相关的笔记#xff0c;我最近又刷了一些题#xff0c;觉得有几道挺好的#xff0c;可以巩固这些知识#xff0c;这几道题重在逆序对的学习#xff0c;比较经典#xff0c;所以我决定分享一下。 目录 例题一#xff1a;蓝桥…在我之前的几篇博客中整理了树状数组、线段树相关的笔记我最近又刷了一些题觉得有几道挺好的可以巩固这些知识这几道题重在逆序对的学习比较经典所以我决定分享一下。目录例题一蓝桥杯官网——逆序对的数量问题描述输入格式输出格式样例输入样例输出代码解析方法一树状数组离散化方法2线段树离散化方法三01trie例题二蓝桥杯官网——逆序对数题目描述代码详解方法一暴力解法方法二树状数组离散化例题三蓝桥杯官网——压制二元组的总价值问题描述输入格式输出格式样例输入样例输出说明注本文例题均来自蓝桥杯官网公开真题仅用于技术学习与算法讲解里面的代码均由本人做出来并附上解析我的详细解析在第三题大家可以先看第三题。例题一蓝桥杯官网——逆序对的数量问题描述给定长度为 n 的序列 a输出 a 中逆序对的数量。逆序对对于 1 ≤ i j ≤ n若 ai aj则 ai, aj 为一对逆序对。输入格式第一行输入一个正整数 n。(1 n ≤ 10^5)第二行输入 n 个正整数表示序列 a。(1 ≤ ai≤ 10^9, 1 ≤ i ≤ n)输出格式输出一个整数表示 a 中逆序对的数量。样例输入8 1 4 7 2 5 7 9 2样例输出8代码解析方法一树状数组离散化#include iostream #includevector #includealgorithm using namespace std; using lllong long; const int N1e59; //方法一树状数组 ll t[4*N],a[N]; vectorintX; int getidx(int x) { return lower_bound(X.begin(),X.end(),x)-X.begin()1; } void pushup(int o) { t[o]t[o1]t[o1|1]; } void update(int l,int r,int k,int s1,int eX.size(),int o1) { if(lser) { t[o]k; return; } int mid(se)1; if(midl)update(l,r,k,s,mid,o1); if(mid1r)update(l,r,k,mid1,e,o1|1); pushup(o); } ll query(int l,int r,int s1,int eX.size(),int o1) { ll res0; if(lser) { return t[o]; } int mid(se)1; if(midl) resquery(l,r,s,mid,o1); if(mid1r) resquery(l,r,mid1,e,o1|1); return res; } int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); ll ans0; int n;cinn; for(int i1;in;i) { cina[i]; X.push_back(a[i]); } //排序和去重 sort(X.begin(),X.end()); X.erase(unique(X.begin(),X.end()),X.end()); //更新 for(int i1;in;i) { update(getidx(a[i]),getidx(a[i]),1); ansquery(1,X.size())-query(1,getidx(a[i])); } coutans\n; return 0; }方法2线段树离散化#include iostream #includevector #includealgorithm using namespace std; using lllong long; const int N1e59; //方法一树状数组 ll t[4*N],a[N]; vectorintX; int getidx(int x) { return lower_bound(X.begin(),X.end(),x)-X.begin()1; } void pushup(int o) { t[o]t[o1]t[o1|1]; } void update(int l,int r,int k,int s1,int eX.size(),int o1) { if(lser) { t[o]k; return; } int mid(se)1; if(midl)update(l,r,k,s,mid,o1); if(mid1r)update(l,r,k,mid1,e,o1|1); pushup(o); } ll query(int l,int r,int s1,int eX.size(),int o1) { ll res0; if(lser) { return t[o]; } int mid(se)1; if(midl) resquery(l,r,s,mid,o1); if(mid1r) resquery(l,r,mid1,e,o1|1); return res; } int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); ll ans0; int n;cinn; for(int i1;in;i) { cina[i]; X.push_back(a[i]); } //排序和去重 sort(X.begin(),X.end()); X.erase(unique(X.begin(),X.end()),X.end()); //更新 for(int i1;in;i) { update(getidx(a[i]),getidx(a[i]),1); ansquery(1,X.size())-query(1,getidx(a[i])); } coutans\n; return 0; }方法三01trie#include iostream using namespace std; using lllong long; const int N32*1e59,M1e59; int e[N]; int son[N][2],tot1; int a[M]; //插入 void insert(int x) { int o1; e[o]; for(int i30;i0;i--) { int yxi1; if(!son[o][y])son[o][y]tot; oson[o][y]; e[o]; } } int query(int x) { int res 0, o 1; // res存储结果o表示当前节点从根节点1开始 for (int i 30; i 0; i--) // 从最高位第30位到最低位第0位遍历 { int y x i 1; if (y 0) res e[son[o][1]]; if (!son[o][y]) break; o son[o][y]; // 移动到下一位的节点 } return res; } int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n;cinn; for(int i1;in;i)cina[i]; ll ans0; for(int i1;in;i) { ans1ll*query(a[i]); insert(a[i]); } coutans\n; return 0; }例题二蓝桥杯官网——逆序对数这题和上一题几乎一模一样大家快速过即可题目描述本题为填空题只需要算出结果后在代码中使用输出语句将所填结果输出即可。在一个序列 a(a[1],a[2],…,a[n]) 中如果 (i,j) 满足 ij 且 a[i]a[j]则称为一个逆序对。例如(3,2,2,1) 中包含 6 个逆序对。请问(87,39,35,1,99,10,54,1,46,24,74,62,49,13,2,80,24,58,8,14,83,23,97,85,3,2,86,10,71,15) 中包含多少个逆序对代码详解方法一暴力解法本体数据量小可直接暴力#include iostream using namespace std; //方法1暴力解法 int main() { int count0; int arr[]{0,87,39,35,1,99,10,54,1,46,24,74,62,49,13,2,80,24,58,8,14,83,23,97,85,3,2,86,10,71,15}; int nsizeof(arr)/sizeof(arr[0])-1; for(int i1;in;i) { for(int ji1;jn;j) { if(arr[i]arr[j]) count; } } coutcount\n; return 0; }方法二树状数组离散化//方法2树状数组 //注意这里是我大E了不能直接对这个a数组进制树状数组操作要进行离散化处理 //核心原因你的数组 a 中元素的值远超树状数组的下标范围树状数组的 update/getprefix 是基于「值作为下标」操作的 //而当前代码的逻辑完全依赖 “值的范围 ≤ 树状数组大小”但是数据不满足这个条件 /*int t[N];//树状数组 int a[]{0,87,39,35,1,99,10,54,1,46,24,74,62,49,13,2,80,24,58,8,14,83,23,97,85,3,2,86,10,71,15}; int nsizeof(a)/sizeof(a[0])-1; int lowbit(int x){return x-x;} void update(int a,int k) { for(int ia;in;ilowbit(i)) t[i]k; } int getprefix(int k) { int res0; for(int ik;i1;i-lowbit(i)) rest[i]; return res; } int main() { int count0; for(int i1;in;i) { update(a[i],1); //计算每一步前面比a[i]大的数 count(i-1)-getprefix(a[i]-1); } coutcount\n; return 0; }*/ #include iostream #includealgorithm #includevector using namespace std; vectorintX; const int N109; int t[N]; //离散化操作 int getidx(int x)//读取x在X中的下标 { return lower_bound(X.begin(),X.end(),x)-X.begin()1; } //树状数组相关操作 int lowbit(int x){return x-x;} void update(int idx,int k) { for(int iidx;iX.size();ilowbit(i)) t[i]k; } int getprefix(int k) { int res0; for(int ik;i1;i-lowbit(i)) rest[i]; return res; } int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans0; int a[]{0,87,39,35,1,99,10,54,1,46,24,74,62,49,13,2,80,24,58,8,14,83,23,97,85,3,2,86,10,71,15}; int nsizeof(a)/sizeof(a[0])-1; for(int i1;in;i) X.push_back(a[i]); //排序和去重 sort(X.begin(),X.end()); X.erase(unique(X.begin(),X.end()),X.end()); for(int i1;in;i) { update(getidx(a[i]),1); ansgetprefix(X.size())-getprefix(getidx(a[i])); } coutans\n; return 0; }例题三蓝桥杯官网——压制二元组的总价值我认为最好的一道题问题描述给定两个长度为 N 的排列 A 和 B。若一对二元组下标 (i,j) 满足以下关系则被称之为压制二元组1≤ij≤N。PAi​​PAj​​其中 Px​ 表示值 x 在数组 B 中的下标。一对压制二元组的价值被定义为 j−i请你计算出所有压制二元组的价值之和。排列的定义长度为 N 的排列表示一个长度为 N 的数组其中 [1,N] 每个数都恰好出现一次。输入格式第一行输入一个整数 N(1≤N≤2×105) 表示排列的长度。第二行输入 N 个整数 A1​,A2​,A3​,…,AN​ 表示排列 A。第三行输入 N 个整数 B1​,B2​,B3​,…,BN​ 表示排列 B。保证 A,B 是一个排列。输出格式输出一个整数表示答案。样例输入4 2 4 1 3 4 1 2 3样例输出7说明样例中有效的压制二元组有 (1,4),(2,3),(2,4),(3,4)总价值为 4−13−24−24−37。//树状数组的另类用法不是简单的单点修改区间求和 #include iostream using lllong long; using namespace std; const int N2e59; ll n,h[N],a[N],b[N],c[N]; //b,c均是树状数组其中 //b维护的是映射数组a中小于a[i]的和 //c维护的是a中小于a[i]的个数 /* 代码的核心目标遍历到第 i 个元素 a[i] 时需要计算所有已遍历的、 比 a[i] 小的元素 对应的 (a[i] - 该元素值) 之和这等价于最终统计的 “带权逆序对和”。 把这个求和公式展开 总和 (a[i] - a[j1]) (a[i] - a[j2]) ... (a[i] - a[jk]) 其中 j1,j2...jk 是 i 之前的位置且 a[j] a[i]k 是这样的元素个数 进一步化简提取公因子 a[i] 总和 a[i] * k - (a[j1] a[j2] ... a[jk]) 从这个公式能直接看出我们需要两个关键数据 k已遍历元素中比 a[i] 小的元素个数对应公式里的 k sum_small已遍历元素中比 a[i] 小的元素值的总和对应公式里的 a[j1]a[j2]...a[jk]。 第二步为什么用两个树状数组分别维护这两个量 树状数组的核心能力是支持单点更新加入新元素 前缀和查询统计区间内的总和。 对于本题的场景 我们遍历元素是 “逐个加入” 的动态过程需要每次加入 a[i] 后 快速查询 [1, a[i]-1] 区间内的统计量因为 [1, a[i]-1] 就是 “比 a[i] 小的数的范围” 两个统计量个数、值的和是独立的无法用一个数组同时维护因此需要两个树状数组 c[] 元素个数 加入 1 个元素 - update(a[i], 1, c) 查询结果 比 a[i] 小的元素个数 k b[] 元素值的和 加入值 a[i] - update(a[i], a[i], b) 查询结果 比 a[i] 小的元素值的和 sum_small //核心思想转化 由题目的样例 A: 2 4 1 3 B: 4 1 2 3 我们把A映射为1 2 3 4 即h[2] 1, h[4] 2, h[1] 3, h[3] 4 那么这时B就变为2 3 1 4 记为a[N]表示b中元素在A中的位置 我们要求的就是2 3 1 4这个数组中所有满足ija[i]a[j]的a[j]-a[i]之和 根据题意此时下标之差就转化为了值之差 即(2,3), (2,4), (3,4), (1,4) (3-2) (4-1) (4-2) (4-3) (3-2) 4*3 - (123) 7 */ int lowbit(ll x){return x-x;} void update(ll a,ll b,ll*arr)//将arr数组包含位置a的管辖区间都更新b { //for(ll i1;ia;ilowbit(i)) arr[i]b;遍历方式写错了 for(ll ia;in;ilowbit(i)) arr[i]b; } ll getprefix(int k,ll*arr)//求arr区间[1,k]的和 { ll res0; for(int ik;i1;i-lowbit(i)) resarr[i]; return res; } ll query(ll l,ll r,ll*arr)//求区间和 { return getprefix(r,arr)-getprefix(l-1,arr); } int main() { ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int x;cinn; for(int i1;in;i) { //输入A数组并将其反向映射到h数组 cinx;h[x]i;//h表示A中出现的每一个数啊位置编号 } for(int i1;in;i) { //输入B数组并将其映射到A表示B在A中出现的位置 cinx;a[i]h[x]; } ll ans0;//计算结果 for(int i1;in;i) { update(a[i],a[i],b); update(a[i],1,c); ans a[i]*query(1, a[i]-1, c) - query(1, a[i]-1, b); } coutans\n; return 0; }创作不易不妨点赞关注支持一下づ3づ╭❤