APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

#NOIP提高组#模板整理

2018年11月4日 1558点热度 2人点赞 1条评论

高精度运算

高精度加法:

int main() {
    scanf("%s%s",&a1,&b1);
    if(a1[0] == '0' && b1[0] == '0') {
        cout << "0";
        return 0;
    }
    for(int i = 0;i < strlen(a1);++i)
        a[strlen(a1) - i - 1] = a1[i] - '0';
    for(int i = 0;i < strlen(b1);++i)
        b[strlen(b1) - i - 1] = b1[i] - '0';
    m = max(strlen(a1),strlen(b1));
    for(int i = 0;i < m;++i)
        c[i] = a[i] + b[i];
    for (int i = 0;i <= m;++i) {
        c[i + 1] = c[i + 1] + c[i] / 10;
        c[i] = c[i] % 10;
    }
    m++;
    while(!c[m]) m--;
    for(int i = m;i >= 0;--i)
        cout << c[i];
    return 0;
}

高精度减法:
int main() {
    scanf("%s%s",&x,&y);
    int lena = strlen(x),lenb = strlen(y);
    for(int i = 0;i < lena;++i)
        a[lena - i - 1] = x[i] - '0';
    for(int i = 0;i < lenb;++i)
        b[lenb - i - 1]=y[i] - '0';
    if(lena > lenb) vis = 1;
    if(lena < lenb) vis = 0;
    if(lena == lenb) {
        string temp1 = x,temp2 = y;
        if(temp1 > temp2) vis = 1;
        if(temp1 == temp2) vis = 1;
        else vis = 0;
    }
    m = max(lena,lenb);
    if(vis) {
        for(int i = 0;i < m;++i)
        c[i]=a[i]-b[i];
    }
    else {
        for(int i = 0;i < m;++i)
        	c[i]=b[i]-a[i];
    }
    for(int i = 0;i <= m;++i) {
        if(c[i] < 0){
            c[i] += 10;
            c[i + 1]--;
        }
    }
    temp = m;
    for(int i = m;i >= 0;--i) {
        if(c[i]) break;
        temp--;
        if(i == 0 && c[i] == 0) {
            temp = 0;
            break;
        }
    }
    if(!vis) cout << "-";
    for(int i = temp;i >= 0;--i)
        cout << c[i];
    return 0;
}

高精度乘法:
int main() {
    scanf("%s%s",&x,&y);
    int lena = strlen(x),lenb = strlen(y);
    for(int i = 0;i < lena;++i)
        a[lena - i - 1] = x[i] - '0';
    for(int i = 0;i < lenb;++i)
        b[lenb - i - 1] = y[i] - '0';
    for(int i = 0;i < lena;++i)
        for(int j = 0;j < lenb;++j) {
            c[i + j] += a[i] * b[j];
            c[i + j + 1] += c[i+j] / 10;
            c[i + j] %= 10;
        }	    
    int lenc = lena + lenb;
    while(lenc > 1 && c[lenc - 1] == 0) lenc--;
    lenc--;
    for(int i = lenc;i >= 0;--i)
        cout << c[i];
    return 0;	
}

数学

快速幂:

LL power(LL a,LL b) {
    LL t = 1,y = a;
    while(b) {
        if (b & 1) t = t * y % k;
        y = y * y % k;
        b >>= 1;
	}
  return t; 
}

埃式素数判定:
bool is_prime(int x) {
	if(x == 1 || x == 0) return false;
	for(int i = 2;i * i <= x;++i)
		if(x % i == 0) return false;
	return true;
}

欧拉筛素数:
void is_prime(int list) {
    memset(vis,true,sizeof vis);
    vis[0] = vis[1] = false;
    for(int i = 2;i <= list;++i){
        if(vis[i]) prime[++tot] = i;
        for(int j = 1;j <= list && i * prime[j] <= list;++j){
           vis[i * prime[j]] = false;
           if(i % prime[j] == 0) break;
        }
    }
}

欧几里得算法:

int gcd(int a,int b) {
	if(!b) return a;
	else return gcd(b,a % b);
}

拓展欧几里得:
void ex_gcd(int &x,int &y,int a,int b) {
    if(b == 0) {
        y = 0;
        x = 1;		
    }
    else {
        ex_gcd(y,x,b,a % b);
        y -= x * (a / b);
    }
}

欧拉函数:
int euler(int n) {
    int res = n;
    for(int i = 2;i * i <= n;++i) {
        if(n % i == 0) res = res / i * (i - 1);
        while(n % i == 0) n /= i;
    }
    if(n > 1) res = res / n * (n - 1);
    return res;
}

