526互联

A+B problem，但是全模板

发布时间 2023-09-13 21:49:01作者: TimelessWelkin

0）前言

在食用此博客前，你需要知道 A+B problem 是什么。

众所周知，A+B problem 是世界上最难的题。所以……我们需要使用各种方法来解决这个难题。

题面：输入两个数 \(1 \leq a,b \leq 10^9\)，输出两数之和。

1）正片开始

一：普通の做法

#include<bits/stdc++.h>
using namespace std;
int main() {
	int a,b;
   cin>>a>>b;
   cout<<a+b<<endl;
	return 0;
}

该问题非常简单，就只是求 a+b 的和

显然， cin 用来输入 a 与 b

而 cout 用来输出 a 与 b 的和

时间复杂度为 \(\mathcal{O}(1)\)

二：前缀和の做法

#include<bits/stdc++.h>
using namespace std;
const int n=2,MaxN=5;
int a[MaxN],sum[MaxN];
int main() {
	for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
	cout<<sum[n]<<endl;
	return 0;
}

对于该问题，我们可以将其视为一个固定长度为 2 的数组，求两个数的和

非常明显，用前缀和可以在 \(\mathcal{O}(n)\) 时间内快速处理

三：树状数组の做法

#include<bits/stdc++.h>
using namespace std;
const int n=2,MaxN=5;
int t[MaxN];
int lowbit(int x) {
	return x&(-x);
}
void add(int p,int l) {
	for(int i=p;i<=n;i+=lowbit(i)) t[i]+=l;
	return ;
}
int query(int p) {
	int res=0;
	for(int i=p;i>0;i-=lowbit(i)) res+=t[i];
	return res;
}
int main() {
	int x;
	for(int i=1;i<=n;i++) cin>>x,add(1,x);
	cout<<query(2)<<endl;
	return 0;
}

根据方法二把两个数视为一个长度固定的数组

查询两个数的和相当于求一段区间和

用树状数组十分便捷，为 \(\mathcal{O}(n \log n)\)

四：栈の做法

#include<bits/stdc++.h>
using namespace std;
const int n=2,MaxN=5;
int t[MaxN],top;
int main() {
	int x,ans=0;
	for(int i=1;i<=n;i++) cin>>x,t[++top]=x;
	while(top) ans+=t[top--];
	cout<<ans<<endl;
	return 0;
}

想法极简单，把所有数放入一个栈

然后弹空栈，把所有元素累加即可

时间复杂度为 \(\mathcal{O}(n)\)

五：队列の做法

#include<bits/stdc++.h>
using namespace std;
const int n=2,MaxN=5;
int t[MaxN],head,tail;
int main() {
	int x,ans=0;
	for(int i=1;i<=n;i++) cin>>x,t[++tail]=x;
	while(head<tail) ans+=t[++head];
	cout<<ans<<endl;
	return 0;
}

和上面的想法差不多，遍历队列，求累加和

时间复杂度接近 \(\mathcal{O}(n)\)

六：高精の做法

感谢 dfdf_luyanlin 给的灵感

#include<bits/stdc++.h>
using namespace std;
int a[114514],b[114514];
string s;
int main() {
	cin>>s;
	int len=s.size();
	a[0]=len;
	for(int i=0;i<len;i++) a[len-i]=s[i]-'0';
	cin>>s;
	len=s.size();
	b[0]=len;
	for(int i=0;i<len;i++) b[len-i]=s[i]-'0';
	a[0]=max(a[0],b[0]);
	for(int i=1;i<=a[0];i++) {
		a[i]=a[i]+b[i];
		if(a[i]>9) a[i+1]++,a[i]-=10;
	}
	if(a[a[0]+1]) a[0]++;
	for(int i=a[0];i>=1;i--) cout<<a[i];
	return 0;
}

该想法也很简单，使用字符串来记录两个加数的每一位数

逐位相加即可

所以时间复杂度在 \(\mathcal{O}(\log_{10}^n)\) 左右

柒：线段树の做法

