树状数组

树状数组

A[i]数组进行前前缀和的维护的时更新成了一个大难题,树状数组提供O(logn)的复杂度更新速度。C[i]所能管理的A[i]数字如下图所示,如果查询7的前缀和,则需要计算C[7] + C[6] + C[4]

Read more

排序总结

交换类?

选择排序

不具有稳定性,复杂度稳定在O(n2)O(n2)。

存在不同元素大范围交换,所以不稳定。

int main(){
    // freopen("./data.in", "r", stdin);
    int c[6] = {5, 3, 2, 1, 7, 2}, n = 6;
    for(int i = 0; i < n; i++){
		int mp = i;
        for(int j = i + 1; j < n; j++){
            if(c[j] < c[mp]){
				mp = j;
			}
        }
        int temp = c[mp];
        c[mp] = c[i];
        c[i] = temp;
    }
    for(int i=0; i < n; i++){
        printf("%d ", c[i]);
    }
    printf("\n");
    return 0;
}

冒泡排序

具有稳定性,复杂度为O(n)O(n)到O(n2)O(n2)。

int main(){
    // freopen("./data.in", "r", stdin);
    int c[6] = {5, 3, 2, 1, 7, 2}, n = 6;
    for(int i=0; i < n-1; i++){
        int flag = 0;
        for(int j=0; j < n - 1 - i; j++){
            if(c[j] > c[j+1]){
                int temp = c[j];
                c[j] = c[j + 1];
                c[j + 1 ] = temp;
                flag = 1;
            }
        }
        if(!flag) break;
    }
    for(int i=0; i < n; i++){
        printf("%d ", c[i]);
    }
    printf("\n");
    return 0;
}

??

插入排序

具有稳定性,复杂度为O(n)O(n)到O(n2)O(n2)。

int main(){
    // freopen("./data.in", "r", stdin);
    int c[6] = {5, 3, 2, 1, 7, 2}, n = 6;
    for(int i = 1; i < n; i++){
        int j = i, t = c[j];
        while(j > 0 && t < c[j - 1]){
            c[j] = c[j - 1];
            j--;
        }
        c[j] = t;
    }
    for(int i=0; i < n; i++){
        printf("%d ", c[i]);
    }
    printf("\n");
    return 0;
}

归并排序

稳定,复杂度为O(nlgn)O(nlgn)。

int printArr(int A[], int r, int l){
    for(int i=r; i < l + 1; i++){
        printf("%d ", A[i]);
    }
    printf("\n");

}

const int maxn  = 100;
int merge(int arr[], int l1, int r1, int l2, int r2){
	int i = l1, j = l2, k = 0;
	int temp[maxn];
	while(i <= r1 && j <= r2){
		if(arr[i] < arr[j])
			temp[k++] = arr[i++]; 
		else if(arr[i] >= arr[j])
			temp[k++] = arr[j++];
	}
	while(i <= r1)
    	temp[k++] = arr[i++]; 
	while(j <= r2)
    	temp[k++] = arr[j++]; 
    for(int i = l1, k = 0; i <= r2; i++, k++) arr[i] = temp[k];
}

//递归写法
int mergeSort_re(int A[], int l, int r){
	if(l < r){
		int mid = (l + r) / 2;
		mergeSort_re(A, l, mid);
		mergeSort_re(A, mid + 1, r);
		merge(A, l, mid, mid + 1, r);
	}
}
// 迭代写法
int mergeSort_for(int A[], int l, int r){
	if(l < r){
		int n = r - l + 1;
		//step为组内元素个数
		for(int step = 1; step <= n; step *= 2){
			for(int i = 0; i < n; i += 2*step){
				//这么写行不行?测试一下A[5]
				// 事实证明这种写法很优美!
				merge(&A[l], i, i + step - 1, i + step, min(i + 2 * step - 1, n - 1));
			}
		    printArr(A, l, r);
        }
        
	}

}
int main(){
    // freopen("./data.in", "r", stdin);
    int c[10] = {5, 3, 2, 1, 7, 2, 10, 3, 5, -1}, n = 10;
    
    // mergeSort_re(c, 0, n - 1);
    mergeSort_for(c, 5, n - 1);
    
    printArr(c, 0, n - 1);
    return 0;
}

快速排序

不稳定,复杂度为O(nlgn)O(nlgn)到O(n2)O(n2),最广泛使用的排序算法。