线性筛欧拉函数:
void get_phi(int list) {
    memset(vis,true,sizeof vis);
    vis[0] = vis[1] = false;
    phi[1] = 1;
    for(int i = 2;i <= list;++i){
        if(vis[i]) prime[++tot] = i,phi[i] = i - 1;
        for(int j = 1;j <= list && i * prime[j] <= list;++j){
           vis[i * prime[j]] = false;
           if(i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1);
           else {
           		phi[i * prime[j]] = phi[i] * prime[j];
           		break;
			}
        }
        //phi[i] += phi[i - 1]; 
    }
}

矩阵运算:
inline Mat Mul(Mat a,Mat b){
    Mat tmp;
    tmp.clear();
    for(int i = 1;i <= n;++i)
        for(int j = 1;j <= n;++j)
            for(int k = 1;k <= n;++k)
               tmp.a[i][j] = (tmp.a[i][j] + (a.a[i][k] * b.a[k][j]) % MOD) % MOD;
    return tmp;
}
inline Mat power(Mat a,long long b){
	Mat ans;
	ans.clear();
    for(int i = 1;i <= n;++i)
            ans.a[i][i]=1;
    while(b){
        if (b & 1) ans = Mul(ans,a);
        a = Mul(a,a);
        b >>= 1;
    }
    return ans;
} 
 
inline Mat Add(Mat T_1,Mat T_2) {
	Mat Tmp;
	Tmp.clear();
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= n;++j)
			Tmp.a[i][j] = T_1.a[i][j] + T_2.a[i][j],Tmp.a[i][j] %= MOD;
	return Tmp;
}

图论

SPFA算法:

void Spfa() {
	queue <int > Q;
	Q.push(s);
	vis[s] = true;
	memset(dis,0x3f,sizeof dis);
	dis[s] = 0;
	while(!Q.empty()) {
		int u = Q.front();
		Q.pop();
		vis[u] = false;
		for(int i = head[u];i;i = e[i].nxt) {
			int v = e[i].to;
			if(dis[v] > dis[u] + e[i].dis) {
				dis[v] = dis[u] + e[i].dis;
				if(!vis[v]) {
					Q.push(v);
					vis[v] = true;
				}
			}
		}
	}
}

Dijkstra算法:
void Dijkstra() {
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0;
    priority_queue <pair <int ,int >,vector <pair <int ,int > >,greater <pair <int ,int > > > Q;
    Q.push(make_pair(0,s));
    while(!Q.empty()) {
        int u = Q.top().second;
        Q.pop();
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u];i;i = e[i].nxt) {
            int v = e[i].to;
            if(dis[v] > dis[u] + e[i].dis) {
                dis[v] = dis[u] + e[i].dis;
                if(!vis[v]) Q.push(make_pair(dis[v],v));
            }
        }
    }
}

最短路计数:
void Dijkstra_Heap() {
	priority_queue <pair <int ,int > ,vector <pair <int ,int > >,greater <pair <int ,int > > > Q;
	memset(dis,0x3f,sizeof dis);
	dis[s] = 0;
	ans[1] = 1;
	Q.push(make_pair(0,s));
	while(!Q.empty()) {
		int u = Q.top().second;
		Q.pop();
		if(vis[u]) continue;
		vis[u] = true;
		for(int i = head[u];i;i = e[i].nxt) {
			int v = e[i].to;
			if(dis[v] > dis[u] + 1) {
				dis[v] = dis[u] + 1;
				ans[v] = ans[u];
				if(!vis[v]) Q.push(make_pair(dis[v],v));
			}
			else if(dis[v] == dis[u] + 1) {
				ans[v] += ans[u];
				ans[v] %= MOD;
			}
		}
	}
}

负环:
bool spfa() {
    queue <int > Q;
    memset(&vis,false,sizeof vis);
    memset(&num,0,sizeof num);
    memset(&dis,0,sizeof dis);
    memset(&head,0,sizeof head);
    memset(&e,0,sizeof e);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;++i) {
        int f,t,d;
        scanf("%d%d%d",&f,&t,&d);
        if(d < 0) {
        	add(f,t,d);	
        }
        else {
        	add(f,t,d);
        	add(t,f,d);
        }
    }
    memset(dis,0x3f,sizeof dis);
    dis[1] = 0;
    Q.push(1);
    vis[1] = true;
    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();
        vis[u] = false;
        for(int i = head[u];i;i = e[i].nxt) {
            int v = e[i].to;
            if(dis[v] > dis[u] + e[i].dis) {
                dis[v] = dis[u] + e[i].dis;
                num[v] = num[u] + 1;
                if(num[v] >= n) return true;
                if(!vis[v]) {
                    Q.push(v);
                    vis[v] = true; 
                }
            } 
        }
    }
    return false;
}

