手把手教你做A+B Problem

XJZ_AK_IOI  •  1个月前

只要你把Luogu上所有的A+B Problem解法全部掌握 你就能NOIP提高组1=

by AK IOI的XJZ

所以 本蒟蒻写了一篇A+B Problem的题解 各位大佬多多包涵

1.递归

/*
因为a=1+(a-1)
这就可以很自然的想到递归
*/
    #include<bits/stdc++.h>
    using namespace std;
    int a,b;
    int dfs(int n){
    	if(n==0)
    		return 0;
    	return dfs(n-1)+1;
    }
    int main()
    {
    	cin>>a>>b;
    	cout<<dfs(a)+dfs(b);
    }

2.高精度

/*
不怕一万 就怕万一
万一long long都不够大怎么办
于是 就自然的引出了高精度
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int a[N],b[N],c[N],j;
bool x=false;
char s[N],ss[N];
int main(){
	scanf("%s%s",s,ss); 
	a[0]=strlen(s);
	b[0]=strlen(ss);
	for(int i=1;i<=a[0];i++)
		a[i]=s[a[0]-i]-'0';
	for(int i=1;i<=b[0];i++)
		b[i]=ss[b[0]-i]-'0';
	for(j=1;j<=max(a[0],b[0])+1;j++){
		c[j]=a[j]+b[j];
		if(c[j]>=10){
			c[j]%=10;
			a[j+1]++;
		}
	}
	c[0]=j;
	if(c[j+1]>0)c[0]++;
	for(int i=c[0];i>=1;i--){
		if(c[i]==0&&!x)continue;
		x=true;
		cout<<c[i];
	}
	return 0;
}

3.二分

/*
我们可以确定a+b的答案一定在min(a,b)~max(a,b)*2之间
所以在区间内二分查找a+b的答案
*/
    #include<bits/stdc++.h>
    using namespace std;
    int a,b;
    int main()
    {
    	cin>>a>>b;
    	int l=min(a,b),r=max(a,b)*2,mid=(l+r)/2;
    	while(l!=r){
    		if(mid==a+b){
    			cout<<mid;
    			break;
    		}
    		else if(mid>a+b){
    			r=mid;
    			mid=(l+r)/2;
    		}
    		else{
    			l=mid;
    			mid=(l+r)/2;
    		}
    	}
    	return 0;
    }

4.DP

/*
我们可以定义一个判断数组 true表示当前这位可以算到 false表示不能
最后从a+b到1逆序查找最大值即可
*/
    #include<bits/stdc++.h>
    using namespace std;
    int a,b;
    bool dp[205];
    int main()
    {
    	cin>>a>>b;
    	int n=max(a,b);
    	dp[a]=true,dp[b]=true;
    	for(int i=a+b;i>=1;--i){
    		if(dp[i-a])
    			dp[i]=true;
    		if(dp[i-b])
    			dp[i]=true;
    	}
    	for(int i=a+b;i>=1;--i)
    		if(dp[i]){
    			cout<<i;
    			break;
    		}
    	return 0;
    }

5.Floyd

/*
我们假设(1,2)的权值为a,(2,3)的权值为b
则(1,3)的最短路就是a+b
*/
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000;
int a,b;
int n=3;
int dp[maxn][maxn];
int main()
{
	cin>>a>>b;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			dp[i][j]=0x7ffffff;
	dp[1][2]=a,dp[2][3]=b;
	for(int k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)	
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
	cout<<dp[1][3];
	return 0;
}

6.Dijkstra+堆优化

/*
我们假设a是起始点 b是终点 每条边的权值是两点点权之和
则a到b的最短路就是a+b
*/
#include<bits/stdc++.h>
#define INF 1000000000000
using namespace std;
vector <pair<long long, long long > > a[110];
priority_queue <pair<long long, long long > > q;
long long n,k,s,t;
long long dis[100050];
int main(){
	cin>>s>>t;
	n=max(s,t);
	long long st=-s-t;
	a[s].push_back(make_pair(-s-t,t));
	a[t].push_back(make_pair(-s-t,s));
	for(int i=1;i<=n;++i)
		dis[i]=INF;
	for(int i=0;i<a[s].size();++i)
		dis[a[s][i].second]=min(-a[s][i].first,dis[a[s][i].second]);
	dis[s]=0;
    for(int i=1;i<=n;++i)
        q.push(make_pair(-dis[i],i));
	while(!q.empty()){
        long long u=-q.top().first,v=q.top().second;
	  	    q.pop();
        if(dis[v]<u)continue;
        for(int i=0;i<a[v].size();++i){
            long long qs=a[v][i].first,ws=a[v][i].second;
	            if(dis[qs]>dis[v]+ws){
	            	dis[qs]=dis[v]+ws;	
					q.push(make_pair(-dis[qs],qs));
				}
        }
    }
	cout<<dis[t];
	return 0;
}

7.Kruskal

