做法"/>
A+B 的做法
C++ 的做法
建议全程 Crtl+A 食用- 原题:
这道题是程序设计经典问题。要求输入两个整数 A和 B,中间用空格分开。输出这两个整数的和。
- 数据范围:
0≤A,B≤1090,总之 A+B 不会超 int;
一:普通の做法#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 的和
时间复杂度为 οο (1)
UPD: 2023.6.4
二:前缀和の做法
#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 的数组
求两个数的和
非常明显,用前缀和可以在 οο (n) 时间内快速处理
又因 n 恒等于 2 ,因此时间复杂度为 οο (1)
UPD: 2023.6.4
三:树状数组の做法
#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;
}
根据方法二把两个数视为一个长度固定的数组
查询两个数的和相当于求一段区间和
用树状数组十分便捷
同上,因为常数较小,时间复杂度几乎为 οο (1)
UPD: 2023.6.4
四:栈の做法
#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;
}
想法极简单,把所有数放入一个栈
然后弹空栈,把所有元素累加即可
常数极小,时间复杂度也为 οο (1)
UPD: 2023.6.4
五:队列の做法
#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;
}
和上面的想法差不多
遍历队列,求累加和
时间复杂度接近 οο (1)
UPD: 2023.6.4
六:高精の做法
#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;
}
该想法也很简单,使用字符串来记录两个加数的每一位数
逐位相加即可
因为 a,b≤1,000,000,000a,b≤1,000,000,000 ,所以时间复杂度在 οο (1) 左右
UPD: 2023.6.5
柒:线段树の做法
#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;
}
继续关于树状数组的思考
维护一个数组,除了树状数组,线段树也是一个不错的选择
同样,时间复杂度接近 οο (1)
UPD: 2023.6.5
八: 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 算法求解
理论时间复杂度 οο (nlgn+elgn)
实际速度接近 οο (1)
UPD: 2023.6.5
九: 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 呢?
时间也很高效,接近 οο(1)
UPD: 2023.6.5
十:并查集の做法
#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 两个点被加入一个点权并查集
这样可以极其高效地解决问题
依然接近 οο (1)
UPD: 2023.6.5
十一:进制转换の做法
#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 还原成计算机中的二进制进行计算(但为什么要那么麻烦呢。。。)
那么计算过程就和高精度差不多了
时间复杂度也是接近 οο (1) 的存在
UPD: 2023.6.6
随缘更新。求轻喷。
该文章只呈现了能完全 AC 的代码
一些无法 AC 的代码是不会出现的
大多数 οο (1) 的算法都是因为常数足够小( n=2 或 3 ),不代表该算法在实际应用中的时间复杂度
如果你发现有些代码有缺陷,请及时告知作者
当你有其他好的意见的时候,请及时告知作者
广告位出租
黑暗森林安全声明:
- 该blog中的写法皆原创(除非特殊标明),版权归原作者 CAXXJYC 所有。
- 未经作者允许不得转载本文内容,否则将视为侵权。
- 转载或者引用本文内容请注明来源及原作者。
- 对于不遵守此声明或者其他违法使用本文内容者,本人依法保留追究权等。
(仿照机灵鹤的声明)
CAXXSZN
更多推荐
A+B 的做法
发布评论