Tarjan割点:
void Tarjan(int u,int fa) {
    dfn[u] = low[u] = ++cmt;
    int child = 0;
    for(int i = head[u];i;i = e[i].next) {
        int v = e[i].to;
        if(!dfn[v]) {
            Tarjan(v,fa);
            low[u] = min(low[u],low[v]);
            if(low[v] >= dfn[u] && u != fa) cut[u] = true;
            if(u == fa) child++;
        }
        else low[u] = min(low[u],dfn[v]);
    }
    if(u == fa && child >= 2) cut[fa]=true;
}

Tarjan强连通分量(缩点):

匈牙利算法:

bool dfs(int u) {
	for(int i = head[u];i;i = e[i].next) {
		int v = e[i].to;
		if(!used[v]) {
			used[v] = true;
			if(!Matched[v] || dfs(Matched[v])) {
				Matched[v] = u;
				return true;
			}
		}
	}
	return false;
}

倍增LCA:
inline void dfs(int now,int f) {
    deepth[now] = deepth[f] + 1;
    fa[now][0] = f;
    for(int i = 1;(1 << i) <= deepth[now];++i) fa[now][i] = fa[fa[now][i - 1]][i - 1];
    for(int i = head[now];i;i = e[i].next) {
        int v = e[i].to;
        if(v != f) dfs(v,now);
    }
}

inline int get_lca(int x,int y) {
    if(deepth[x] < deepth[y]) swap(x,y);
    while(deepth[x] > deepth[y]) x = fa[x][lg[deepth[x] - deepth[y]] - 1];
    if(x == y) return x;
    for(int k = lg[deepth[x]];k >= 0;--k) if(fa[x][k] != fa[y][k]) x = fa[x][k],y = fa[y][k];
    return fa[x][0];
    
}

inline void Init() {
    for(int i = 1;i <= n;++i) lg[i] = lg[i >> 1] + 1;
}

Kruskal算法:
int find(int x){
    if(fa[x] != x) fa[x] = find(fa[x]);
    return fa[x];
}

bool cmp(node a,node b){
    return a.w < b.w; 
}

void Kruskal() {
	for(int i = 1;i <= n;i++)
        fa[i] = i;
    sort(a + 1,a + 1 + m,cmp);
    for(int i = 1;i <= m;++i){
        int fx = find(a[i].x);
		int fy = find(a[i].y);
        if(rand() & 1) swap(fx,fy);
        if(fx == fy) continue;
        ans += a[i].w;
        fa[fy] = fx;
        cnt++;
        if(cnt == n - 1) break;
    }
}

Prim算法:
void Prim_Heap(int s) {
    memset(dis,0x3f,sizeof dis);
    memset(vis,false,sizeof vis);
    priority_queue <pair <int ,int >, vector < pair <int ,int > >, greater < pair <int ,int > > > Q;
    dis[s] = 0;
    Q.push(make_pair(0,s));
    while(!Q.empty()) {
        int u = Q.top().second;
        int d = Q.top().first;
        Q.pop();
        if(vis[u]) continue;
        num++;
        sum += d; 
        vis[u] = true;
        for(int i = head[u];i;i = e[i].next) {
            int v = e[i].to;
            if(dis[v] > e[i].dis) {
                dis[v] = e[i].dis;
                Q.push(make_pair(dis[v],v));
            }
        }
    }
}

数据结构

一维树状数组:

void add(int x,int t) {
	while(x <= n) {
		v[x] += t;
		x += lowbit(x);	
	}
}
 
int query(int x) {
	int res = 0;
	while(x) {
		res += v[x];
		x -= lowbit(x);
	}
	return res;
}

二维树状数组:
void add(int x,int y,int t) {
	while(x <= n) {
		for(int k = y;k <= m;k += lowbit(k))
			v[x][k] += t;
		x += lowbit(x);
	}
}
 
int query(int x,int y) {
	int res = 0;
	while(x) {
		for(int k = y;k;k -= lowbit(k))
			res += v[x][k];
		x -= lowbit(x);
	}
	return res;
}

线段树1(单点修改,区间查询):
void push_up(LL k) {
    tree[k] = tree[ls(k)] + tree[rs(k)];
}