//挖沙法 分割
int Partition(int A[], int l, int r){
	//三个数取最小值
    int minp = l;
    if(A[r] < A[minp]) minp = r;
    if(A[(r + l) / 2] < A[minp]) minp = (r + l) / 2;
    int temp = A[minp];
    A[minp] = A[l];
    A[l] = temp;
    int i = l, j = r;
    while(i < j){
        while(i < j && temp < A[j]) j--;
        A[i] = A[j];
        while(i < j && temp >= A[i]) i++;
        A[j] = A[i];
    }
    A[j] = temp;
    return j;
}
void quickSort(int A[], int l, int r){
    if(l >= r) return;
    int mid = partition(A, l, r);
        printArr(A, 0, 9);
        printf("%d\n", mid);
    quickSort(A, l, mid - 1); // 如果这里取mid - 1, 可能会导致mid为右侧最小值的情况时,无限partition!(没错,微妙的递归)
    quickSort(A, mid + 1, r);

}

快速幂

快速幂算法,也称二分幂。 递归写法:

typedef long long ll;
ll binaryPow(ll a, ll b, ll m){
	if(b == 0) return 1;
	if(b & 1) return a * binaryPow(a, b - 1, m) % m;
	else{
		ll mul = binaryPow(a, b / 2, m);
		return mul * mul % m;
	}
}

迭代写法:

typedef long long ll;
ll binaryPow(ll a, ll b, ll m){
	ll res = 1, pow = a;
	while(b){
		if(b & 1)
			res = res * pow % m; //注意这两个地方的取余
		pow = pow * pow % m; 
		b >> 1;
	}
	return res;
}

双指针法

双指针算法作为编程中的一种思想,利用了数据有序性,有效减少了算法复杂度。比如在两数之和的题目,可达到O(n)O(n)复杂度,而非O(n2)O(n2)。在序列递增的数组中找两个数之和为aim。

  • 对于a[i]+a[j]==Ma[i]+a[j]==M, 结果成立;
  • 对于a[i]+a[j]<Ma[i]+a[j]<M,则有a[i−1]+a[j]<Ma[i−1]+a[j]<M成立,但是a[i+1]+a[j]a[i+1]+a[j]大小未知。尝试ii向上移动
  • 对于a[i]+a[j]>Ma[i]+a[j]>M,则有a[i]+a[j+1]>Ma[i]+a[j+1]>M成立,但是a[i]+a[j−1]a[i]+a[j−1]大小未知。尝试jj向上移动

上面的算法推导有一个不太严谨的地方:没有证明[0,i−1]和[j+1,n−1][0,i−1]和[j+1,n−1]之间的元素的任何搭配不成立。

诶好像可以用归纳法!

int aim, i = 0, j = n - 1;
while(i<j){
	int sum = arr[i] + arr[j];
	if(sum ==aim){
		pirntf("%d,%d\n", arr[i], arr[j]);
		i++; j--;
	}
	if(sum < aim){
		i++
	}else j--; 
}

其他例子,如两个数列合并的双指针例子。

最大公约数——欧几里得算法

欧几里得算法又称碾转相除法,其算法基于以下定理:

