电商网站制作方案,合肥做网站行吗,做公众号封面图的网站,宣传网站设计目录 一、trie树
题目描述#xff1a;
输入格式
输出格式
输入样例#xff1a;
输出样例#xff1a;
①、思路
②、代码实现
二、并查集
1、样例
题目描述#xff1a;
输入格式
输出格式
输入样例#xff1a;
输出样例#xff1a;
①、思路
②、代码实现…目录 一、trie树
题目描述
输入格式
输出格式
输入样例
输出样例
①、思路
②、代码实现
二、并查集
1、样例
题目描述
输入格式
输出格式
输入样例
输出样例
①、思路
②、代码实现
2、应用并查集
题目描述
输入格式
输出格式
数据范围
输入样例
输出样例
①、思路
②、代码
三、堆排序
题目描述
输入格式
输出格式
数据范围
输入样例
输出样例
①、思路
②、代码
四、模拟哈希表
1、离散化
题目描述
输入格式
输出格式
数据范围
输入样例
输出样例
①、思路
②、代码
2、模拟散列表
题目描述
输入格式
输出格式
数据范围
输入样例
输出样例
①、思路
1、拉链法
2、开放寻址法
五、图论
Ⅰ、树与图的遍历
①、深度优先遍历
②、广度优先遍历
Ⅱ、拓扑排序有向图
六、最短路径图论
Ⅲ、dijkstra算法
①、dijkstraⅠ(朴素算法)
②、dijkstraⅡ优先队列优化
Ⅳ、bellman - ford算法 一、trie树
题目描述 维护一个字符串集合支持两种操作
I x 向集合中插入一个字符串 xQ x 询问一个字符串在集合中出现了多少次。
共有 N 个操作所有输入的字符串总长度不超过 105105字符串仅包含小写英文字母。
输入格式
第一行包含整数 N表示操作数。
接下来 N 行每行包含一个操作指令指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x都要输出一个整数作为结果表示 x 在集合中出现的次数。
每个结果占一行。
输入样例
5
I abc
Q abc
Q ab
I ab
Q ab输出样例
1
0
1①、思路 trie树就是可以查询字符串出现次数的一种结构我们使用数组实现。idx用来区分每个结点使得每个节点的值不相同cnt表示每个字符串的末尾从而记录没个字符串出现过几次son[i][j]表示i结点指向j结点同时其值就是j结点本身的值p用来遍历过程中的结点路径。 ②、代码实现 #includeiostream
using namespace std;
const int N 1e5 10;char st[N];
int cnt[N], idx, son[N][27];void insert(char str[])
{int p 0;for(int i 0; str[i]; i){int u str[i] - a;if(!son[p][u]) son[p][u] idx;p son[p][u];}cnt[p] ;
}int query(char *str)
{int p 0;for(int i 0; str[i]; i){int u str[i] - a;if(!son[p][u]) return 0; //该节点不存在即该字符串不存在p son[p][u]; }return cnt[p]; //返回字符串出现的次数
}int main()
{int n;scanf(%d, n);while( n -- ){char op[2];scanf(%s %s, op, st);if(op[0] I) insert(st);else printf(%d\n, query(st));}return 0;
}
二、并查集
1、样例
题目描述
一共有 n 个数编号是 1∼n1∼最开始每个数各自在一个集合中。
现在要进行 m个操作操作共有两种
M a b将编号为 a 和 b 的两个数所在的集合合并如果两个数已经在同一个集合中则忽略这个操作Q a b询问编号为 a和 b的两个数是否在同一个集合中
输入格式
第一行输入整数 n 和 m。
接下来 m 行每行包含一个操作指令指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b都要输出一个结果如果 a和 b 在同一集合内则输出 Yes否则输出 No。
每个结果占一行。
输入样例
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4输出样例
Yes
No
Yes ①、思路 核心代码
int find(int n)
{if(p[n] ! n) p[n] find(p[n]);return p[n];
}
原理时p[ i ]就表示i的祖先只有祖先才是i p[i]。
初始化时每个人都是自己的祖先也就是一开始相互独立。
for(int i 0; in; i) p[i] i;
我们模拟一下案例
M 1,2时p[find(a)] find(b) 》 p[a] bp[b] b。
Q12时find(a) 第一步p[a] b ! a,因此继续找find(p[a])。最后p[b] b。返回b。
find(b) 直接返回b。最后相同所以输出Yes。 ②、代码实现 #includeiostream
using namespace std;
const int N 1e5 10;
int p[N];//p[]表示每个数的祖宗节点。int find(int n)
{if(p[n] ! n) p[n] find(p[n]);return p[n];
}int main()
{int n,m;cinnm;for(int i 0; in; i) p[i] i;while( m -- ){char arr[2];scanf(%s, arr);int a, b;cinab;if(arr[0] M) p[find(a)] find(b);else {if(find(a) find(b)){printf(Yes\n);}else printf(No\n);}}return 0;
} 2、应用并查集
题目描述
给定一个包含 n 个点编号为 1∼n1∼的无向图初始时图中没有边。
现在要进行 m 个操作操作共有三种
C a b在点 a和点b之间连一条边a 和 b 可能相等Q1 a b询问点 a 和点 b 是否在同一个连通块中a 和 b 可能相等Q2 a询问点 a 所在连通块中点的数量
输入格式
第一行输入整数 n 和 m。
接下来 m 行每行包含一个操作指令指令为 C a bQ1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b如果 a 和 b 在同一个连通块中则输出 Yes否则输出 No。
对于每个询问指令 Q2 a输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤1e5
输入样例
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5输出样例
Yes
2
3 ①、思路 本题是个图类问题但是我们可以用并查集思路求解我们设定一个sz数组存储每个块中的结点数量。同时让每个在块内的结点直接指向最高的祖先。便可以求得节点数量。 ②、代码 #includeiostream
using namespace std;
const int N 1e5 10;
#includestring
int p[N], sz[N];//p[]表示每个数的祖宗节点。int find(int n)
{if(p[n] ! n) return p[n] find(p[n]); return p[n];
}void merge(int a, int b)
{int x find(a);int y find(b);p[x] y;sz[y] sz[x];
}bool ask(int a, int b)
{return find(a) find(b);
}int main()
{int n,m; cinnm;for(int i 0; in; i){p[i] i;sz[i] 1;}while( m -- ){int a, b; string str;cinstr;if(str C){scanf(%d %d, a, b);if(!ask(a, b)) merge(a, b);}else if(str Q1){scanf(%d %d, a, b);ask(a, b) ? printf(Yes\n) : printf(No\n);}else {scanf(%d, a);printf(%d\n, sz[find(a)]);}}return 0;
} 三、堆排序
题目描述
输入一个长度为 n 的整数数列从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数表示整数数列。
输出格式
共一行包含 m 个整数表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤1e5 1≤数列中元素≤1e9
输入样例
5 3
4 5 1 3 2输出样例
1 2 3 ①、思路 堆排序本身就是一种数组但是排序的时候就是一种模拟树状结构通过比较选出该部分最小的数并放到最前面反复进行。从而达到排序的效果。每次将最小数打印之后再将最后面的数放到最前面然后继续排序。 ②、代码 #includeiostream
using namespace std;
#includealgorithm
const int N 1e5 10;
int arr[N], sz;void down(int u)
{int t u;if(2 * u sz arr[t] arr[2 * u]) t 2 * u;if(2 * u 1 sz arr[t] arr[2 * u 1]) t 2 * u 1;if(t ! u){swap(arr[t], arr[u]);down(t);}
}int main()
{int n, m;cinnm;sz n;for(int i 1; i n; i) scanf(%d, arr[i]);for(int i n / 2; i 0; i--) down(i);while( m -- ){coutarr[1] ;arr[1] arr[sz -- ];down(1);}return 0;
} 四、模拟哈希表
1、离散化
题目描述
假定有一个无限长的数轴数轴上每个坐标上的数都是 00。
现在我们首先进行 n 次操作每次操作将某一位置 x 上的数加 c。
接下来进行 m次询问每个询问包含两个整数 l 和 r你需要求出在区间 [l,r]之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行每行包含两个整数 x 和 c。
再接下来 m 行每行包含两个整数 l 和 r。
输出格式
共 m 行每行输出一个询问中所求的区间内数字和。
数据范围
−1e9≤x≤1e9 1≤n,m≤1e5 −1e9≤l≤r≤1e9 −10000≤c≤10000
输入样例
3 3
1 2
3 6
7 5
1 3
4 6
7 8输出样例
8
0
5 ①、思路 离散化就是对于特别大范围的数进行优化的一种操作将他们都对应到小的范围从而实现求解。本题就是将所有坐标都存起来然后将重复坐标全部去除再利用二分方法求出对应的离散化坐标。然后利用前缀和进行求解。 ②、代码 #includeiostream
#includevector
using namespace std;
#includealgorithm
const int N 300010;
int a[N],s[N];
int n,m;
vectorint alls;
vectorpairint,int add,query;int find(int x)
{int l 0;int r alls.size()-1;while(lr){int mid lr1;if(alls[mid]x) r mid;elsel mid1;}return r1;
}int main()
{scanf(%d%d,n,m);for(int i 0;in;i){int x,c;scanf(%d%d,x,c);add.push_back({x,c});alls.push_back(x);}for(int i 0;im;i){int l,r;scanf(%d%d,l,r);query.push_back({l,r});alls.push_back(l);alls.push_back(r);}//去重sort(alls.begin(),alls.end());alls.erase(unique(alls.begin(),alls.end()),alls.end());//处理输入for(auto item :add){int x find(item.first);a[x]item.second;}//构建前缀和数组for(int i 1;ialls.size();i) s[i] s[i-1]a[i];//for(auto item : query){int l find(item.first);int r find(item.second);printf(%d\n,s[r]-s[l-1]);}} 2、模拟散列表
题目描述
维护一个集合支持如下几种操作
I x插入一个整数 xQ x询问整数 x 是否在集合中出现过
现在要进行 N 次操作对于每个询问操作输出对应的结果。
输入格式
第一行包含整数 N表示操作数量。
接下来 N 行每行包含一个操作指令操作指令为 I xQ x 中的一种。
输出格式
对于每个询问指令 Q x输出一个询问结果如果 x 在集合中出现过则输出 Yes否则输出 No。
每个结果占一行。
数据范围
1≤N≤1e5 −109≤x≤1e9
输入样例
5
I 1
I 2
I 3
Q 2
Q 5输出样例
Yes
No ①、思路
1、拉链法
拉链法就是利用邻接表存储其中将目标数字通过取余1e5 3。从而求解。
具体代码如下。 代码实现
#includeiostream
#includecstring
using namespace std;
#includestring
const int N 1e5 3;
int h[N], e[N], ne[N], idx;void insert(int x)
{int k (x % N N) % N;e[idx] x;ne[idx] h[k];h[k] idx;
}bool find(int x)
{int k (x % N N) % N;//次数因为c取余运算可能有负数因此这样操作。for(int i h[k]; i ! -1; i ne[i]){if(e[i] x) return true;}return false;
}int main()
{int n; cinn;memset(h, -1, sizeof(h));while(n -- ){string op; int x;cinopx;if(op I){insert(x);}else {if(find(x)){printf(Yes\n);}else {printf(No\n);}}}return 0;
} 2、开放寻址法
这种方法就是通过不断遍历如果遍历到头就返回0重新遍历然后直到找到目标值如果为空说明该位置就是应该被插入值的地方。 代码实现
#includeiostream
#includecstring
using namespace std;const int N 2e5 3; //大于数据范围的第一个质数
const int null 0x3f3f3f3f; //规定空指针为 null 0x3f3f3f3f
int n;int h[N];int find(int x) {int t (x % N N) % N;while (h[t] ! null h[t] ! x) {t;if (t N) {t 0;}}return t; //如果这个位置是空的, 则返回的是他应该存储的位置
}int main() {cin n;memset(h, 0x3f, sizeof h); //规定空指针为 0x3f3f3f3fwhile (n--) {string op;int x;cin op x;if (op I) {h[find(x)] x;} else {if (h[find(x)] null) {puts(No);} else {puts(Yes);}}}return 0;
} 五、图论 Ⅰ、树与图的遍历 ①、深度优先遍历
题目链接树与图的重心
思路
本题首先使用邻接表将所有结点都连在一起然后深度遍历时有两个变量res和sumsum表示以当前节点作为重心其它所有分支的和res表示分支里面数量最多的分支
ans作为最终结果它表示所有最大连通子路里面的最小值。 代码
#includeiostream
#includecstring
using namespace std;
const int N 1e5 10;
const int M N * 2;
int h[N], n, ans N;
int e[M], ne[M], idx;
bool st[N];void add(int a, int b)
{e[idx] b;ne[idx] h[a]; h[a] idx ;
}int dfs(int u)
{int res 0;st[u] true;int sum 1;for(int i h[u]; i ! -1; i ne[i]){int j e[i];if(!st[j]){int s dfs(j);res max(res, s);sum s;}}res max(res, n - sum);ans min(res, ans);return sum;
}int main()
{memset(h, -1, sizeof(h));cinn;for(int i 0; i n - 1; i){int a, b;cinab;add(a, b); add(b, a);}dfs(1);coutansendl;return 0;
} ②、广度优先遍历
题目链接图中点的层次
思路
本题使用邻接表进行存储然后层序遍历时使用队列进行遍历然后d数组用来存储每个点到根节点的距离最后返回dp[ n ]代表n到1的距离。 代码
#includeiostream
using namespace std;
#includecstring
#includequeueint n, m;
const int N 1e5 10;
int h[N], e[N], ne[N], idx;
int d[N];void add(int a, int b)
{e[idx] b; ne[idx] h[a]; h[a] idx ;
}int bfs()
{memset(d, -1, sizeof(d));queueint q;d[1] 0;q.push(1);while(q.size()){int t q.front();q.pop();for(int i h[t]; i ! -1; i ne[i]){int j e[i];if(d[j] -1){d[j] d[t] 1;q.push(j);}}}return d[n];
}int main()
{cinnm;memset(h, -1, sizeof(h));for(int i 0; i m; i){int a, b;cinab;add(a, b);}coutbfs()endl;return 0;
} Ⅱ、拓扑排序有向图
题目链接拓扑排序
思路
我们使用数组模拟一个队列q然后我们将入度为0的点放在队列里同时删除这个点对应的边最后依次输出q这个数组就可以了。
代码
#includeiostream
using namespace std;
#includecstring
const int N 1e5 10;
int e[N], ne[N], h[N],idx;
int n, m;
int q[N], hh 0, tt -1;
int d[N];//保存每个点的入度void add(int a, int b)
{e[idx] b; ne[idx] h[a]; h[a] idx ;
}void topsort()
{for(int i 1; i n; i){if(d[i] 0)q[tt] i;}while(hh tt){int t q[hh ];for(int i h[t]; i ! -1; i ne[i]){int j e[i];d[j] --;if(d[j] 0){q[tt] j;}}}if(tt n - 1){for(int i 0; in; i) coutq[i] ;}else puts(-1);}int main()
{cinnm;memset(h, -1, sizeof(h));while( m -- ){int x, y;cinxy;d[y] ;add(x, y);}topsort();return 0;
} 六、最短路径图论 Ⅲ、dijkstra算法
①、dijkstraⅠ(朴素算法)
题目链接disktra求最短路Ⅰ
思路
本题使用dijkstra的思路是每个最短路径都取离起点距离最小的然后用t更新节点坐标遍历过的用true标记表示已经遍历过了。最后返回dist[ n ]表示n到1的最短路径。 代码
#includeiostream
using namespace std;
#includecstring
const int N 510;
int n, m;
int g[N][N], dist[N];//g表示x到y的权重dist[N]表示点N对第一个点的最短距离。
bool st[N];int Dijkstra()
{memset(dist, 0x3f3f3f3f, sizeof(dist));dist[1] 0;for(int i 0; in; i){int t -1;for(int j 1; j n; j){if(!st[j] (t -1 || dist[t] dist[j])){t j;}}st[t] true;for(int j 1; j n; j){dist[j] min(dist[j], dist[t] g[t][j]);}}if(dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main()
{memset(g, 0x3f3f3f3f, sizeof(g));cinnm;while( m -- ){int x, y, z;cinxyz;g[x][y] min(g[x][y], z);}coutDijkstra()endl;return 0;
} ②、dijkstraⅡ优先队列优化
题目链接disktra求最短路Ⅱ
思路
本题稀疏表因此使用邻接表存储同时遍历与上面基本相同但是在基础上新加了优先队列的优化优先队列自动排序然后就可以降低时间复杂度到o(m log n)。 代码
#includeiostream
using namespace std;
#includecstring
#includequeue
typedef pairint, int PII;
const int N 1e6 10;
int e[N], ne[N], h[N], w[N], idx;
int dist[N];
bool st[N];
int n, m;void add(int a, int b, int c)
{e[idx] b; ne[idx] h[a]; w[idx] c; h[a] idx ;
}int dijkstra()
{memset(dist, 0x3f3f3f3f, sizeof(dist));dist[1] 0;priority_queuePII, vectorPII, greaterPII heap;heap.push({0, 1});while(heap.size()){PII k heap.top();heap.pop();int ver k.second; int distance k.first;if(st[ver]) continue;st[ver] true;for(int i h[ver]; i ! -1; i ne[i]){int j e[i];if(dist[j] distance w[i]){dist[j] distance w[i];heap.push({dist[j], j});}}}if(dist[n] 0x3f3f3f3f) return -1;return dist[n];
}int main()
{cinnm;memset(h, -1, sizeof(h));while( m -- ){int x, y, z;cinxyz;add(x, y, z);}coutdijkstra()endl;return 0;
} Ⅳ、bellman - ford算法
题目链接bellman-ford算法
思路
两层for循环第一层是最多k次然后循环k,之后的遍历每条边更新最小值然后我们的back数组是用来保存上一层的状态防止回权部分有重边。每条边我们使用一个结构体存储。 代码
#includeiostream
#includecstringusing namespace std;const int N 510, M 10010;struct Edge {int a;int b;int w;
} e[M];//把每个边保存下来即可int dist[N];
int back[N];//备份数组防止串联
int n, m, k;//k代表最短路径最多包涵k条边int bellman_ford() {memset(dist, 0x3f, sizeof dist);dist[1] 0;for (int i 0; i k; i) {//k次循环memcpy(back, dist, sizeof dist);for (int j 0; j m; j) {//遍历所有边int a e[j].a, b e[j].b, w e[j].w;dist[b] min(dist[b], back[a] w);//使用backup:避免给a更新后立马更新b, 这样b一次性最短路径就多了两条边出来}}if (dist[n] 0x3f3f3f3f / 2) return -2;else return dist[n];}int main() {scanf(%d%d%d, n, m, k);for (int i 0; i m; i) {int a, b, w;scanf(%d%d%d, a, b, w);e[i] {a, b, w};}int res bellman_ford();if (res -2) puts(impossible);else cout res;return 0;
}