inline void f(LL k,LL l,LL r,LL p) {
    tag[k] += p;
    tree[k] += p * (r - l + 1);
}

void push_down(LL k,LL l,LL r) {
    LL mid = (l + r) >> 1;
    f(ls(k),l,mid,tag[k]);
    f(rs(k),mid + 1,r,tag[k]);
    tag[k] = 0; 
}

void build(LL k,LL l,LL r) {
    tag[k] = 0;
    if(l == r) {
        tree[k] = a[l];
        return ;
    }
    LL mid = (l + r) >> 1;
    build(ls(k),l,mid);
    build(rs(k),mid + 1,r);
    push_up(k);
}

void update(LL k,LL l,LL r,LL x,LL y,LL p) {
    if(y < l || x > r) return ;
    if(x <= l && y >= r) {
        tree[k] += p * (r - l + 1);
        tag[k] += p;
        return ;
    }
    push_down(k,l,r);
    LL mid = (l + r) >> 1;
    if(x <= mid) update(ls(k),l,mid,x,y,p);
    if(y > mid) update(rs(k),mid + 1,r,x,y,p);
    push_up(k);
}

LL Query(LL k,LL l,LL r,LL x,LL y) {
    LL res = 0;
    if(y < l || x > r) return 0;
    if(x <= l && y >= r) return tree[k];
    LL mid = (l + r) >> 1;
    push_down(k,l,r);
    if(x <= mid) res += Query(ls(k),l,mid,x,y);
    if(y > mid) res += Query(rs(k),mid + 1,r,x,y);
    return res;
}

线段树2(单点修改,区间查询):
void push_up(LL k) {
    tree[k] = tree[ls(k)] + tree[rs(k)];
    tree[k] %= MOD;
}

inline void f(LL k,LL l,LL r,LL p) {
    tree[k] += p * (r - l + 1);
    tree[k] %= MOD;
    tag[k] += p;
    tag[k] %= MOD; 
}

void f_2(LL k,LL l,LL r,LL p) {
    tree[k] *= p;
    tree[k] %= MOD;
    tag[k] *= p;
    tag[k] %= MOD;
    tag2[k] *= p;
    tag2[k] %= MOD;
}

void push_down(LL k,LL l,LL r) {
    LL mid = (l + r) >> 1;
    if(tag2[k] != 1) {
        f_2(ls(k),l,mid,tag2[k]);
        f_2(rs(k),mid + 1,r,tag2[k]);
        tag2[k] = 1;
    }
    if(tag[k]) {
        f(ls(k),l,mid,tag[k]);
        f(rs(k),mid + 1,r,tag[k]);
        tag[k] = 0;
    }
}

void build(LL k,LL l,LL r) {
    tag[k] = 0;
    tag2[k] = 1;
    if(l == r) {
        tree[k] = a[l];
        return ;
    }
    LL mid = (l + r) >> 1;
    build(ls(k),l,mid);
    build(rs(k),mid + 1,r);
    push_up(k);
}

void Update_Add(LL k,LL l,LL r,LL x,LL y,LL p) {
    if(y < l or x > r) return ;
    if(l >= x and r <= y) {
        tag[k] += p;
        tag[k] %= MOD;
        tree[k] += p * (r - l + 1);
        tree[k] %= MOD;
        return ;
    }
    push_down(k,l,r);
    LL mid = (l + r) >> 1;
    if(x <= mid) Update_Add(ls(k),l,mid,x,y,p);
    if(y > mid) Update_Add(rs(k),mid + 1,r,x,y,p);
    push_up(k);
} 

LL Query(LL k,LL l,LL r,LL x,LL y) {
    if(y < l or x > r) return 0;
    if(l >= x and r <= y) return tree[k];
    push_down(k,l,r);
    LL mid = (l + r) >> 1;
    LL res = 0;
    if(x <= mid) res = (res + Query(ls(k),l,mid,x,y)) % MOD;
    if(y > mid) res = (res + Query(rs(k),mid + 1,r,x,y)) % MOD;
    return res % MOD;	
}

void Update_Cheng(LL k,LL l,LL r,LL x,LL y,LL p) {
    if(y < l or x > r) return ;
    if(l >= x and r <= y) {
        tag[k] *= p;
        tag[k] %= MOD;
        tree[k] *= p;
        tree[k] %= MOD;
        tag2[k] *= p;
        tag2[k] %= MOD;
        return ;
    }
    push_down(k,l,r);
    LL mid = (l + r) >> 1;
    if(x <= mid) Update_Cheng(ls(k),l,mid,x,y,p);
    if(y > mid) Update_Cheng(rs(k),mid + 1,r,x,y,p);
    push_up(k); 
}