#include<bits/stdc++.h>
using namespace std;
int a,b;
int tree[10],lazy[10];
void up(int p) {
    tree[p]=tree[p<<1]+tree[p<<1|1];
    return;
}
void build(int p,int l,int r) {
    if(l==r) {
        tree[p]=0;
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    up(p);
    return;
}
inline void down(int p,int len) {
    if(len<2||!lazy[p]) return;
    lazy[p<<1]+=lazy[p];
    lazy[p<<1|1]+=lazy[p];
    tree[p<<1]+=lazy[p]*(len+1>>1);
    tree[p<<1|1]+=lazy[p]*(len>>1);
    lazy[p]=0;
    return;
}
void update(int p,int l,int r,int R,int L,int v) {
    if(r<L||R<l)return;
    if(L<=l&&r<=R) {
        tree[p]+=(r-l+1)*v;
        lazy[p]+=v;
        return;
    }
    down(p,r-l+1);
    int mid=l+r>>1;
    if(L<=mid)update(p<<1,l,mid,L,R,v);
    if(mid<R) update(p<<1|1,mid+1,r,L,R,v);
    up(p);
    return;
}
int query(int p,int l,int r,int L,int R) {
    if(r<L||R<l) return 0;
    if(L<=l&&r<=R) return tree[p];
    down(p,r-l+1);
    int mid=l+r>>1;
    int res=0;
    if(L<=mid) res+=query(p<<1,l,mid,L,R);
    if(mid<R) res+=query(p<<1|1,mid+1,r,L,R);
    return res;
}
int main() {
    scanf("%d%d",&a,&b);
    update(1,1,2,1,1,a);
    update(1,1,2,2,2,b);
    printf("%d",query(1,1,2,1,2));
    return 0;
}

继续关于树状数组的思考

维护一个数组，除了树状数组，线段树也是一个不错的选择

同样，时间复杂度为 \(\mathcal{O}(n \log n)\)（但是常数巨大）

八： Dijkstra の做法

#include<bits/stdc++.h>
using namespace std;
int head[5],nxt[10],ver[10],wor[10],edgenum;
void addedge(int u,int v,int w) {
	++edgenum;
	ver[edgenum]=v,wor[edgenum]=w;
	nxt[edgenum]=head[u];
	head[u]=edgenum;
	return ;
}
struct node {
	int v,c;
	node(int vv=0,int cc=0) {
		v=vv,c=cc;
		return ;
	}
	friend bool operator<(const node a,const node b) {
		return a.c>b.c;
	}
};
priority_queue<node> q;
int dist[5],vis[5];
int dijkstra(int start,int end) {
	memset(dist,0x3f,sizeof(dist));
	dist[start]=0;
	q.push(node(start,0));
	while(!q.empty()) {
		int u=q.top().v;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		if(u==end) return dist[u];
		for(int e=head[u];e;e=nxt[e]) {
			int v=ver[e],w=wor[e];
			if(!vis[v]&&dist[u]+w<dist[v]) {
				dist[v]=dist[u]+w;
				q.push(node(v,dist[v]));
			}
		}
	}
	return -1;
}
int main() {
	int a,b;
	cin>>a>>b;
	addedge(1,2,a);
	addedge(2,3,b);
	cout<<dijkstra(1,3)<<endl;
	return 0;
}

不妨想象 1,2,3 三个点，a 与 b 分别为 1 到 2 、 2 到 3 的有向边的权值

该题可以用 Dijkstra 算法求解

时间复杂度 \(\mathcal{O}(n \log n+e \log n)\)

九： SPFA の做法

关于 SPFA ，它死了！（好吧我错了 QwQ ）

#include<bits/stdc++.h>
using namespace std;
int head[5],nxt[10],ver[10],wor[10],edgenum;
void addedge(int u,int v,int w) {
	++edgenum;
	ver[edgenum]=v,wor[edgenum]=w;
	nxt[edgenum]=head[u];
	head[u]=edgenum;
	return ;
}
queue<int> q;
int dist[5],vis[5],cnt[5];
const int n=2;
int SPFA(int start,int end) {
	memset(dist,0x3f,sizeof(dist));
	vis[start]=1,dist[start]=0;
	q.push(start);
	while(!q.empty()) {
		int u=q.front();
		vis[u]=0;
		if(cnt[u]>=n) return -1;
		cnt[u]++;
		q.pop();
		for(int e=head[u];e;e=nxt[e]) {
			int v=ver[e],w=wor[e];
			if(dist[u]+w<dist[v]) {
				dist[v]=dist[u]+w;
				if(!vis[v]) {
					q.push(v);
					vis[v]=1;
				}
			}
		}
	}
	return dist[end];
}
int main() {
	int a,b;
	cin>>a>>b;
	addedge(1,2,a);
	addedge(2,3,b);
	cout<<SPFA(1,3)<<endl;
	return 0;
}

如果可以用 Dijkstra 来解，为什么不能用 SPFA 呢？

时间也很高效，接近 \(\mathcal{O}(kE)\)（注意！常数 \(k\) 经常被卡！）

十：并查集の做法

#include<bits/stdc++.h>
using namespace std;
int fa[5],sum[5];
const int n=2;
int find(int x) {
	return fa[x]==x?x:(fa[x]=find(fa[x]));
}
void join(int a,int b) {
	int faa=find(a),fab=find(b);
	fa[fab]=faa;
	sum[faa]+=sum[fab];
	return ;
}
int main() {
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=n;i++) cin>>sum[i];
	join(1,2);
	int fa=find(2);
	cout<<sum[fa];
	return 0;
}

