感觉挺好的一道题,可以检验一下自己学习OI的知识牢不牢固。
题目描述
计算 $A+B$
样例
input:
1 2
output:
3
算法1
(标程)$(O^1)$
#include <cstdio>
using namespace std;
int main(void)
{
int n,m;
scanf("%d%d",&n,&m);
printf("%d\n",n+m);
return 0;
}
算法2
(暴力枚举)
#include <cstdio>
#include <algorithm>
using namespace std;
int main(void)
{
int n,m;
scanf("%d%d",&n,&m);
for(register int i=0;i<=max(n,m)*max(n,m);i++)
{
if(n+m==i)
{
printf("%d\n",n+m);
return 0;
}
}
}
算法3
(高精度)
#include<iostream>
#include<cstring>
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;
}
算法4
(递归)
#include<iostream>
using namespace std;
long long a,b,c;
long long 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;
}
算法5
(Floyed (懒得打Dijkstra )
#include<iostream>
#include<cstring>
using namespace std;
long long n=3,a,b,dis[4][4];
int main()
{
cin>>a>>b;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
dis[i][j]=1<<29;
}
}
dis[1][2]=a,dis[2][3]=b;
for(register int k=1;k<=n;k++)
{
for(register int i=1;i<=n;i++)
{
for(register int j=1;j<=n;j++)
{
dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
}
cout<<dis[1][3];
return 0;
}
算法6
(线段树)
手写到吐…
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1000005;
ll a[maxn],ans[maxn<<2],t[maxn<<2];
inline ll ls(ll p)
{
return p<<1;
}
inline ll rs(ll p)
{
return p<<1|1;
}
inline void pushup(ll p)
{
ans[p]=ans[ls(p)]+ans[rs(p)];
}
inline void build(ll p,ll l,ll r)
{
t[p]=0;
if(l==r)
{
ans[p]=a[l];
return;
}
ll mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pushup(p);
}
inline void lazy(ll p,ll l,ll r,ll k)
{
t[p]+=k;
ans[p]+=k*(r-l+1);
}
inline void pushdown(ll p,ll l,ll r)
{
ll mid=(l+r)>>1;
lazy(ls(p),l,mid,t[p]);
lazy(rs(p),mid+1,r,t[p]);
t[p]=0;
}
inline void updata(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
if(nl<=l && r<=nr)
{
lazy(p,l,r,k);
return;
}
pushdown(p,l,r);
ll mid=(l+r)>>1;
if(nl<=mid)
{
updata(nl,nr,l,mid,ls(p),k);
}
if(nr>mid)
{
updata(nl,nr,mid+1,r,rs(p),k);
}
pushup(p);
}
inline ll query(ll q_x,ll q_y,ll l,ll r,ll p)
{
if(q_x<=l && r<=q_y)
{
return ans[p];
}
ll res=0;
ll mid=(l+r)>>1;
pushdown(p,l,r);
if(q_x<=mid)
{
res+=query(q_x,q_y,l,mid,ls(p));
}
if(q_y>mid)
{
res+=query(q_x,q_y,mid+1,r,rs(p));
}
return res;
}
ll n,m;
int main()
{
scanf("%lld%lld",&n,&m);
a[1]=n,a[2]=m;
build(1,1,2);
printf("%lld\n",query(1,2,1,2,1));
return 0;
}
跑的超快!!!
算法7
(二分)
#include <cstdio>
using namespace std;
int main(void)
{
int n,m;
scanf("%d%d",&n,&m);
int l=-99999,r=2*(n+m);
int x=0;
while(l+1<r)
{
x=(l+r+1)>>1;
if(n+m>x)
{
l=x;
}
else if(n+m<x)
{
r=x;
}
else
{
printf("%d\n",x);
return 0;
}
}
if(l!=r)
{
printf("%d\n",r);
}
return 0;
}
$upd$
算法8
(最小生成树Kruskal)
#include <cstdio>
#include <algorithm>
using namespace std;
const int INF=(1<<29);
struct node
{
int x;
int y;
int t;
};
node a[10];
inline bool cmp(node a,node b)
{
return a.t<b.t;
}
int f[15];
int k,n,m,x,y,t,ans;
int get(int x)
{
if(f[x]==x)
{
return x;
}
f[x]=get(f[x]);
return f[x];
}
int main()
{
for(register int i=1;i<=10;i++)
{
f[i]=i;
}
for(register int i=1;i<=2;i++,k++)
{
scanf("%d",&a[i].t);
a[i].x=i+1;
a[i].y=1;
}
a[++k].x=1;a[k].y=3,a[k].t=INF;
sort(a+1,a+1+k,cmp);
for(register int i=1;i<=k;i++)
{
x=get(a[i].x);
y=get(a[i].y);
if(x!=y)
{
f[x]=y;
ans+=a[i].t;
}
}
printf("%d\n",ans);
return 0;
}
鄙人码力薄弱,请多见谅。
📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊📡๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊๊
被最后一句话破防了
?
orz
A + B Problem 是检验一个人算法程度的唯一标准(bushi
屮 哈哈哈
orz stO