/*
设a是一棵子树 b也是一棵子树 则将它们变成同一棵树的代价就是a+b(边权为点权和)
这就能很自然的想到最小生成树
*/
#include<bits/stdc++.h>
using namespace std;
struct node{
	int q1,q2,k;
}a[100005];
bool cmp(node a,node b){
	return a.k<b.k;
}int pre[10005];
int find(int root)
{
	int son,tmp;
	son=root;
	while(root!=pre[root]) 
		root=pre[root];
	while(son!=root){
		tmp=pre[son];
		pre[son]=root;
		son=tmp;
	}
	return root; 
}
int n=2,m=1;
int mx=-1;
int main()
{
	for(int i=1;i<=m;++i){
		scanf("%d%d",&a[i].q1,&a[i].q2);
		a[i].k=a[i].q1+a[i].q2;
		mx=max(mx,a[i].q1);
		mx=max(mx,a[i].q2);
	}
	for(int i=1;i<=mx;++i)
		pre[i]=i;
	sort(a+1,a+1+m,cmp);
	long long num=0;
	for(int i=1;i<=m;++i){
		int Q1=a[i].q1,Q2=a[i].q2;
		if(find(Q1)!=find(Q2)){
			pre[find(Q1)]=find(Q2);
			num+=a[i].k;
		}
	}
	cout<<num;
	return 0;
}

8.线段树

/*
a+b要求的也就是区间和 那就能自然的想到线段树维护区间
*/
#include<bits/stdc++.h>
using namespace std;
struct Node{
	int l;
	int r; 
	int sum; 
}tree[10];
int a[10],n=2;
void FZ(int num){ 
	tree[num].sum=tree[num*2].sum + tree[num*2+1].sum;
	return;
}     
static void JS(int l,int r,int num){
	tree[num].l=l;
	tree[num].r=r;
	if(l==r){ 
	tree[num].sum=a[l];
	return;
	}
	int mid=(l+r)/2;
	JS(l,mid,num*2); 
	JS(mid+1,r,num*2+1); 
	FZ(num);
	}
	void DDXG(int i,int value,int num){ 
	if (tree[num].l==tree[num].r){
	tree[num].sum=value;
	return;
	}
	int mid=(tree[num].l+tree[num].r)/2;
	if(i<=mid)
	DDXG(i,value,num*2); 
	else
	DDXG(i,value,num*2+1); 
	FZ(num);
}
static int QJCX(int l,int r,int num){
	if(tree[num].l==l&&tree[num].r==r) 
	return tree[num].sum;
	int mid=(tree[num].l+tree[num].r)/2;
	if(r<=mid)
	return QJCX(l,r,num*2);
	if (l>mid)
	return QJCX(l,r,num*2+1);
	return QJCX(l,mid,num*2)+QJCX(mid+1,r,num*2+1); 
	}
int main()
{
	for(int i=1;i<=n;++i)
	cin>>a[i];
	JS(1,n,1);
	cout<<QJCX(1,2,1);
}

下面的代码由AKIOI的XJZ大佬友情赞助

已死的SPFA

#include<bits/stdc++.h>
using namespace std;
int inf=0x7fffffff;
int n,m,tot;
int dis[10005],vis[10005],head[500005],cnt[500005];
struct Edge
{
    int next,to,dis;
}edge[500005]; 
void add(int from,int to,int dis) 
{ 
    edge[++tot].next=head[from]; 
    edge[tot].to=to; 
    edge[tot].dis=dis; 
    head[from]=tot; 
}
int spfa(int s)
{
    queue<int>q; 
    for(int i=1;i<=n;i++) 
    {
        dis[i]=inf; 
        vis[i]=0; 
    }
    cnt[s]=1;
    q.push(s);
 dis[s]=0;
 vis[s]=1; 
    while(!q.empty())
    {
        int u=q.front(); 
        q.pop(); vis[u]=0; 
        for(int i=head[u];i;i=edge[i].next)
        {
            int v=edge[i].to; 
            if(dis[v]>dis[u]+edge[i].dis)
            {
             cnt[v]=cnt[u]+1;
                dis[v]=dis[u]+edge[i].dis;
                if(cnt[v]>n)
                return 0;
                if(vis[v]==0)
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return 1;
}
int main()
{
 n=3;
 int x,y;
 cin>>x>>y;
    add(1,2,x);
    add(2,3,y);
    if(!spfa(1))
    {
     cout<<"天呐!!!a+b都有负环,spfa无语";
     return 0;
 }
 cout<<dis[3];
    return 0;
}
//既然zsh都写最短路了,我就帮他写份spfa吧
//ZSH:话说SPFA的数组为什么要叫dis?

树状数组

#include<bits/stdc++.h>
using namespace std;
int c[100010];
int n,m;
int lb(int x)
{
    return x&(-x);
}
void add(int k,int v)
{
    for(int i=k;i<=n;i+=lb(i))c[i]+=v;
}
int qh(int k)
{
    int ans=0;
    for(int i=k;i;i-=lb(i))ans+=c[i];
    return ans;
}
int main()
{
    n=2;
    int x,y;
    cin>>x>>y;
    add(1,x);
    add(2,y);
    cout<<qh(2);
    return 0;
}
//树状数组 又是我写?zsh去哪了!!!

灵感来源:this

ps:本博客将不定期更新

another ps:听说在代码后面%XJZ大佬会有好运哦

好了 这篇A+B Problem的题解就到这里 大家都学废了吗?


暂未启用评论功能。