A+B problem
Jerrlee✅
2021-08-30 22:27:21
## 错解：
```cpp
#include<cstdio>
using namespace std;
int main(){
long long a,b;
scanf("%lld%lld",&a,&b);
printf("%lld",a+b);
}
```
## 正解：
**一，递归**
```cpp
#include<cstdio>
using namespace std;
#define int long long
int a,b,c;
int f(int a){
if(a<=5) return a;
return f(a/2)+f(a-a/2);
}
signed main(){
scanf("%lld%lld",&a,&b);
c=f(a)+f(b);
printf("%lld",c);
}
```
**二，二分**
```cpp
#include<cstdio>
using namespace std;
long long a,b,c;
signed main(){
long long l=-int(1e9)<<1,r=int(1e9)<<1;
scanf("%lld%lld",&a,&b);
while(r-l>1){
c=(l+r)>>1;
if(c-b<a) l=c;
else if(c-b>a) r=c;
else return printf("%lld",c),0;
}
if(l!=r) return printf("%lld",r),0;
}
```
**三，模拟**
```cpp
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long
int fu=1,f=1,a,b,c;
signed main(){
scanf("%lld%lld",&a,&b);
if(a<0&&b>0) fu=2;
if(a>0&&b<0) fu=3;
if(a<0&&b<0) f=-1;
if(a==0) return printf("%lld",b),0;
if(b==0) return printf("%lld",a),0;
a=abs(a),b=abs(b);
if(a>b&&fu==3) f=1;
if(b>a&&fu==3) f=-1;
if(b>a&&fu==2) f=1;
if(b<a&&fu==2) f=-1;
if(fu==1) c=a+b;
if(fu>1) c=max(a,b)-min(a,b);
c*=f;
printf("%lld",c);
}
```
**四，高精**
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define int long long
int la,lb,lc,i,x,a[1000],b[1000],c[1000];
char a1[1000],b1[1000];
signed main(){
cin>>a1>>b1;
la=strlen(a1),lb=strlen(b1);
for(i=0;i<=la-1;i++) a[la-i]=a1[i]-48;
for(i=0;i<=lb-1;i++) b[lb-i]=b1[i]-48;
lc=1,x=0;
while(lc<=la||lc<=lb) c[lc]=a[lc]+b[lc]+x,x=c[lc]/10,c[lc]%=10,lc++;
c[lc]=x;
if(c[lc]==0) lc--;
for(i=lc;i>=1;i--) printf("%lld",c[i]);
}
```
**五，Floyd**
```cpp
#include<cstdio>
#include<iostream>
using namespace std;
#define int long long
int n=3,a,b,dis[4][4];
signed main(){
scanf("%lld%lld",&a,&b);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) dis[i][j]=2147483647;
dis[1][2]=a,dis[2][3]=b;
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
printf("%lld",dis[1][3]);
}
```
**六，Dijkstra+STL**
```cpp
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define int long long
const int N=405;
struct Edge{
int v,w;
};
vector<Edge>edge[N*N];
int a,b,n,dis[N*N];
bool vis[N*N];
struct cmp{
bool operator()(int a,int b){
return dis[a]>dis[b];
}
};
int Dijkstra(int start,int end){
priority_queue<int,vector<int>,cmp>dijQue;
memset(dis,-1,sizeof(dis));
memset(vis,0,sizeof(vis));
dijQue.push(start);
dis[start]=0;
while(!dijQue.empty()){
int u=dijQue.top();
dijQue.pop();
vis[u]=0;
if(u==end) break;
for(int i=0;i<edge[u].size();i++) {
int v=edge[u][i].v;
if(dis[v]==-1||dis[v]>dis[u]+edge[u][i].w){
dis[v]=dis[u]+edge[u][i].w;
if(!vis[v]){
vis[v]=true;
dijQue.push(v);
}
}
}
}
return dis[end];
}
signed main(){
scanf("%lld%lld",&a,&b);
Edge Qpush;
Qpush.v=1,Qpush.w=a;
edge[0].push_back(Qpush);
Qpush.v=2,Qpush.w=b;
edge[1].push_back(Qpush);
printf("%lld",Dijkstra(0,2));
}
```
**七，SPFA**
```cpp
#include<cstdio>
using namespace std;
#define int long long
int n,m,a,b,l,r,u,e,v1,op,head[200009],next[200009],dis[200009],len[200009],v[200009],team[200009],pd[100009];
int lt(int x,int y,int z){
op++,v[op]=y;
next[op]=head[x],head[x]=op,len[op]=z;
}
int SPFA(int s,int f){
for(int i=1;i<=200009;i++) dis[i]=999999999;
l=0,r=1,team[1]=s,pd[s]=1,dis[s]=0;
while(l!=r){
l=(l+1)%90000,u=team[l],pd[u]=0,e=head[u];
while(e!=0){
v1=v[e];
if(dis[v1]>dis[u]+len[e]){
dis[v1]=dis[u]+len[e];
if(!pd[v1]){
r=(r+1)%90000,
team[r]=v1,
pd[v1]=1;
}
}
e=next[e];
}
}
return dis[f];
}
signed main(){
scanf("%lld%lld",&a,&b);
lt(1,2,a);
lt(2,3,b);
printf("%lld",SPFA(1,3));
}
```
**八，最小生成树**
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
#define INF 2140000000
struct tree{
int x,y,t;
}a[10];
bool cmp(const tree&a,const tree&b){
return a.t<b.t;
}
int f[11],i,j,k,n,m,x,y,t,ans;
int root(int x){
if(f[x]==x) return x;
f[x]=root(f[x]);
return f[x];
}
signed main(){
for(i=1;i<=10;i++) f[i]=i;
for(i=1;i<=2;i++){
scanf("%lld",&a[i].t);
a[i].x=i+1;a[i].y=1;k++;
}
a[++k].x=1;a[k].y=3,a[k].t=INF;
sort(a+1,a+1+k,cmp);
for(i=1;i<=k;i++){
x=root(a[i].x),y=root(a[i].y);
if(x!=y) f[x]=y,ans+=a[i].t;
}
printf("%lld",ans);
}
```
**九，线段树**
```cpp
#include<cstdio>
using namespace std;
#define int long long
struct node{
int val,l,r;
};
node t[5];
int n,m,a[5],f[5];
void build(int l,int r,int node){
t[node].l=l;t[node].r=r;t[node].val=0;
if(l==r){
f[l]=node;
t[node].val=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,node*2);
build(mid+1,r,node*2+1);
t[node].val=t[node*2].val+t[node*2+1].val;
}
void update(int node){
if(node==1) return;
int fa=node>>1;
t[fa].val=t[fa*2].val+t[fa*2+1].val;
update(fa);
}
int find(int l,int r,int node){
if(t[node].l==l&&t[node].r==r) return t[node].val;
int sum=0;
int lc=node*2;int rc=lc+1;
if(t[lc].r>=l){
if(t[lc].r>=r) sum+=find(l,r,lc);
else sum+=find(l,t[lc].r,lc);
}
if(t[rc].l<=r){
if(t[rc].l<=l) sum+=find(l,r,rc);
else sum+=find(t[rc].l,r,rc);
}
return sum;
}
signed main(){
for(int i=1;i<=2;i++) scanf("%lld",&a[i]);
build(1,2,1);
printf("%lld",find(1,2,1));
}
```
**十，字典树**
```cpp
#include<cstdio>
#include<cstring>
using namespace std;
#define int long long
struct node{
int sum,str[26];
}s[1000];
char str1[100];
int t=0,tot=0,ss=0;
bool f1;
void built(){
t=0;
for(int i=0;i<strlen(str1);i++){
if(str1[i]=='-'){
f1=true;
continue;
}
if(!s[t].str[str1[i]-'0'])
s[t].str[str1[i]-'0']=++tot;
t=s[t].str[str1[i]-'0'];
s[t].sum=str1[i]-'0';
}
}
int query(){
int t=0;int s1=0;
for(int i=0;i<strlen(str1);i++){
if(str1[i]=='-') continue;
if(!s[t].str[str1[i]-'0']) return s1;
t=s[t].str[str1[i]-'0'];
s1=s1*10+s[t].sum;
}
return s1;
}
signed main(){
for(int i=1;i<=2;i++){
f1=false;
scanf("%s",str1);
built();
if(f1)
ss-=query();
else ss+=query();
}
printf("%lld",ss);
}
```
**十一，LCA**
```cpp
#include<cstdio>
#define int long long
#define NI 2
struct edge{
int to,next,data;
}e[30];
int a,b,v[10],d[10],lca[10][NI+1],f[10][NI+1],tot=0;
void build(int x,int y,int z){
e[++tot].to=y; e[tot].data=z; e[tot].next=v[x]; v[x]=tot;
e[++tot].to=x; e[tot].data=z; e[tot].next=v[y]; v[y]=tot;
}
void dfs(int x){
for(int i=1;i<=NI;i++)
f[x][i]=f[x][i-1]+f[lca[x][i-1]][i-1],
lca[x][i]=lca[lca[x][i-1]][i-1];
for(int i=v[x];i;i=e[i].next){
int y=e[i].to;
if(lca[x][0]==y) continue;
lca[y][0]=x;
f[y][0]=e[i].data;
d[y]=d[x]+1;
dfs(y);
}
}
int ask(int x,int y){
if(d[x]<d[y]){
int t=x;
x=y;
y=t;
}
int k=d[x]-d[y],ans=0;
for(int i=0;i<=NI;i++)
if(k&(1<<i))
ans+=f[x][i],
x=lca[x][i];
for(int i=NI;i>=0;i--)
if(lca[x][i]!=lca[y][i])
ans+=f[x][i]+f[y][i],
x=lca[x][i],y=lca[y][i];
return ans+f[x][0]+f[y][0];
}
signed main(){
scanf("%lld%lld",&a,&b);
build(1,2,a);
build(1,3,b);
dfs(1);
printf("%lld",ask(2,3));
}
```
**十二，LCT**
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
struct node{
int data,rev,sum;
node *son[2],*pre;
bool judge();
bool isroot();
void pushdown();
void update();
void setson(node *child,int lr);
}lct[233];
int top,a,b;
node *getnew(int x){
node *now=lct+ ++top;
now->data=x;
now->pre=now->son[1]=now->son[0]=lct;
now->sum=0;
now->rev=0;
return now;
}
bool node::judge(){return pre->son[1]==this;}
bool node::isroot(){
if(pre==lct)return true;
return !(pre->son[1]==this||pre->son[0]==this);
}
void node::pushdown(){
if(this==lct||!rev)return;
swap(son[0],son[1]);
son[0]->rev^=1;
son[1]->rev^=1;
rev=0;
}
void node::update(){sum=son[1]->sum+son[0]->sum+data;}
void node::setson(node *child,int lr){
this->pushdown();
child->pre=this;
son[lr]=child;
this->update();
}
void rotate(node *now){
node *father=now->pre,*grandfa=father->pre;
if(!father->isroot()) grandfa->pushdown();
father->pushdown();now->pushdown();
int lr=now->judge();
father->setson(now->son[lr^1],lr);
if(father->isroot()) now->pre=grandfa;
else grandfa->setson(now,father->judge());
now->setson(father,lr^1);
father->update();now->update();
if(grandfa!=lct) grandfa->update();
}
void splay(node *now){
if(now->isroot())return;
for(;!now->isroot();rotate(now))
if(!now->pre->isroot())
now->judge()==now->pre->judge()?rotate(now->pre):rotate(now);
}
node *access(node *now){
node *last=lct;
for(;now!=lct;last=now,now=now->pre){
splay(now);
now->setson(last,1);
}
return last;
}
void changeroot(node *now){
access(now)->rev^=1;
splay(now);
}
void connect(node *x,node *y){
changeroot(x);
x->pre=y;
access(x);
}
void cut(node *x,node *y){
changeroot(x);
access(y);
splay(x);
x->pushdown();
x->son[1]=y->pre=lct;
x->update();
}
int query(node *x,node *y){
changeroot(x);
node *now=access(y);
return now->sum;
}
signed main(){
scanf("%lld%lld",&a,&b);
node *A=getnew(a);
node *B=getnew(b);
connect(A,B);
cut(A,B);
connect(A,B);
printf("%lld",query(A,B));
}
```
**十三，树剖**
```cpp
#include<iostream>
#include<vector>
using namespace std;
#define int long long
#define MAXN 100005
#define lson(x) ((x)<<1)
#define rson(x) (((x)<<1)+1)
int n,x,y,tot,dep[MAXN],fa[MAXN],siz[MAXN],son[MAXN],top[MAXN],val[MAXN],idx[MAXN],mp[MAXN],sum[MAXN*4],lazy[MAXN*4];
vector<int>a[MAXN];
void pushdown(int x,int y,int p){
int mid=(x+y)>>1;
sum[lson(p)]+=(mid-x+1)*lazy[p];lazy[lson(p)]+=lazy[lson(p)];
sum[rson(p)]+=(y-mid)*lazy[p];lazy[rson(p)]+=lazy[p];
lazy[p]=0;
}
void build(int x,int y,int p){
if(x==y){
sum[p]=idx[x];
return;
}
pushdown(x,y,p);
int mid=(x+y)>>1;
build(x,mid,lson(p));
build(mid+1,y,rson(p));
sum[p]=sum[lson(p)]+sum[rson(p)];
}
int query(int x,int y,int l,int r,int p){
if(l<=x&&r>=y) return sum[p];
pushdown(x,y,p);
int mid=(x+y)>>1,ans=0;
if(l<=mid)ans+=query(x,mid,l,r,lson(p));
if(r>mid)ans+=query(mid+1,y,l,r,rson(p));
sum[p]=sum[lson(p)]+sum[rson(p)];
return ans;
}
void modify(int x,int y,int l,int r,int val,int p){
if(l<=x&&r>=y){
lazy[p]+=val;
sum[p]+=val*(y-x+1);
return;
}
pushdown(x,y,p);
int mid=(x+y)>>1;
if(l<=mid)modify(x,mid,l,r,val,lson(p));
if(r>mid)modify(mid+1,y,l,r,val,rson(p));
sum[p]=sum[lson(p)]+sum[rson(p)];
return;
}
void dfs_build(int p){
dep[p]=dep[fa[p]]+1;
siz[p]=1;
for(int i=0;i<a[p].size();++i){
if(a[p][i]==fa[p])continue;
fa[a[p][i]]=p;
dfs_build(a[p][i]);
siz[p]+=siz[a[p][i]];
if(siz[son[p]]<siz[a[p][i]])
son[p]=a[p][i];
}
}
void dfs_top(int p){
top[p]=son[fa[p]]!=p?p:top[fa[p]];
idx[++tot]=val[p];mp[p]=tot;
if(son[p])dfs_top(son[p]);
for(int i=0;i<a[p].size();++i)
if(a[p][i]!=fa[p]&&a[p][i]!=son[p])
dfs_top(a[p][i]);
}
void OP1(int x,int y,int w){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
modify(1,n,mp[top[x]],mp[x],w,1);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
modify(1,n,mp[x],mp[y],w,1);
return;
}
int OP2(int x,int y){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans+=query(1,n,mp[top[x]],mp[x],1);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans+=query(1,n,mp[x],mp[y],1);
return ans;
}
signed main(){
n=3;
a[1].push_back(2);a[1].push_back(3);
a[2].push_back(1);a[3].push_back(1);
dfs_build(1);
dfs_top(1);
build(1,n,1);
scanf("%lld%lld",&x,&y);
OP1(2,2,x);
OP1(3,3,y);
printf("%lld",OP2(2,3));
}
```
**以上内容推荐在需要计算加法时使用**