目录
引言:不同的人模版不同,程序是人思维的结晶,最好用自己的代码,殊途同归!
(以下模版均有其对应的分析博客,点击标题即可跳转)
数据结构篇
1.并查集
2.字典树
3.线段树与树状数组
4.ac自动机
5.大根堆
算法篇
1.KMP算法
2.素数处理
3.gcd与扩展gcd
4.二分查值法
(1).最大化最小值
(2).最小化最大值
5.排序算法合集(模版仅摘选几个高效的)
(1).插入排序
(2).冒泡排序
(3).归并排序
(4).堆排序
(5).快速排序
(6).计数排序
(7).基数排序
6.快速幂算法
待整理的代码
数据结构篇
1.并查集
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。
//并查集(路径压缩)
const int max_n=100005;
int par[max_n];
void init(int n){ //初始化
for(int i=1;i<=n;i++) par[i]=i;
}
int find(int x){ //查找x所在集合的根
if(par[x]!=x) par[x]=find(par[x]);//递归返回的同时压缩路径
return par[x];
}
void unite(int x,int y){ //合并x与y所在集合
x=find(x);
y=find(y);
par[x]=y;
}
bool same(int x,int y){ //x与y在同一集合则返回真
return find(x)==find(y);
}
2.字典树
处理大量字符串
//一个只带更新字符串与查找字符串的字典树 （为了效率以数组实现）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int maxn=26; //这里假设字符串中只出现26个小写字母
const int maxm=100000;
struct treenode{
bool end; //标志此节点是否是某字符串的结尾
treenode* next[maxn];
}head;
treenode memory[maxm];
int mallocp=0;
void init(){
head.end=1;
for(int i=0;i<maxn;i++) head.next[i]=NULL;
}
treenode* createnew(){
treenode* newnode;
newnode=&memory[mallocp++];
newnode->end=0;
for(int i=0;i<maxn;i++) newnode->next[i]=NULL;
return newnode;
}
void update(char* s){
int k=0,temp;
treenode* t=&head;
while(s[k]){
temp=s[k]-97;
if(!t->next[temp]) t->next[temp]=createnew();
t=t->next[temp];
k++;
}
t->end=1;
}
bool search(char* s){
int k=0,temp;
treenode* t=&head;
while(s[k]){
temp=s[k]-97;
if(!t->next[temp]) return false;
t=t->next[temp];
k++;
}
if(t->end) return true;
return false;
}
int main(){
init();
char x[1000];
char t;
while(1){
fflush(stdin);
scanf("%c",&t);
if(t=='q'){
scanf("%s",&x);
if(search(x)) printf("匹配成功！\n");
else printf("匹配失败！\n");
}
else if(t=='u'){
scanf("%s",&x);
update(x);
printf("更新完毕！\n");
}
else if(t=='e'){
printf("退出ing....\n");
break;
}
else printf("无效命令！,请重新输入！\n");
}
return 0;
}
//一个以链表实现带删除功能允许重复字符串的字典树
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int charmapping[256]; //字符映射数组,charmapping[i]=x表示ascii码为i的字符对应于treenode中的next[x]
void init_charmapping(){
for(int i='a';i<='z';i++){ //我的这个字典树现在只允许输入小写字符组成的字符串,然而由于有charmapping的存在,增加新字符添加映射并且增大maxn就好,很方便.
charmapping[i]=i-'a';
}
}
const int maxn=26; //这里假设字符串中只出现26个小写字母
const int maxm=100000;
struct treenode{
int count; //标志此节点所表示字符串在所有字符串中以前缀形式出现的总次数
treenode* next[maxn];
}head;
void init_trie(){
head.count=1; //初始化为1包括空串并且避免树头被删
for(int i=0;i<maxn;i++) head.next[i]=NULL;
}
treenode* createnew(){ //申请一个新结点并初始化它
treenode* newnode;
newnode=(treenode*)malloc(sizeof(treenode));
newnode->count=0;
for(int i=0;i<maxn;i++) newnode->next[i]=NULL;
return newnode;
}
void update(char* s,int num){ //向字典树添加num个字符串s
int k=0,temp;
treenode* t=&head;
while(s[k]){
t->count+=num;
temp=charmapping[s[k]];
if(!t->next[temp]) t->next[temp]=createnew();
t=t->next[temp];
k++;
}
t->count+=num;
}
bool search(char* s,int num){ //查找字典树中是否已经存在num个字符串s
int k=0,temp;
treenode* t=&head;
while(s[k]){
temp=charmapping[s[k]];
if(!t->next[temp]||t->next[temp]->count<num) return false; //根本不存在字符串s或者存在的数目小于num直接失败
t=t->next[temp];
k++;
}
int snum=t->count;
for(int i=0;i<maxn;i++) if(t->next[i]) snum-=t->next[i]->count; //这里是核心!!!结点t代表的字符串出现的次数就是总次数减去所有子节点次数和
if(snum>=num) return true; //如果字符串s的数目snum大于等于num
return false;
}
void erase(char* s,int num){ //删除字典树中的num个字符串s并释放无用结点,删除前一定要先search是否存在
int k=0,temp;
treenode* t=&head;
treenode* t1; //t1后面的结点都是删除后需要被释放的
head.count-=num;
while(s[k]){
temp=charmapping[s[k]];
t->next[temp]->count-=num;
if(t->next[temp]->count==0){
t1=t->next[temp];
t->next[temp]=NULL;
k++;
break;
}
t=t->next[temp];
k++;
}
while(s[k]){ //释放无用结点
temp=charmapping[s[k]];
t=t1->next[temp];
free(t1);
t1=t;
k++;
}
free(t1);
}
char temp[1000];
void printall(treenode* tnode,int pos){ //递归打印字典树咯,打出了就是字典序升序的
int count=tnode->count;
for(int i=0;i<maxn;i++) if(tnode->next[i]) count-=tnode->next[i]->count;
for(int i=0;i<count;i++) printf("\"%s\"\n",temp);
for(int i='a';i<='z';i++){
if(tnode->next[charmapping[i]]){
temp[pos]=i;
temp[++pos]='\0';
printall(tnode->next[charmapping[i]],pos);
temp[--pos]='\0';
}
}
}
int main(){
init_charmapping(); //初始化映射
init_trie(); //初始化字典树
char x[1000];
char order; //命令
int num; //数目
printf("q：查询\nu：插入\nd：删除\np：打印字典树\ne：退出\n");
while(1){
printf("请输入命令：");
fflush(stdin);
scanf("%c",&order);
if(order=='q'){
printf("请输入要查找的字符串与数目：");
scanf("%s%d",&x,&num);
if(search(x,num)) printf("匹配成功。\n\n");
else printf("匹配失败，不存在%d个\"%s\"\n\n",num,x);
}
else if(order=='u'){
printf("请输入要插入的字符串与数目：");
scanf("%s%d",&x,&num);
update(x,num);
printf("%d个\"%s\"已加入字典树。\n\n",num,x);
}
else if(order=='d'){
printf("请输入要删除的字符串与数目：");
scanf("%s%d",&x,&num);
if(!search(x,num)){
printf("树中无%d个字符串\"%s\"请重新键入命令！\n\n",num,x);
continue;
}
erase(x,num);
printf("%d个\"%s\"已从字典树中删除。\n\n",num,x);
}
else if(order=='p'){
printf("当前字典树内有如下字符串：\n");
temp[0]='\0';
printall(&head,0);
}
else if(order=='e'){
printf("退出ing....\n");
break;
}
else printf("无效命令,请重新输入！\n命令q：查询是否存在字符串\n命令u：往字典树加入字符串\n命令d：删除某个字符串\n命令p：按字典序升序输出字典树\n命令e：退出程序\n\n");
}
return 0;
}
3.线段树与树状数组
RMQ,区间求和,区间状态求解这些问题
//线段树
/*
常见使用方法：
一.基于线段树的RMQ
要求完成：
1.给定s和t，求s到t区间内的最小值(求最大值只需修改部分细节)
2.给定i，x把a[i]的值修改为x
*/
#include <iostream>
#include <string.h>
using namespace std;
const int maxn=10000;
const int inf=(1<<30);
int n;
int dat[4*maxn];
int min(int a,int b){
if(a>b) return b;
return a;
}
void update(int k,int x){
k+=n-2;
dat[k]=x;
while(k>0){
k=(k-1)>>1;
dat[k]=min(dat[(k<<1)+1],dat[(k<<1)+2]);
}
}
void init(int tn){
n=1;
while(n<tn) n=(n<<1);
memset(dat,inf,2*n+1);
int t;
for(int i=1;i<=n;i++){
scanf("%d",&t);
update(i,t);
}
}
int query(int a,int b,int k,int l,int r){
if(a>r||b<l) return inf;
if(a<=l&&b>=r) return dat[k];
else{
int v1=query(a,b,(k<<1)+1,l,(l+r)>>1);
int v2=query(a,b,(k<<1)+2,((l+r)>>1)+1,r);
return min(v1,v2);
}
}
int main(){
cin>>n;
init(n);
int t1,t2;
char ch;
getchar();
while(1){
scanf("%c%d%d",&ch,&t1,&t2);
if(ch=='Q') printf("%d\n",query(t1,t2,0,1,n));
else if(ch=='U') update(t1,t2);
getchar();
}
return 0;
}
/*
二. 求指定区间和
1.求指定区间l到r的和
2.对第i个加x
*/
#include <iostream>
#include <string.h>
using namespace std;
const int maxn=10000;
int n;
int dat[4*maxn];
void update(int k,int x){
k+=n-2;
dat[k]=x;
while(k>0){
k=(k-1)>>1;
dat[k]=dat[(k<<1)+1]+dat[(k<<1)+2];
}
}
void init(int tn){
n=1;
while(n<tn) n=(n<<1);
memset(dat,0,2*n+1);
int t;
for(int i=1;i<=n;i++){
scanf("%d",&t);
update(i,t);
}
}
int query(int a,int b,int k,int l,int r){
if(a>r||b<l) return 0;
if(a<=l&&b>=r) return dat[k];
else{
int v1=query(a,b,(k<<1)+1,l,(l+r)>>1);
int v2=query(a,b,(k<<1)+2,((l+r)>>1)+1,r);
return v1+v2;
}
}
int main(){
cin>>n;
init(n);
int t1,t2;
char ch;
getchar();
while(1){
scanf("%c%d%d",&ch,&t1,&t2);
if(ch=='Q') printf("%d\n",query(t1,t2,0,1,n));
else if(ch=='U') update(t1,t2);
getchar();
}
return 0;
}
//树状数组BIT
/*
作用：
1.给定i计算1到i的和
2.给定i和x，执行ai+=x；
*/
#include <iostream>
#include <string.h>
using namespace std;
const int maxn=10000;
int bit[maxn+1],n;
int sum(int i){
int s=0;
while(i>0){
s+=bit[i];
i-=i&-i;
}
return s;
}
void add(int i,int x){
while(i<=n){
bit[i]+=x;
i+=i&-i;
}
}
void init(n){
int tn=n,t;
n=1;
while(n<tn) n=(n<<1);
memset(bit,0,2*n-1);
for(int i=1;i<=tn;i++){
scanf("%d",&t);
add(i,t);
}
}
int main(){
scanf("%d",&n);
init(n);
for(int i=1;i<=n;i++) cout<<bit[i]<<" ";
cout<<endl;
return 0;
}
//线段树的区间更新（延迟标记）
const int maxn=100000;
int treen,tl,tr,dat[4*maxn],add[4*maxn];
void init(int tn){
treen=1;
while(treen<tn) treen<<=1;
memset(dat,0,sizeof(dat));
memset(add,0,sizeof(add));
}
void pushdown(int k,int l,int r){
int temp=(r-l+1)>>1;
add[(k<<1)+1]+=add[k];
dat[(k<<1)+1]+=temp*add[k];
add[(k+1)<<1]+=add[k];
dat[(k+1)<<1]+=temp*add[k];
add[k]=0;
}
void update(int k,int l,int r,int val){
if(r<tl||l>tr) return ;
if(r<=tr&&l>=tl){
dat[k]+=val*(r-l+1);
add[k]+=val;
return ;
}
update((k<<1)+1,l,(l+r)>>1,val);
update((k+1)<<1,((l+r)>>1)+1,r,val);
}
int query(int k,int l,int r){
if(r<tl||l>tr) return 0;
if(r<=tr&&l>=tl) return dat[k];
if(add[k]) pushdown(k,l,r);
return query((k<<1)+1,l,(l+r)>>1)+query((k+1)<<1,((l+r)>>1)+1,r);
}
4.ac自动机
求解字符串多模匹配问题
#include <iostream>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <malloc.h>
using namespace std;
const int maxkeywordlen=51;
const int maxstrlen=1000001;
char keyword[maxkeywordlen],str[maxstrlen];
int charmapping[256]; //字符映射数组,charmapping[i]=x表示ascii码为i的字符对应于treenode中的next[x]
void init_charmapping(){
for(int i='a';i<='z';i++){ //我的这个字典树现在只允许输入小写字符组成的字符串,然而由于有charmapping的存在,增加新字符添加映射并且增大maxn就好,很方便.
charmapping[i]=i-'a';
}
}
struct node{
node *fail; //失败指针,此节点失配时将跳向fail所指节点
int end; //此值表示以此节点为结尾的单词个数
node *next[26]; //指向子节点
}root;
node *getnode(){ //构造 一个新结点并做好初始化,返回指向该节点的指针
node *newnode=(node *)malloc(sizeof(node));
newnode->end=0;
newnode->fail=NULL;
for(int i=0;i<26;i++) newnode->next[i]=NULL;
return newnode;
}
void insert(char *s){ //向ac自动机加入字符串s
int k=0,temp;
node* t=&root;
for(int i=0;s[i];i++){
temp=charmapping[s[i]];
if(!t->next[temp]) t->next[temp]=getnode();
t=t->next[temp];
}
t->end++;
}
void build_fail(){ //构造ac自动机的失败指针
queue<node *> q;
q.push(&root);
while(!q.empty()){
node* t=q.front();
q.pop();
for(int i=0;i<26;i++){
if(t->next[i]){
if(t==&root) t->next[i]->fail=&root;
else{
node *p=t->fail;
while(p!=NULL){
if(p->next[i]){
t->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) t->next[i]->fail=&root;
}
q.push(t->next[i]);
}
}
}
}
void free_trie(){ //释放ac自动机, 只留根节点
queue<node *> q;
for(int i=0;i<26;i++){
if(root.next[i]){
q.push(root.next[i]);
root.next[i]=NULL;
}
}
while(!q.empty()){
node* t=q.front();
q.pop();
for(int i=0;i<26;i++) if(t->next[i]) q.push(t->next[i]);
free(t);
}
}
int match(char *s){ //计算ac自动机中所有模式串在字符串s中出现的次数之和
node *now=&root;
int ans=0;
for(int i=0;s[i];i++){
int temp=charmapping[s[i]];
if(now->next[temp]) now=now->next[temp];
else{
node* p=now->fail;
while(p!=NULL&&p->next[temp]==NULL) p=p->fail;
if(p==NULL) now=&root;
else now=p->next[temp];
}
if(now->end){
node *tn=now;
while(tn!=NULL){
ans+=tn->end;
tn->end=0;
tn=tn->fail;
}
}
}
return ans;
}
int main(){
init_charmapping();
int t;
scanf("%d",&t);
while(t--){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",&keyword);
insert(keyword);
}
build_fail();
scanf("%s",&str);
printf("%d\n",match(str));
free_trie();
}
return 0;
}
5.大根堆
const int maxn=100001;
class myheap_max{
private:
int heap[maxn];
int heap_size;
public:
void init(){
for(int i=0;i<maxn;i++) heap[i]=0;
heap_size=0;
}
void clear(){
for(int i=0;i<heap_size;i++) heap[i]=0;
heap_size=0;
}
void myswap(int *t1,int *t2){ int temp=*t1;*t1=*t2;*t2=temp; } //交换函数,相当于swap
int parent(int pos){ return (pos-1)/2; } //获得pos结点的父亲节点
int left_children(int pos){ return pos*2+1; } //获得pos结点的左子节点
int right_children(int pos){ return pos*2+2; }//获得pos结点的右子节点
int size(){ return heap_size; }
bool empty(){ return heap_size==0; }
void push(int t){ //push操作
int now=heap_size++;
do{
int pa=parent(now);
if(heap[pa]>=t) break;
heap[now]=heap[pa];
now=pa;
}while(now);
heap[now]=t;
}
int top(){ //top操作
return heap[0];
}
void adjust_max(int pos){ //调整使pos结点下的子树成为一个大根堆
int l=left_children(pos),r=right_children(pos),largest;
if(l<heap_size&&heap[l]>heap[pos]) largest=l;
else largest=pos;
if(r<heap_size&&heap[r]>heap[largest]) largest=r;
if(largest!=pos){
myswap(heap+largest,heap+pos);
adjust_max(largest);
}
}
void pop(){ //pop操作
heap[0]=heap[--heap_size];
adjust_max(0);
}
};
或者
priority_queu<int> que;
算法篇
1.KMP算法
涉及字符串匹配的问题.
//kmp算法
const int maxn=100005;
int next[maxn];//next数组
void getnext(char* s){//构造next数组,真正的模版
next[0]=-1;
int i=0,j=-1; //j为什么初值赋值-1?0其实也行,仅仅是为了少一个判断,
while(s[i]){
if(j==-1||s[i]==s[j]) next[++i]=++j;
else j=next[j];
}
}
void kmp(char* a,char* b){ //输出a中每个匹配b串的下标,不同问题这个函数的写法多变
int blen=0;
while(b[blen]) blen++;
getnext(b);
int i=0,j=0;
while(a[i]){
if(j==-1||a[i]==b[j]){
i++,j++;
if(!b[j]){
printf("%d ",i-blen);
j=next[j];
}
}
else j=next[j];
}
}
2.素数处理
素数相关的问题.
// 位操作求素数
const int maxn=1000000;
int prime[maxn],primenum;
int flag[maxn/32+1];//数组大小实际缩小8倍
void wei_prime(int t){
primenum=0;
flag[0]|=3;
for(int k=1;k<=t/32+1;k++) flag[k]=0;
for(int i=2;i<=t;i++){
if(!((flag[i/32]>>(i2))&1)){
for(int j=i*i;j<=t;j+=i) flag[j/32]|=(1<<(j2));
prime[primenum++]=i;
}
}
}
void wei_prime_onlyflag(int t){
flag[0]|=3;
for(int k=1;k<=t/32+1;k++) flag[k]=0;
for(int i=2;i<=t;i++) if(!((flag[i/32]>>(i2))&1)) for(int j=i*2;j<=t;j+=i) flag[j/32]|=(1<<(j2));
}
void printby_flag(int t){
for(int i=0;i<=t;i++) if(!((flag[i/32]>>(i2))&1)) printf("%d ",i);
}
3.gcd与扩展gcd
gcd算法是一个很古老的用于计算两数最大公约数的算法,而扩展gcd是基于gcd的一个扩展算法,用于求解模线性方程ax≡b (mod n).
//gcd与扩展gcd
int gcd(int a,int b){ //返回a,b的最大公因数
if(b==0) return a;
return gcd(b,a%b);
}
ll extgcd(ll a,ll b,ll &x,ll &y){ //扩展gcd
if(b==0){
x=1;
y=0;
return a;
}
ll d=extgcd(b,a%b,x,y);
ll t=x;
x=y;
y=t-a/b*y;
return d;
}
ll cal(ll a,ll b,ll c){ //计算ax+by=c的满足条件的x
ll x,y;
ll gcd=extgcd(a,b,x,y);
if(c%gcd!=0) return -1; //不存在解
x*=c/gcd;
b/=gcd;
if(b<0) b=-b;
ll ans=x%b;
if(ans<=0) ans+=b; //对ans为负的特殊处理+
return ans;
}
4.二分查值法
用于求满足某条件的最大化最小值的答案或最小化最大值答案.
(1).最大化最小值
bool c(double mid){
//判断答案为mid时是否满足条件,满足返回true,否则false
}
void solve(){
double l=0,r=maxa,mid;
while(r-l>0.001){
mid=(l+r)/2;
if(c(mid)) l=mid;
else r=mid;
}
printf("%.1lf",l);
}
(2).最小化最大值
bool c(double mid){
//判断答案为mid时是否满足条件,满足返回true,否则false
}
void solve(){
double l=0,r=maxa,mid;
while(r-l>0.001){
mid=(l+r)/2;
if(c(mid)) r=mid;
else l=mid;
}
printf("%.1lf",r);
}
5.排序算法合集(模版仅摘选几个高效的)
(1).插入排序
(2).冒泡排序
(3).归并排序
void merge(int *a,int l,int r,int mid){
int temp[r-l],tempnum=0;
int pos1=l,pos2=mid+1;
while(pos1<=mid&&pos2<=r){
if(a[pos1]<=a[pos2]) temp[tempnum++]=a[pos1++];
else temp[tempnum++]=a[pos2++];
}
while(pos1<=mid) temp[tempnum++]=a[pos1++];
while(pos2<=r) temp[tempnum++]=a[pos2++];
for(int i=0;i<tempnum;i++) a[l+i]=temp[i];
}
void merge_sort(int *a,int l,int r){ //排序a数组中[l,r]区间内的数为升序
if(l<r){
int mid=(l+r)/2;
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
merge(a,l,r,mid);
}
}
(4).堆排序
const int maxn=100001;
class myheap_max{
private:
int heap[maxn];
int heap_size;
public:
void init(){
for(int i=0;i<maxn;i++) heap[i]=0;
heap_size=0;
}
void clear(){
for(int i=0;i<heap_size;i++) heap[i]=0;
heap_size=0;
}
void myswap(int *t1,int *t2){ int temp=*t1,*t1=*t2,*t2=temp; } //交换函数,相当于swap
int parent(int pos){ return (pos-1)/2; } //获得pos结点的父亲节点
int left_children(int pos){ return pos*2+1; } //获得pos结点的左子节点
int right_children(int pos){ return pos*2+2; }//获得pos结点的右子节点
int size(){ return heap_size; }
bool empty(){ return heap_size==0; }
void push(int t){ //push操作
int now=heap_size++;
do{
int pa=parent(now);
if(heap[pa]>=t) break;
heap[now]=heap[pa];
now=pa;
}while(now);
heap[now]=t;
}
int top(){ //top操作
return heap[0];
}
void adjust_max(int pos){ //调整使pos结点下的子树成为一个大根堆
int l=left_children(pos),r=right_children(pos),largest;
if(l<heap_size&&heap[l]>heap[pos]) largest=l;
else largest=pos;
if(r<heap_size&&heap[r]>heap[largest]) largest=r;
if(largest!=pos){
myswap(heap+largest,heap+pos);
adjust_max(largest);
}
}
void pop(){ //pop操作
heap[0]=heap[--heap_size];
adjust_max(0);
}
};
void heap_sort(int *a,int l,int r){
myheap_max que;
que.init();
for(int i=l;i<=r;i++) que.push(a[i]);
for(int i=r;i>=l;i--){
a[i]=que.top();
que.pop();
}
}
(5).快速排序
void quick_sort(int *a,int l,int r){
if(l>=r) return;
int key=a[l],left=l,right=r;
while(left<right){
while(a[right]>=key&&left<right) right--;
while(a[left]<=key&&left<right) left++;
if(left<right){
int t=a[left];
a[left]=a[right];
a[right]=t;
}
}
a[l]=a[left];
a[left]=key;
quick_sort(a,l,left-1);
quick_sort(a,left+1,r);
}
(6).计数排序
const int tmin=0; //输入数据最小界
const int tmax=1000001; //输入数据最大界
const int k=tmax-tmin+1;//区间大小
int count[k]; //这里count[i]存的是输入数据中i+tmin出现的次数
void jishu_sort(int *a,int l,int r){
for(int i=0;i<k;i++) count[i]=0;
for(int i=l;i<=r;i++) count[a[i]-tmin]++;
int pos=0;
for(int i=0;i<k;i++){
if(count[i]){
for(int j=0;j<count[i];j++) a[pos+j]=i+tmin;
pos+=count[i];
}
}
}
(7).基数排序
#include <stdio.h>
const int k=10;//关键码区间大小
void radix_sort(int* a,int l,int r,int key){ //排序a数组区间[l,r]内的数字
if(key<1||r-l+1<2) return;
int count[k]; //这里count[i]存的是输入数据中i出现的次数
for(int i=0;i<k;i++) count[i]=0;
for(int i=l;i<=r;i++) count[a[i]/key]++;
for(int i=1;i<k;i++) count[i]+=count[i-1];
int tcount[k]; //count复制数组
for(int i=0;i<k;i++) tcount[i]=count[i];
int temp[r-l]; //暂存排序结果
for(int i=l;i<=r;i++) temp[--tcount[a[i]/key]]=a[i]; //一种计数排序的思维
for(int i=0;i<r-l+1;i++) a[l+i]=temp[i]; //上传排序结果到a
//对关键码0-9分出的区间分别进行基数排序
radix_sort(a,0,count[0]-1,key/10);
for(int i=1;i<k;i++) radix_sort(a,count[i-1],count[i]-1,key/10);
}
int main(){
int a[10]={13,55,25,36,66,38,51,29,114,157};
int key=1;
for(int i=0;i<10;i++) while(key<a[i]) key*=10;
radix_sort(a,0,9,key/10);
for(int i=0;i<10;i++) printf("%d ",a[i]);
printf("\n");
return 0;
}
6.快速幂算法
ll fastpower(ll a,ll b,ll mod)//计算(a^b)%mod
{
ll ans=1;
ll powerofa=a;
while(b){
if(b&1) ans=ans*powerofa%mod;//一种位运算
powerofa=powerofa*powerofa%mod;
b>>=1;
}
return ans;
}
待整理代码
//用邻接表和邻接矩阵存图. 基于邻接表的拓扑排序
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int inf=0x3f3f3f3f;
int main(){
int v,e,x,y;
cin>>v>>e;
int a[v+1][v+1];
for(int i=0;i<=v;i++) for(int j=0;j<=v;j++) a[i][j]=i==j?0:inf;
vector<int> m[v+1];
while(e--){
cin>>x>>y;
a[x][y]=1;
m[x].push_back(y);
}
for(int i=1;i<=v;i++){
for(int j=1;j<=v;j++) cout<<a[i][j]<<" ";
cout<<endl;
}
for(int i=1;i<=v;i++){
cout<<i<<"->";
for(int j=0;j<m[i].size();j++) cout<<m[i][j]<<" ";
cout<<endl;
}
int rudu[v+1];
for(int i=0;i<v+1;i++) rudu[i]=0;
for(int i=1;i<=v;i++) for(int j=0;j<m[i].size();j++) rudu[m[i][j]]++;
queue<int> q;
for(int i=1;i<=v;i++) if(!rudu[i]) q.push(i);
int tuopuans[v];
int count=0,t,flag[v+1];
for(int i=1;i<=v;i++) flag[i]=0;
while(!q.empty()){
t=q.front();
q.pop();
if(flag[t]) break;
else flag[t]=1;
tuopuans[count++]=t;
for(int i=0;i<m[t].size();i++) if(--rudu[m[t][i]]==0) q.push(m[t][i]);
}
if(count!=v) cout<<"wrong"<<endl;
else for(int i=0;i<v;i++) cout<<tuopuans[i]<<" ";
}
HDOJ 2647 例题
#include <iostream>
#include <vector>
#include <stdio.h>
#include <queue>
using namespace std;
typedef pair<int,int> p;
int main(){
int v,e,x,y;
while(scanf("%d %d",&v,&e)!=EOF){
vector<int> m[v+1];
while(e--){
scanf("%d %d",&x,&y);
m[y].push_back(x);
}
int rudu[v+1];
for(int i=0;i<v+1;i++) rudu[i]=0;
for(int i=1;i<=v;i++) for(int j=0;j<m[i].size();j++) rudu[m[i][j]]++;
queue<p> q;
for(int i=1;i<=v;i++) if(!rudu[i]) q.push(p(i,888));
int count=0,ans=0;
while(!q.empty()){
p t=q.front();
q.pop();
ans+=t.second;
count++;
for(int i=0;i<m[t.first].size();i++) if(--rudu[m[t.first][i]]==0) q.push(p(m[t.first][i],t.second+1));
}
if(count!=v) cout<<"-1"<<endl;
else cout<<ans<<endl;
}
}
//单源最短路问题
//beelman_ford比尔曼—福特算法 允许负边的存在
struct edge{
int from,to,cost;
};
edge es[max_e];
int d[max_v];
int v,e;
void shortest_path(int s){
for(int i=0;i<v;i++) d[i]=inf;
d[s]=0;
while(true){
bool update=true;
for(int i=0;i<e;i++){
edge e=es[i];
if(d[e.from]!=inf&&d[e.to]>d[e.from]+e.cost){
d[e.to]=d[e.from]+e.cost;
update=false;
}
}
if(update) break;
}
}
//检查是否存在负圈
bool find_negative_loop(){
memset(d,0,sizeof(d));
for(int i=0;i<v;i++){
for(int j=0;j<e;j++){
edge t=es[j];
if(d[e.from]!=inf&&d[e.to]>d[e.from]+t.cost){
d[e.to]=d[e.from]+e.cost;
if(i==v-1) return true;
}
}
}
return false;
}
//dijkstra迪杰斯特拉算法 不允许负边的存在
struct edge{
int to,cost;
};
typedef pair<int,int> p;
int v;
vector<edge> g[max_v];
int d[max_v];
void dijkstra(int s){
priority_queue<p,vector<p>,greater<p> > q;
fill(d,d+v,inf);
d[s]=0;
q.push(p(0,s));
while(!q.empty()){
p t=q.top();
q.pop();
int v=t.second;
if(d[v]<t.first) continue; //避免上一个点到这个点有多个路径
for(int i=0;i<g[v].size();i++){
edge e=g[v][i];
if(d[e.to]>d[v]+e.cost){
d[e.to]=d[v]+e.cost;
q.push(p(d[e.to],e.to));
}
}
}
}
// Floyd-warshall 弗洛伊德算法 任意两点间最短路
int d[max_v][max_v];
int v;
void warshall_floyd(){
for(int i=0;i<v;i++) for(int j=0;j<v;j++) if(i==j) d[i][i]=0; else d[i][j]=INF;
for(int k=0;k<v;k++) for(int i=0;i<v;i++) for(int j=0;j<v;j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
//以dijsktra路径还原
struct edge{
int to,cost;
};
typedef pair<int,int> p;
int v,s;
vector<edge> g[max_v];
int d[max_v];
int prev[max_v];
void dijkstra(int s){
priority_queue<p,vector<p>,greater<p> > q;
fill(d,d+v,inf);
fill(prev,prev+v,-1);
d[s]=0;
q.push(p(0,s));
while(!q.empty()){
p t=q.top();
q.pop();
int v=t.second;
if(d[v]<t.first) continue;
for(int i=0;i<g[v].size();i++){
edge e=g[v][i];
if(d[e.to]>d[v]+e.cost){
d[e.to]=d[v]+e.cost;
prev[e.to]=v;
q.push(p(d[e.to],e.to));
}
}
}
}
//kruskal克鲁斯卡尔算法
#include <iostream>
#include <algorithm>
using namespace std;
#define max_v 1000
#define max_e 5000
int par[max_v];
void init(int n){
for(int i=0;i<n;i++) par[i]=i;
}
int find(int x){
if(par[x]==x) return x;
return par[x]=find(par[x]);
}
void unite(int x,int y){
x=find(x);
y=find(y);
if(x==y) return;
par[x]=y;
}
bool same(int x,int y){
return find(x)==find(y);
}
struct edge{
int u,v,cost;
};
bool comp(const edge& e1,const edge& e2){
return e1.cost<e2.cost;
}
edge es[max_e];
int v,e;
int kruskal(){
sort(es,es+e,comp);
init(v); //并查集初始化
int res=0;
for(int i=0;i<e;i++){
edge e=es[i];
if(!same(e.u,e.v)){
unite(e.u,e.v);
res+=e.cost;
}
}
return res;
}
int main(){
cin>>v>>e;
for(int i=0;i<e;i++) cin>>es[i].u>>es[i].v>>es[i].cost;
cout<<kruskal()<<endl;
return 0;
}
//prim算法普通实现
const inf=(1<<30);
const max_n=1000;
int cost[max_n][max_n];
int mincost[max_n];
bool used[max_n];
int n;
int prim(){
for(int i=0;i<n;i++){
used[i]=false;
mincost[i]=inf;
}
mincost[0]=0;
int res=0;
while(true){
int v=-1;
for(int i=0;i<n;i++) if(!used[i]&&(v==-1||mincost[i]<mincost[v])) v=i;
if(v==-1) break;
used[v]=true;
res+=mincost[v];
for(int i=0;i<n;i++) mincost[i]=min(mincost[i],cost[u][v]);
}
return res;
}
//prim算法小根堆实现
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> p;
const int max_n=1000;
const int inf=(1<<30);
vector<p> m[max_n];
bool used[max_n];
int v,e;
int prim(){
priority_queue<p,vector<p>,greater<p> > q;
q.push(p(0,1));
int res=0,num=0;
while(!q.empty()){
p t=q.top();
q.pop();
num++;
res+=t.first;
int v=t.second;
used[v]=1;
for(int i=0;i<m[v].size();i++){
p temp=m[v][i];
if(!used[temp.second]) q.push(temp);
}
while(!q.empty()&&used[q.top().second]) q.pop();
}
if(num==v) return res;
else return -1;// 表示是一个非连通图
}
int main(){
int from,to,c;
while(cin>>v>>e,~v){
for(int i=0;i<v+1;i++){
m[i].clear();
used[i]=false;
}
while(e--){
cin>>from>>to>>c;
m[from].push_back(p(c,to));
m[to].push_back(p(c,from));
}
cout<<prim()<<endl;
}
return 0;
}
/*
测试范例：
7 9
1 2 1
2 3 2
2 4 3
3 5 10
2 7 7
4 7 1
4 6 5
5 7 5
6 7 8
*/
//sort的比较函数返回值意义是：为真时前置a
//升序排列：
bool comp(int a,int b){ return a<b; }
//降序排列：
bool comp(int a,int b){ return a>b; }
//针对有序数组可用的三个查找函数
/*
lower_bound(int *start,int *end,int a) :返回值是区间中第一个大于等于a的元素的指针
upper_bound(int *start,int *end,int a) :返回值是区间中第一个大于a的元素的指针
equal_bound(int *start,int *end,int a) :返回值是一个pair<int*,int*>,是指向相等元素所在区间的 左闭右闭 区间的一对指针
int a[7]={1,2,3,3,3,4,5};
pair<int*,int*> t=equal_range(a,a+7,3);
for(int* i=t.first;i!=t.second;i++) cout<<*i<<" ";
注意事项：
1.默认传入区间元素已经是升序排列
2.cout<<*lower_bound(a,a+7,3)<<endl; 这样即可直接确定值
3.返回值直接减数组名可得下标值： lower_bound(int *start,int *end,int a)-num表示插入a时a应插入位置
4.upper_bound(int *start,int *end,int a)-lower_bound(int *start,int *end,int a)可求得相等元素个数
5.可自己编写第四个参数并传入作为比较规则
*/
//枚举函数
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
int a[5]={1,2,3,4,5};
stable_sort(a,a+5);//从小到大
do{
for(int i=0;i<5;i++) cout<<a[i]<<" ";
cout<<endl;
}while(next_permutation(a,a+5));
stable_sort(a,a+5,greater<int>());//从大到小
do{
for(int i=0;i<5;i++) cout<<a[i]<<" ";
cout<<endl;
}while(prev_permutation(a,a+5));
return 0;
}
//背包dp
//01背包问题 （每种物品只有一个）
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int n,m;//n是物品geshu，m是背包最大容量
scanf("%d",&n);
int w[n],v[n];// w是物品费用，v是物品价值
for(int i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]);
int dp[m+1];// 空间压缩的dp数组
for(int i=0;i<=m;i++) dp[i]=0; //要求装满背包时初始化为inf
for(int i=0;i<n;i++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
printf("%d",dp[m]); //能获得的最大价值
return 0;
}
//完全背包问题 （每种物品无限个）
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int n,m;//n是物品geshu，m是背包最大容量
scanf("%d",&n);
int w[n],v[n];// w是物品费用，v是物品价值
for(int i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]);
int dp[m+1];// 空间压缩的dp数组
for(int i=0;i<=m;i++) dp[i]=0;
for(int i=0;i<n;i++) for(int j=w[i];j<=m;j++) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
printf("%d",dp[m]); //能获得的最大价值
return 0;
}
//多重背包问题 （每种物品有ki个）
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
int n,m;//n是物品geshu，m是背包最大容量
scanf("%d",&n);
int w[n],v[n],k[n];// w是物品费用，v是物品价值，k是物品个数
for(int i=0;i<n;i++) scanf("%d%d%d",&w[i],&v[i],&k[i]);
int dp[m+1];// 空间压缩的dp数组
for(int i=0;i<=m;i++) dp[i]=0;
for(int i=0;i<n;i++){
if(k[i]*w[i]>=m) for(int j=w[i];j<=m;j++) dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
else{
int tk=k[i];
int k=1;
while(k<=tk){
for(int j=m;j>=k*w[i];j--) dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
tk-=k;
k<<=1;
}
if(tk) for(int j=m;j>=tk*w[i];j--) dp[j]=max(dp[j],dp[j-tk*w[i]]+tk*v[i]);
}
}
printf("%d",dp[m]); //能获得的最大价值
return 0;
}
//3种背包问题的封装
void zeroonepack(int w,int v){ //01背包
for(int i=m;i>=w;i--) dp[i]=max(dp[i],dp[i-w]+v);
}
void completepack(int w,int v){ //完全背包问题
for(int i=w;i<=m;i++) dp[i]=max(dp[i],dp[i-w]+v);
}
void multiplepack(int w,int v,int k){
if(w*k>=m) completepack(w,v);
else{
for(int t=1;t<=k;k-=t,t<<=1) zeroonepack(t*w,t*v);
if(k) zeroonepack(k*w,k*v);
}
}
//LCS 最长公共子序列 待搞成m+n
#include <iostream>
using namespace std;
int main(){
string a,b;
cin>>a>>b;
int alen=a.length(),blen=b.length();
int dp[alen+1][blen+1];
for(int i=0;i<alen;i++) dp[i][0]=0;
for(int i=0;i<blen;i++) dp[0][i]=0;
for(int i=0;i<alen;i++){
for(int j=0;j<blen;j++){
if(a[i]==b[j]) dp[i+1][j+1]=dp[i][j]+1;
else dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
}
}
cout<<dp[alen][blen]<<endl; //a和b的最长公共子序列长度
int i=alen,j=blen,k=0; //输出最长公共子序列
int path[alen];
while(dp[i][j]){
if(dp[i][j]==dp[i-1][j]) i--;
else if(dp[i][j]==dp[i][j-1]) j--;
else{
path[k++]=i-1;
i--;
j--;
}
}
for(int i=k-1;i>0;i--) printf("%c ",a[path[i]]);
printf("%c\n",a[path[0]]);
return 0;
}
//LIS最长上升子序列 n*logn复杂度 二分法实现
#include <iostream>
#include <stdio.h>
using namespace std;
const int inf=(1<<30);
int main(){
int n,t,res=0;
scanf("%d",&n);
int a[n],dp[n];
//dp[i]的含义是长度为i+1的上升子序列中末尾元素的最小值，故dp数组中存的不是最长上升子序列
for(int i=0;i<n;i++) scanf("%d",&a[i]);
fill(dp,dp+n,inf);
for(int i=0;i<n;i++) *lower_bound(dp,dp+n,a[i])=a[i];
printf("%d\n",lower_bound(dp,dp+n,inf)-dp);
return 0;
}
