a+b problem
1.标准做法
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;
int aa[1000001];
int main()
{
cin>>a>>b;
cout<<a+b<<endl;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d;
int aa[1000001];
int main()
{
scanf("%d%d",&a,&b);
printf("%d",a+b);
return 0;
}
2.图论
Dijkstra
#include<bits/stdc++.h>
using namespace std;
struct node{
int to,nxt,w;
} e[1000001];
int a,b,c,d,ans,cnt;
int aa[1000001],head[1000001];
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
e[cnt].w=w;
}
void dfs(int u,int w)
{
if(u==3) ans=w;
for(int i=head[u];i!=0;i=e[i].nxt)
{
int v=e[i].to;
dfs(v,w+e[i].w);
}
}
int main()
{
scanf("%d%d",&a,&b);
add(1,2,a);add(2,3,b);
dfs(1,0);
printf("%d
",ans);
return 0;
}
Floyd
#include<bits/stdc++.h>
using namespace std;
const int N=5,oo=1e9;
int f[N][N];
void floyd()
{
for (int k=1; k<=N; k++)
for (int i=1; i<=N; i++)
if (i==k) continue;
else for (int j=1; j<=N; j++)
if (k==j||i==j) continue;
else f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
int main()
{
int a,b;
for (int i=1;i<=N;i++)
for (int j=1;j<=N;j++)
f[i][j]=oo;
scanf ("%d %d",&a,&b);
f[1][2]=a;
f[2][3]=b;
floyd();
printf("%d",f[1][3]);
return 0;
}
SPFA
#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,op,head[200009],next[200009],dis[200009],len[200009],v[200009],l,r,team[200009],pd[100009],u,v1,e;
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];
}
int main()
{
scanf("%d%d",&a,&b);
lt(1,2,a);lt(2,3,b);
printf("%d",SPFA(1,3));
return 0;
}
LCA
#include <bits/stdc++.h>
#define NI 2
using namespace std;
struct edge
{
int to,next,data;
}e[30];
int 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]) swap(x,y);
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];
}
int main()
{
int a,b;
scanf("%d%d",&a,&b);
build(1,2,a);
build(1,3,b);
dfs(1);
printf("%d",ask(2,3));
}
3.位运算
与 and 或
#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
cout<<(a|b)+(a&b);
return 0;
}
二进制
#include<bits/stdc++.h>
using namespace std;
int cnt(int x)
{
if(abs(x)<2)return x;
return cnt(x>>1)+cnt(x-(x>>1));
}
int a,b;
int main()
{
cin>>a>>b;
cout<<cnt(a)+cnt(b);
return 0;
}
异或 and 与
#include <bits/stdc++.h>
using namespace std;
int m, n;
int main()
{
scanf("%d%d", &m, &n);
int u=m&n;
int v=m^n;
while(u)
{
int s=v;
int t=u<<1;
u=s&t;
v=s^t;
}
printf("%d
",v);
}
4.算法
高精度
#include <bits/stdc++.h>
using namespace std;
int main()
{
char a1[1000],b1[1000];
int a[1000]= {0},b[1000]= {0},c[1000]= {0},la,lb,lc,i,x;
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--) cout<<c[i];
cout<<endl;
return 0;
}
二分
#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{
long long l=-int(1e9)<<1,r=int(1e9)<<1;
scanf("%d%d",&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("%d
",c),0;
}
if(l!=r) return printf("%d
",r),0;
}
递归
#include <bits/stdc++.h>
using namespace std;
long long int a,b,c;
long long int dg(long long a)
{
if(a<=5) return a;
return dg(a/2)+dg(a-a/2);
}
int main()
{
cin>>a>>b;
c=dg(a)+dg(b);
cout<<c<<endl;
}
线段树
#include <bits/stdc++.h>
using namespace std;
struct node
{
int val,l,r;
};
node t[5];
int a[5],f[5];
int n,m;
void init()
{
for(int i=1; i<=2; i++)
{
scanf("%d",&a[i]);
}
}
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;
}
int main()
{
init();
build(1,2,1);
printf("%d",find(1,2,1));
}
5.快读
#include <bits/stdc++.h>
#define reg register
using namespace std;
inline int s()
{
reg char ch=getchar();
reg int re=0;
reg bool fl=1;
if(ch=='-')
{
fl=0;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
re=re*10+ch-'0';
ch=getchar();
}
return fl?re:-re;
}
inline bool w(reg int r)
{
if(r>9) w(r/10);
putchar(r%10+'0');
return 1;
}
int main()
{
reg int a=s(),b=s();
if(a+b>=0) return !w(a+b);
putchar('-');
return !w(-a-b);
}
#include <bits/stdc++.h>
using namespace std;
int read()
{
int out=0,fh=1;
char cc=getchar();
if (cc=='-') fh=-1;
while (cc>'9'||cc<'0') cc=getchar();
while (cc>='0'&&cc<='9')
{
out=out*10+cc-'0';
cc=getchar();
}
return out*fh;
}
void write(int x)
{
if (x==0)
{
putchar('0');
return;
}
int num = 0;
char c[15];
while(x) c[++num] = (x%10)+48, x /= 10;
while(num) putchar(c[num--]);
putchar(' ');
}
int main()
{
write(read()+read());
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int read()
{
int f=1,x=0;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
int main()
{
printf("%d",read()+read());
return 0;
}