显然，可以想象 1,2 两个点被加入一个点权并查集

这样可以极其高效地解决问题

依然接近 \(\mathcal{O}(n \log^* n)\)

十一：进制转换の做法

#include<bits/stdc++.h>
using namespace std;
int a[40],b[40],taga,tagb;
void doge(int t[],int &ttag,int a) {
	if(a==1) {
		t[++ttag]=a;
		return ;
	}
	t[++ttag]=a&1;
	doge(t,ttag,a/2);
	return ;
}
int A,B;
int main() {
	cin>>A>>B;
	doge(a,taga,A),doge(b,tagb,B);
	taga=max(taga,tagb);
	for(int i=1;i<=taga;i++) {
		a[i]+=b[i];
		if(a[i]>1) {
			a[i]-=2;
			a[i+1]++;
		}
	}
	if(a[taga+1]) taga++;
	int res=1,ans=0;
	for(int i=1;i<=taga;i++) {
		ans+=res*a[i];
		res<<=1;
	}
	cout<<ans<<endl;
	return 0;
}

显然的，可以将 a 和 b 还原成计算机中的二进制进行计算（但为什么要那么麻烦呢。。。）

那么计算过程就和高精度差不多了

时间复杂度也是 \(\mathcal{O}(\log n)\)

十二：二分の做法

#include <bits/stdc++.h>
using namespace std;

int find(int key) {
    int l=1,r=2000000000,mid,ans;
    while(l<=r) {
        mid=(l+r)>>1;
        if(mid>key) r=mid-1;
        else ans=mid,l=mid+1;
    }
    return ans;
}

int main() {
    int a,b;
    cin>>a>>b;
    cout<<find(a+b)<<endl;
    return 0;
}

若枚举 1~2000000000 会超时

那么使用二分答案优化一下

时间复杂度大概也是 \(\mathcal{O}(\log 2000000000)\)

2）The End

本文旨在讲解各种算法，而并非展示 A+B 的做法。希望这篇文章对你有所帮助。

当然，还会慢慢添加的，如果你觉得有什么好的想法或什么不足，大可私信或评论。

希望在使用程序等时标上出处，都是作者一个字一个字敲出来的，谢谢。

另，未来可能会添加的做法：

  1. 数据结构方面：FHQTreap，Treap，LCT

  2. 算法方面：LCA，DFS 序，Prim，Kruscal，Floyed，各种 DP