gcd(a,b)=gcd(b,agcd(a,b)=gcd(b,a

其中gcd(a, b)表示a除于b的余数。

int gcd(int a, int b){
    return b? gcd(b, a % b) : a;

}

素数

用素数性质简单判断

bool isPrime(int n){
    if(n <= 1) return false;
    int sqr = (int)sqrt(1.0 * n);
    for(int i = 2; i <= sqr; i++)
        if(n % i == 0) return false;
    return true;
}

打素数表

经典的埃氏筛法

const int maxn = 1e5;
int prime[maxn], pNum = 0;

void findPrime(){
    for(int i = 2; i < maxn; i++){
        if(prime[i] == 0){
            prime[pNum++] = i;
            for(int j = i * 2; j < maxn; j += i)
                prime[j] = 1;
            printf("%d\n", i);
        } 
    }

}

素数表的经典应用就是分解质因子,在有了素数表的情况下分解一个数字的因子的复杂度为O(n−−√)O(n)

中缀式计算

中缀表示式计算分为两个步骤,一是中缀转后缀,二是后缀表达式计算;

#include<string>
#include<cstdio>
#include<iostream>
#include<queue>
#include<stack>
#include<map>
using namespace std;

stack<char> stop; // 符号栈
map<char, int> opp; // 运算符 映射到优先级 the priority of operators
stack<double> stn;// 数字栈

string mid2Post(string s){
	string res;
	for(int i = 0; i < s.size(); i++){
		if(isdigit(s[i]) || s[i] == '.') res += s[i];
		else{
            if(s[i] == ' ') continue; //去空格
			if(s[i] == '(') stop.push(s[i]);
			else if(s[i] == ')'){
				while(stop.top() != '('){
					res += stop.top();
					stop.pop();
				}

				stop.pop();
			}else{
				int pro = opp[s[i]];
				//为运算符两旁数字插入空格,否则无法区分数字
				res += ' ';
				//pop出运算优先级高的运算操作符
				while( !stop.empty() && pro <= opp[stop.top()]){ //注意这里stack要有数据,
					res += stop.top();
					stop.pop();
				}
				stop.push(s[i]);
			}
		}
	}
    
	while(!stop.empty()){
		res += stop.top();
		stop.pop();
	}
	return res;
}

// 获取正数(可有小数点)
double getNum(string &str, int &pos){
	int k = pos, flag = 1;// flag = 1表计算正整数
	double inter = 0, fac = 0, pow10 = 10;
	while(isdigit(str[k]) || str[k] == '.'){
	 	if( str[k] == '.') flag = 0;  
		else if(flag == 1){	//计算正整数
			inter = inter * 10 + (double)(str[k] - '0'); //地址?
		}else{	// 计算小数
			fac += (double)(str[k]-'0') / pow10;
			pow10 *= 10;
		}
		k++;
	 	if(k >= str.size() ) break;
	}
	pos = k;
	return inter + fac;
}


//计算后缀表达式的值
double calPost(string pStr){
	if(pStr.size() == 0) return 0;
	for(int i = 0; i < pStr.size(); i++){
		if(isdigit(pStr[i])){ //对于数字
			double t = getNum(pStr, i);
			i--; //多加了一次i
			printf("%f\n", t);
			stn.push(t);			
		}else if(pStr[i] == '+' || pStr[i] == '-' ||
			pStr[i] == '*' || pStr[i] == '/') { // 对于运算符(不包括小数,理论上规范的格式中应该被数据包裹着)
			double op2 = stn.top(); stn.pop(); //注意压栈后 数据顺序是反的
             double op1 = stn.top(); stn.pop();
    		if(pStr[i] == '+') stn.push(op1 + op2);
    		else if(pStr[i] == '-') stn.push(op1 - op2);
    		else if(pStr[i] == '*') stn.push(op1 * op2);
    		else if(pStr[i] == '/') stn.push(op1 / op2); //不做非零判断了

		}
	}
	if( stn.size() != 1){
		printf("error! the size of stck of num isn't 1.\n");
		return -1;
	} 
	return stn.top();
}
int main(){
    //freopen("data.in", "r", stdin);
	string str;
	getline(cin, str);
    cout << str << endl;
	opp['+'] = opp['-'] = 1;
    opp['/'] = opp['*'] = 2;
	opp['('] = 0; //'(' 特殊处理
    string pStr = mid2Post(str);
    cout << pStr << endl;
    double calRes = calPost(pStr);
    printf("%.2lf\n", calRes);
}

细节上也可以再改动,比如在识别数字的时候就把它提取出来并用结构体的形式存储下来。

拓扑排序



/** This is Code of JJ

Problem      :拓扑排序
Source       :
Solution     :
AnyDetial    :

DateAndTime  :2.26
CostofTime   :

**/
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
using namespace std;

const int N = 1e3;

vector<int>adj[N];
int indegree[N],dvis[N];

int n,m;

vector<int>res;

bool topu()
{
    int sortnum = 0;
    queue<int>q;
    for(int i=0;i<n;i++)
    {
        if(indegree[i]==0)
            q.push(i);
    }
    while(!q.empty())
    {
        int u = q.front();
        cout<< u << endl;
        q.pop();

        for(int j=0;j<adj[u].size();j++)
        {
            int k = adj[u][j];
            indegree[k]--;
            if(indegree[k]==0)
            {
                q.push(k);
            }
        }
        sortnum++;
    }

    if(sortnum==n) return true;
    else return false;
}


//dfs 逆序输出拓扑排序
stack<int> s;
int vis[N];
void dfs(int u){
    vis[u] = 1;
    for(int i=0;i<adj[u].size();i++){
        int v = adj[u][i];
        if(!vis[v]){
            dfs(v);
        }
    }
    s.push(u);
    cout<<u<<endl;
}
int main()
{
    scanf("%d%d",&n,&m);

    int c1, c2, w;
    for(int j=0;j<m;j++)
    {
        scanf("%d%d",&c1,&c2);
        adj[c1].push_back(c2);
        indegree[c2] ++;

    }
    topu();
}
/*

5 5
0 1
1 3
3 4
0 2
2 4
*/w

最短路


#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int INF = 0x3ffffff;
const int MX = 500;
int n, m, l, cap, s, t;
int dis[MX], vis[MX], bvis[MX], edge[MX][MX], fushe[MX];
int bec = -1    , becfu = INF, allp;
double rate = 1;
vector<int> path[MX], bepath, nwpath;
int disjk(){
    fill(dis,dis + MX, INF);
    dis[s] = 0;
    for(int i = 0;i < n;i++){
        int u = -1, minv =  INF;
        for(int j = 0;j < n; j++){
            if(!vis[j] && dis[j] < minv){
                minv = dis[j];
                u  = j;
            }
        }
        if(u == -1 ) break;
        vis[u] = 1;
        for(int v = 0; v < n;v++){
            if( edge[u][v] != INF && !vis[v]){//! vis[v] == 0 必须成立, 根据Dijkstra算法不能放缩已经标记过的节点
                                            //! 但是之前已经放缩的节点是绝对不会再被放缩的。。因为无负权
//            if( edge[u][v] != INF ){//! vis[v] == 0 必须成立, 根据Dijkstra算法不能放缩已经标记过的节点
                if(!vis[v] && dis[v] > dis[u] + edge[u][v] ){
                    dis[v] = dis[u] + edge[u][v];
                    path[v].clear();
                    path[v].push_back(u);
                }else if( dis[v] ==  dis[u] + edge[u][v]){
                    path[v].push_back(u);
                }
//            }

        }
    }
}

int bfs(){
    queue<int> que, lay;
    que.push(s);
    lay.push(0);
    bvis[s] = 1;
    while(que.size()){
        int u = que.front(), layer = lay.front(); que.pop(), lay.pop();
        if(layer < l)
            fushe[u] += (int)(ceil(1.0 * fushe[u] * (l - layer) / l));
        for(int i = 0; i < n;i++)
            if(edge[u][i] != INF && !bvis[i]){//!
                que.push(i);
                bvis[i] = 1;
                lay.push( layer + 1);
            }
    }
}
int dfs(int u){
    nwpath.push_back(u);
    if(u == s){
        allp ++;
        int npc = 0, npfushe = 0;
        for(int i = 0;i < nwpath.size(); i++){
            npc += fushe[nwpath[i]];
            if(i < nwpath.size() / 2) npfushe += fushe[nwpath[i]];
        }
        npc = npc % cap;
        if(npc > bec || npc == bec && npfushe < becfu){ //! npc >= bec
            bepath = nwpath;
            bec = npc;
            becfu = npfushe;
        }
    }else{
        for(int i = 0;i < path[u].size(); i++)
            dfs(path[u][i]);
    }
    nwpath.pop_back();
}

 int main(){
    fill(edge[0], edge[0] + MX * MX , INF);//! init
    int c1, c2, tmp;
    cin >> n >> m >> l >> cap >> s >> t;
    for(int i = 0;i < n;i ++) cin >> fushe[i] ;
    for(int i = 0; i < m;i++){
        scanf("%d%d%d",&c1, &c2, &tmp);
        edge[c1][c2] = edge[c2][c1] = tmp;
    }
    bfs();
    disjk();
    dfs(t);
    if( !bvis[t]) printf("-1\n");
    else{
        printf("%d %d %d %d\n", allp, dis[t], bec, becfu);
        reverse(bepath.begin(), bepath.end());
//        if(bepath.size()) printf("%d", bepath[0]);//! runtime error
        for(int i = 0;i < bepath.size(); i++)
            if(i + 1 == bepath.size()) printf("%d", bepath[i]);
            else  printf("%d->", bepath[i]);
    }
    return 0;
}

关键路径

​ ```

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
const int mss = 1e3 + 100;
const int INF = 0x3fffffff;
int edge[mss][mss], n, m;
int ve[mss], vl[mss], e[mss][mss], l[mss][mss];
int ingree[mss], maxtime;
stack<int> stk;
vector<int> activity[mss], tempp;
int topu(){
    queue<int> que;
    for(int i = 1;i <= n;i++)
        if(ingree[i] == 0) que.push(i);
    while(que.size()){
        int u = que.front(); que.pop();
        stk.push(u);
        for(int i = 1; i <= n;i++){
            if(edge[u][i] != INF){
                ingree[i] --;
                if(ingree[i] == 0) que.push(i);
                ve[i] = max(ve[i], ve[u] + edge[u][i]);// 拓扑排序兵同时计算 每个节点的最早开始时间
//                cout << ve[u] << endl;
            }
        }
    }
    if(stk.size() == n) return true;
    else return false;
}
int critical_path(){
    //初始化汇点
    int maxv = 0;
    for(int i = 1;i <= n; i++)
        if( maxv < ve[i]) maxv =  ve[i];
    for(int i = 1;i <= n; i++)
        vl[i] = maxv;
    maxtime = maxv;
    //逆拓扑排序地计算每个节点的最晚开始时间
    while(stk.size()){
        int u = stk.top(); stk.pop();
        for(int i = 1;i <= n;i++){
            if(edge[u][i] != INF)
                vl[u] = min( vl[u], vl[i] - edge[u][i]);
        }
    }
    // 查找关键路径
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= n;j ++){
            if(edge[i][j] != INF){
                e[i][j] = ve[i];
                l[i][j] = vl[j] - edge[i][j];
                if(e[i][j] == l[i][j]){//插入path 以便查询所关键路径
                    activity[i].push_back(j);
                }
            }
        }
    }
    //排序以保证按序输出
    for(int i = 0;i <= n; i++){
        sort(activity[i].begin(), activity[i].end());
    }
}
int dfs(int u){//输出所有关键路径
    tempp.push_back(u);
//    cout << u << endl;
    if(activity[u].size() == 0){
        for(int i =0 ;i < tempp.size() ;i++){
            cout << tempp[i];
            if(i + 1 != tempp.size()) cout << "->";
            else cout << "\n";
        }
    }else {
        for(int i = 0;i < activity[u].size(); i++)
            dfs( activity[u][i]);
    }
    tempp.pop_back();
}
int main(){
    fill(edge[0], edge[0] + mss * mss, INF);
    int u, v, w;
    cin >> n >> m;
    for(int i = 0;i < m;i++){
        cin >> u >> v >> w;
        edge[u][v] = w;
        ingree[v]++;
    }
    if(!topu()){
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    critical_path();
    int q;
    cin >> q;
    for(int i = 0;i < q;i++){
        cin >> u >> v;
        cout << e[u][v] << ' ' << l[u][v] << endl;
    }
    cout << maxtime << endl;
    for(int i = 1;i <= n;i++)
        if( activity[i].size() && ve[i] == 0) dfs(i); //一个关键路径的起点的后序存在节点的 且最早开始时间为0
}

字符串hash

滚动哈希:O(n+m)时间内完成字符串匹配;
实现:选取两个台适的互素数$b$和h(l<b<h),假设字符串 C=clc2c3…CmC=clc2c3…Cm,定义哈希函数:
$$
H(C)=(C_1b_{m−1}+C_2b_{m−2}+⋯+C_mb_0)
$$

其中b是基数。

可以得出O(n)的时间复杂度就可以计算得到一个串的Hash值。而由取余性质

$$
(A+B)
$$

以滚动计算hash值,可实现以复杂度O(1)O(1)计算每个母串的长度为nn子串的hash值。最后再O(n+m)时间内完成字符串匹配。在实现时,可以使用64位无符号整数计算哈希值,并取M等于264264,通过自然溢出省去求模运算。

typedef unsigned long long ull;
const ull b=100000007;//哈希的基数;
//C是否在S中出现
bool contain(string C,string S)
{
     int m = C.length(), n = S.length();
     if(m > n)  return false;
     //计算b的m次方
     ull t=1;
     for(int i = 0;i < m; i++)   t *= b;
 
     //计算C和S长度为m的前缀对应的哈希值
     ull Chash=0, Shash=0;
     for(int i = 0;i < m; i++)   Chash = Chash * b + C[i];
     for(int i = 0; i < m; i++)   Shash = Shash * b + S[i];
 
     //对S不断右移一位,更新哈希值并判断
     for(int i = 0; i + m < n; i++){
          if(Chash == Shash)  return true;//S从位置i开始长度为m的字符串子串等于C;
          Shash = Shash * b - S[i] * t + S[i+m];
      }
      return false;
}

LCA问题

LCA问题即最近公共祖先问题

常见解法有递归法,向上