大数乘法:模拟乘法手算累加:和小学生一样竖式计算,逐位相乘,结果相加(很麻烦)改进:先不算任何进位,只保存每一位结果,最后从右到左相加int result[num1.length+num2.length]; //结果不会比俩数长度加起来还长
for(int i=0; i<num1.size(); i++) {for(int j=0; j<num2.size(); j++) { //不考虑进位,先乘了再说result[i+j+1] += num1[i] * num2[j];//+1位给最后最高位进位留空间}
}//单独处理进位
for(int k = result.size()-...
数据输入格式:首先输入顶点个数n和弧数m,然后输入每条弧的数据。规定源点为顶点0,汇点为顶点n-1.每条弧的数据格式为:u,v,w,分别表示这条弧的起点,终点,容量。顶点序号从0开始。代码: 1 #include <iostream>2 #include <cstdio>3 #include <cstring>4 #include <algorithm>5 #include <cmath>6 #include <string>7 #include <map>8 #include <stack>9 #include <vector>10 #include <set>11 #include <queue>12#pragma ...
什么是最小树形图?相信大家如果会过来看这篇文章,想必也应该对最小生成树有所了解的,最小生成树求的是无向图的一颗生成树的最小权值。我们的最小树形图就是来解决一个有向图的一颗生成树的最小权值,对于度娘来说,最小树形图是这样定义的:最小树形图,就是给有向带权图中指定一个特殊的点root,求一棵以root为根的有向生成树T,并且T中所有边的总权值最小。通解最小树形图的一种算法是是1965年朱永津和刘振宏提出的复杂度为O(...
算法模板汇总1、牛顿迭代法(c++代码)int mysqrt(int x){double tmps = x;double k = 1.0;double k0 = 0.0;while(abs(k0-k) >= 1){k0 = k;k = (k + tmpx/k)/2;}return (int)k;
} 2、二分查找代码模板left, right = 0, len(array) - 1
while left <= right:mid = (left + right) / 2if array[mid] == target:#find the target!!breakorreturn resultelif array[mid] < target:left = mid + 1else:right = mid + 1 3、递归代码模板def...
1.归并排序板子(包含求逆序对个数):#include<bits/stdc++.h>
usingnamespace std;
constint maxn=1e5+10;
int a[maxn],tmp[maxn];
int ans=0;void merge_sort(int l,int r)
{if(l>=r)return;int mid=l+r>>1;merge_sort(l,mid);merge_sort(mid+1,r);int i=l,j=mid+1,k=0;while(i<=mid&&j<=r){if(a[i]<=a[j])tmp[k++]=a[i++];else{ans+=mid-i+1;tmp[k++]=a[j++];}}while(i<=mid)tmp[k++]=a[i++];while(j<=r)tmp[k++]=a[j++];for(i...
详解:http://blog.csdn.net/wall_f/article/details/8207595算法时间复杂度:O(E * V * V) 1 #include <cstdio>2 #include <cstring>3 #include <queue>4 #include <vector>5usingnamespace std;6#define N 1057#define M 10108#define INF 0x3f3f3f3f910struct Edge {
11int u, v, cap;
12 Edge () {}
13 Edge (int u, int v, int cap) : u (u), v (v), cap (cap) {}
14 }edge[N*N];
15 vector<int> G[N];
16int S, T, ...
1 #include <stdio.h>2 #include <string.h>3 #include <algorithm>4usingnamespace std;5constint N=1001;6constint inf=1<<29;7int w[N][N];8int dis[N],flag[N];9int n,m,u,v,c;
10int prim()
11{
12int sum=0;//计算最小距离13 memset(flag,0,sizeof(flag));
14for(int i=1; i<=n; i++)
15 {
16 dis[i]=w[1][i];//把起点到每个点的距离付给dis17 }
18 flag[1]=1;
19for(int i=1; i<n; i++)//会更新n-1次...
一、为什么要有模板?将类型参数化,可以实现算法与类型的分离,编写针对类型更加抽象的函数或者类。 二、函数模板通用定义:template<typename 类型形参1, ...>返回类型 函数模板名 (形参表) { ... }特化定义:template<>返回类型 函数模板名<类型实参1, ...> (形参表) { ... } 三、类模板通用定义:template<typename 类型形参1, ...>class 类模板名 { ... };全类特化:template<>class 类模板名<类型实参1, ...> { ... };成员特...
该模板来自大白书 【解释】给多个语句,每个语句为“ Xi为真(假) 或者 Xj为真(假)”每个变量和拆成两个点 2*i为假, 2*i+1为真“Xi为真 或 Xj为真” 等价于 “Xi为假 –> Xj为真”。DFS算法没有回溯过程。 【函数说明】模板bfs函数在模板外一般用不到void init(int n) :初始化void add(int x,int xval,int y,int yval) :添加边,x,y为节点编号,xval=1表示真,xval=0表示假,yval同理bool solve() :计算是否存在解。如果存在解返...
模板—算法—整体二分(区间k小值)Code:#include <cstdio>
#include <algorithm>
using namespace std;
#define N 200010
int num[N],number[N],tmp[N],ans[N],n,m,id[N];
struct Ask {int l,r,id,k;}ask[N],ask1[N],ask2[N];
void change(int x,int y) {while(x<=n) tmp[x]+=y,x+=x&-x;}
int find(int x) {int sum=0;while(x) sum+=tmp[x],x-=x&-x;return sum;}
bool cmp(const int &a,const int &b) {return num[a]<num[b];}
in...
#include<iostream>
#include<algorithm>usingnamespace std;int f[20000],n;struct node
{int u,v,val;booloperator < (node&a) const{return val<a.val;}
}e[20000];int findx(int x)
{if(x==f[x])return x;return f[x]=findx(f[x]);
}
int main()
{int k,ans,x,y;while(cin>>n){ans=0;k=(n*(n-1))/2;for(int i=1;i<=n;i++)f[i]=i;for(int i=0;i<k;i++)cin>>e[i].u>>e[i].v>>e[i].val;sort(e,e+k);for(int i=0;i<k;i++){x=findx(...
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
usingnamespace std;constint maxn=1111;//有多少个结点
vector<int>G[maxn];
int visited[maxn];//标记该节点有没有访问过int node,edge;//顶点数目int tmpdfn;//dfs过程中记录当前的深度优先搜索序数int dfn[maxn];//记录每个顶点的深度优先搜索序数int low[maxn];//每个顶点的low值,根据该值来判断是否是关节点int son;//根结点的有...
一.引入二分图匹配算法是一个非常有用的算法,我们首先从一个简单的题目引入。给你n个水果,m个箱子,每个水果只能被放在指定的几个箱子里,每个盒子只能放一个水果,问如何安排能使的放在盒子里的水果最多。怎么写?暴力,可以试试。但不管是暴力还是什么算法,都需要面对一个情况——后面的水果如果没盒子放了,不能不管不顾,应该腾空间。对,腾。二分图算法的最重要思想就是腾二.算法流程二分图有两种主流算法,一个是匈牙利算...
1.Dijkstra算法(计算正权图上的单源最短路 single-source shortest paths (sssp) )从单个节点出发到所有节点的最短路。该算法适用于:有向图和无向图。1). O(n^2)的实现:邻接矩阵map存储实现,INF表示无穷大void Dijkstra(int s, int e, int n) //从s开始到e点的最短路,有n个节点,编号:0-->n-1.
{memset(vis, 0, sizeof(vis));int i, j;for(i=0; i<n; i++)dis[i]=(i==0?0:INF);for(i=0; i<n; i++){int mm=INF; int pos;for...
Sunday是一个线性字符串模式匹配算法。算法的概念如下:Sunday算法是Daniel M.Sunday于1990年提出的一种字符串模式匹配算法。其核心思想是:在匹配过程中,模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较,它在发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。记模式串为S,子串为T,长度分别为N,M。对于T,我们做一个简单而巧妙的预处理:记录T中每一种字符最后出现的位置,将其...