char a[maxn]; int p[maxn]; //manachervoid manacher(char *s){int len = strlen(s+1);int m = 2*len+1;for(int i=1; i<=len; i++){a[i<<1] = s[i];a[i<<1|1] = ‘#‘;}a[0] = ‘+‘; a[1] = ‘#‘; a[m+1] = ‘-‘;// cout<<a<<endl;int mx=0, idx;for(int i=1; i<=m; i++) {if(mx > i)p[i] = min(p[2*idx-i], mx-i);elsep[i] = 1;for(; a[i-p[i]]==a[i+p[i]]; p[i]++);if(p[i]+i > mx) mx = p[i]+i, idx=i;}// for(int i=1; ...
题目大意：给一张无向图，求出最小树形图。题目分析：套朱-刘算法模板就行了。。。 代码如下：# include<iostream> # include<cstdio> # include<cstring> # include<algorithm> using namespace std; # define LL long long # define REP(i,s,n) for(int i=s;i<n;++i) # define CL(a,b) memset(a,b,sizeof(a)) # define CLL(a,b,n) fill(a,a+n,b)const int N=1005; const int INF=1<<30; struct Edge {int fr,to,w; }; Edge e[N*4...
这篇文章主要介绍了Python基于回溯法子集树模板解决旅行商问题（TSP）,简单描述了旅行商问题并结合实例形式分析了Python使用回溯法子集树模板解决旅行商问题的相关实现步骤与操作技巧,需要的朋友可以参考下本文实例讲述了Python基于回溯法子集树模板解决旅行商问题（TSP）。分享给大家供大家参考，具体如下：问题旅行商问题（Traveling Salesman Problem,TSP）是旅行商要到若干个城市旅行，各城市之间的费用是已知的，为了节省费用...
这篇文章主要介绍了Python基于回溯法子集树模板实现8皇后问题,简单说明了8皇后问题的原理并结合实例形式分析了Python回溯法子集树模板解决8皇后问题的具体实现技巧,需要的朋友可以参考下本文实例讲述了Python基于回溯法子集树模板实现8皇后问题。分享给大家供大家参考，具体如下：问题88格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。分析为了简化问题，考...
问题描述：目的：使用C++模板设计循环链表的抽象数据类型（ADT）。并在此基础上，使用循环链表ADT的基本操作，设计并实现单链表的简单算法设计。 内容：（1）请使用模板设计循环链表的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的单链表ADT原型文件，自行设计循环链表的ADT。） （2）ADT的简单应用：使...
基础介绍 数据结构 1. 软件 = 程序 + 文档 程序 = 数据结构 + 算法 2. 对于一个数据结构来讲，需要做到增删减查四个基本功能。 堆栈 堆栈是一种数据结构。堆栈都是一种数据项按序排列的数据结构,只能在一端(称为栈顶(top))对数据项进行插入和删除。 堆栈就像一个圆柱体的硬币盒（只开一边口），每次只能从顶部操作，后进先出，每次只能取得最顶部的一枚硬币。 模板类 在定义类之前，使用template<class Item>获得一个模板 (item处...
愿意写代码的人一般都不太愿意去写文章，因为代码方面的艺术和文字中的美学往往很难兼得，两者都兼得的人通常都已经被西方极乐世界所收罗，我也是只喜欢写代码，让那些字母组成美妙的歌曲，然后自我沉浸在其中自得其乐。而今天，在清明之际，在踏青时节，我还是忍不住停下来歇歇脚，稍微共享一下最近一直研究的一个非常基础的算法和应用 - 多目标多角度的模板匹配。 模板匹配，这是一个几十年来一直为业界所重点研究和处理的...
基础算法模板 排序二分和前缀和二分求红色部分的右边界求绿色部分的左边界 前缀和差分一维差分二维差分双指针算法 题目来自Acwing 网站，该专栏为博主在ACWing算法基础课上的学习记录和总结。 排序基础算法模板题（一）—— 排序 二分和前缀和 二分求红色部分的右边界 int l = 0, r = n-1; while(l < r ){int mid = l + r + 1 >>1;if(check(红色性质是否满足)) l =mid;else r = mid -1; }这里mid之所以要加上1，是当区间长度为2时，...
今天我们来讲一下kmp（看毛片）算法 讲到字符串操作有那些算法时，相信学过数据结构的小伙伴们都能想到kmp算法。 那么什么是kmp算法呢？从百度百科我们可以知道，kmp是三个人共同研究出来的一个算法，并以他们的名字命名。它的前身是Brute-Force算法，它有一个很大的缺点，那就是如果当前匹配失败那么指针往前移一位继续匹配。细心的小伙伴很容易就能发现匹配串越长的话本身就不容易匹配成功，那么你每次匹配失败指针只往前移动一位...
前言：该篇博客主要记录一些算法的模板代码，比较简单就不赘述其解决的思路，如确实有不明白的可以在评论区留言，谢谢阅读~文章目录 two pointers序列合并归并排序递归实现非递归实现 快速排序普通快排生成随机数two pointers 给定一个递增或递减的序列和一个正整数 M，求两个不同位置上的数 a 和 b，使得 a + b = M。 while (i < j){if (a[i] + a[j] == M){printf("%d %d\n", i, j);++i; --j;}else (a[i] + a[j] < M)++i;else--j;...
第三部分：搜索与图论 1.树与图的存储 树是一种特殊的图，与图的存储方式相同。 对于无向图中的边ab，存储两条有向边a->b, b->a。 因此我们可以只考虑有向图的存储。 (1) 邻接矩阵：g[a][b] 存储边a->b (2) 邻接表： //对于每个点k，开一个单链表，存储k所有可以走到的点。 //h[k]存储这个单链表的头结点 int h[N],e[N],ne[N],idx;//添加一条边a->b void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++; } //初始化 idx=0; m...
3 顺序表ADT模板简单应用算法设计：线性表的合并 问题描述：目的：使用自行设计的顺序表ADT或STL中的vector模板，设计并实现顺序表应用场合的一些简单算法设计。 应用4：试设计一个算法，将所有在线性表LB中但不在LA中的数据元素插入到LA中,算法执行之后，线性表LB不再存在。 参考函数原型： （2）顺序表ADT版本 template void Union_Sq( SqList &LA, SqList &LB )； （2）vector版本 template void Union_Sq( vector &LA, vector ...
平衡二叉树模板 #include <bits/stdc++.h> using namespace std; struct node {int data;node *l, *r; }; node *ll(node *p) //右旋 {node *q = p->l;p->l = q->r;q->r = p;p = q;return p; } node *rr(node *p) //左旋 {node *q = p->r;p->r = q->l;q->l = p;p = q;return p; } node *lr(node *p) //先左旋再右旋 {p->l = rr(p->l);return ll(p); } node *rl(node *p) //先右旋再左旋 {p->r = ll(p->r);return rr(p); } int dep(n...
我的常用刷题网站：http://218.5.5.242:9018/JudgeOnline/https://www.luogu.com.cn/ 排序 选择排序（selection sort） 1 void selection(int n,int* a){ 2 for (int i = 0;i < n;i++){ 3 for (int j = i + 1;j < n;j++){ 4 if (a[i] > a[j]){ 5 swap(a[i],a[j]); 6 } 7 } 8 } 9 }选择排序 冒泡排序（bubble sort） void bubble(int n,int* a){for (int i = 0;i ...
没什么好说的，建议直接背过。 “Dinic的复杂度就是个笑话，跟放P一样” 看似 \(O(n^2m)\) 实则艹过 \(n=10^5,m=10^6\) #include <bits/stdc++.h> using namespace std; typedef long long ll;const int N=1e4+10,M=2e5+10,INF=1e8;int n,m,s,t; int head[N],ver[M],nxt[M],cc[M],tot=0; void add(int x,int y,int c) {ver[tot]=y;cc[tot]=c;nxt[tot]=head[x];head[x]=tot++;ver[tot]=x;cc[tot]=0;nxt[tot]=head[y];head[y]=tot++;...