ST表:
void Init() {
	lg[0] = -1;
	for(int i = 1;i <= n;++i) lg[i] = lg[i >> 1] + 1;
    for(int i = 1;i <= n;++i) scanf("%d",&Max[i][0]);
    for(int i = 1;i <= n;++i) Min[i][0] = Max[i][0];
    for(int j = 1;j <= 21;++j)
        for(int i = 1;i + (1 << j) - 1 <= n;++i) {
            Max[i][j] = max(Max[i][j - 1],Max[i + (1 << (j - 1))][j - 1]);
            Min[i][j] = min(Min[i][j - 1],Min[i + (1 << (j - 1))][j - 1]);
        }
}

int QueryMax(int l,int r) {
    int k = lg[r - l + 1];
    return max(Max[l][k],Max[r - (1 << k) + 1][k]);
}

int QueryMin(int l,int r) {
    int k = lg[r - l + 1];
    return min(Min[l][k],Min[r - (1 << k) + 1][k]);
}

并查集:
void Init() {
	for(int i = 1;i <= n;++i) father[i] = i;
}

int Find(int x) {
	if(x != father[x]) father[x] = Find(father[x]);
	return father[x];
}

分块:以后会整理分块入门1-9

字符串算法:

Manacher算法:

int Init() {  //初始化并返回new_s长度 
	int len = strlen(s);
	new_s[0] = '$';
	new_s[1] = '#';
	int j = 2;
	for(int i = 0; i < len;++i) {
		new_s[j++] = s[i];
		new_s[j++] = '#';
	}
	new_s[j] = '\0';
	return j;
}
 
int Manacher() {
	int len = Init();
	int max_len = -1;
	int id = 0,mx = 0; 
	for(int i = 1;i < len;++i) {
		if(i < mx) p[i] = min(p[2 * id - i],mx - i); // 2 * id - i指i关于id的对称点j
		else p[i] = 1;
		while(new_s[i - p[i]] == new_s[i + p[i]]) p[i]++;
		if(mx < i + p[i]) {
			id = i;
			mx = i + p[i];
		}
		max_len = max(max_len,p[i] - 1);
	}
	return max_len;
}

KMP算法:

void kmp1() {
    int j = 0;
    for(int i = 2;i <= lenb;++i) {
        while(j && b[j + 1] != b[i]) j = next[j];
        if(b[j + 1] == b[i]) j++;
        next[i] = j;
    }
}

void kmp2() {
    int j = 0;
    for(int i = 1;i <= lena;++i) {
        while(j && b[j + 1] != a[i]) j = next[j];
        if(b[j + 1] == a[i]) j++;
        if(j == lenb) {
            cout << i - lenb + 1 <<endl;
            j = next[j];
        }
    }
}

Hash:
const int Base = 131;
const int Prime = 19260817;
const LL MOD = 212370440130137957ll;

LL hash(char s[]) {
    int len = strlen(s);
    LL cnt = 0;
    for(int i = 0;i < len;++i)
        cnt = (cnt * Base + (LL)s[i]) % MOD + Prime;
    return cnt;
}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: DFS Dijkstra Hash Manacher NOIP OI Prim ST ST表 Tarjan 匈牙利算法 图论 字符串 并查集 强连通分量 快速幂 拓展欧几里得 数据结构 最短路 树 树状数组 模板 欧几里得 矩阵 算法
最后更新:2018年12月15日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇

文章评论

  • qinghuan

    lz可以加个qq沟通交流一下吗pwp

    2018年12月4日
    回复
  • razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
    取消回复

    神楽坂 みずき

    萌萌萌,好萌!

    搜索
    最新 热点 随机
    最新 热点 随机
    站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
    #动画#《多田君不恋爱》观后感:内心永远是彩虹色! C/C++Manacher算法(字符串判断回文串) 马拉车算法 模板 #C/C++#数据结构:树状数组/线段树/并查集/树链剖分 #C/C++#二分图匹配匈牙利算法模板(邻接表/邻接矩阵) WPscan扫描Wordpress漏洞的工具使用教程 Linux中zip/unzip命令简略笔记
    标签聚合
    ST 动漫 日常 洛谷 C/C++ OI C++ HTML
    分类
    • ACGN
    • Coding
    • Daily
    • DevOps
    • OI
    • Share

    COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

    Theme Kratos Made By Seaton Jiang