c语言做的网站,网站文章标题,易货小程序开发教程,中国移动网站建设怎么做//PS#xff1a;最近修改日期#xff1a;2017-11-07 20:41:44 首先感觉这种模板类的东西写了还是很有意义的#xff0c;毕竟时不时的可以拿出来借鉴一下。 现在因为刚开始写这一类的东西#xff0c;所以说还不是很详细#xff0c;若有读者感觉可以补充#xff0c;欢迎…//PS最近修改日期2017-11-07 20:41:44 首先感觉这种模板类的东西写了还是很有意义的毕竟时不时的可以拿出来借鉴一下。 现在因为刚开始写这一类的东西所以说还不是很详细若有读者感觉可以补充欢迎反馈感激不尽 注意在本篇文章中有 #includebits/stdc.h #define LL long long typedef pair int,int pill; using namespace std; 所以以下的LL指的就是long long 的数据类型。 并且pill 指的是2元整形容器pairint,int 目录 一、读入优化 二、快速幂 三、Floyd算法 四、Dijkstra算法 五、Dijkstra算法的堆优化 六、欧几里得算法 七、扩展欧几里得 八、矩阵快速幂 九、ST表 一、读入优化 //读入数据的大小以MB作为单位的。 inline LL read(){LL base0,flag1;char ch.;while(ch9||ch0){chgetchar();if(ch-) flag-1;}while(ch0ch9){basebase*10ch-0;chgetchar();};return flag*base;
} 二、快速幂 //输出(x^k)%p的值满足k非常大n也非常大 inline LL quick_pow(LL x,LL k){ LL base1; while(k){if(k1) base(base*x)%p;k1;x(x*x)%p;}return base;
} 三、Floyd算法 //求所有的节点到每个节点的最短路的距离 inline void Floyd (){memset(dis,0x3f,sizeof(dis));for(int k1;kn;k){for(int i1;in;i){for(int j1;jn;j){dis[i][j]min(dis[i][j],dis[i][k]dis[k][j];}}}return;
} 四、Dijkstra算法 //求n点到其他点的单源最短路径长度 inline void Dijkstra (int x){int min1e91,place0; dis[x]0;memset(dis,0x3f,sizeof(dis));memset(vis,false,sizeof(vis));for(int i1;in;i){for(int j1;jn;j){if(!vis[j]dis[j]min){mindis[j];placej;}}if(place0)break;vis[place]true;for(int jhead[place];j!-1;jedge[j].next){if(!vis[edge[j].to]dis[edge[j].to](edge[j].disdis[place])){dis[edge[j].to]edge[j].disdis[place];}}}return;
} 五、Dijkstra的堆优化 //求n点到其他点的单源最短路径长度 inline void Dijkstra (int x){priority_queuepill,vectorpill,greaterpill q;dis[s]0;q.push(make_pair(dis[s],s));while(!q.empty()){pill tempq.top();q.pop();numbtemp.second;if(vis[numb])continue;vis[numb]1;for(int ihead[numb];i!-1;iedge[i].next){if(dis[edge[i].to]dis[numb]edge[i].dis){dis[edge[i].to]dis[numb]edge[i].dis;q.push(make_pair(dis[edge[i].to],edge[i].to));}}}return;
} 六、欧几里得算法 //求最大公约数 inline LL gcd(LL a,LL b){if(a%b0)return b;else return gcd(b,a%b);
} 七、扩展欧几里得 //在求最大公约数的同时求axbygcd(a,b)的整数解 inline LL exgcd(LL a,LL b,LL x,LL y){if(b0){x1;y0;return a;}else{ansexgcd(b,a%b,x,y);LL tempx;xy;ytemp-(a/b)*y;return ans;}
} 八、矩阵快速幂 //线性代数中比较重要的一课 struct Mat{LL mat[105][105];
}
Mat operator *(Mat a,Mat b){Mat c;memset(c.mat,0,sizeof(c.mat));for(int k0;kn;k)for(int i0;in;i)for(int j0;jn;j)c.mat[i][j]a.mat[i][k]*b.mat[k][j];return c;
}
void work(){for(int i0;in;i){for(int j0;jn;j)scanf(%lld,x.mat[i][j]);res.mat[i][i]1;}}while(k){if(k1) resres*x;k1;xx*x;}
} 九、ST表 //灵活运用二进制进行加速的访问操作 inline void ST(){scanf(%d%d,n,m);for(int i1;in;i) scanf(%d,f[i][0]);LOG[0]-1; for(int i1;in;i) LOG[i]LOG[i/2]1;power[0]1; for(int i1;iLOG[n];i) power[i]power[i-1]*2;for(int j1;jLOG[n];j)for(int i1;in;i)if(ipower[j-1]-1n)f[i][j]max(f[i][j-1],f[ipower[j-1]][j-1]); return;
} 等待补充。。。。。。 转载于:https://www.cnblogs.com/ACworker/p/7725467.html
