145 条题解
-
5
这题是入门的基础题,可以用很多方法求解,下面是最简单的几种方法,讲解与代码奉上。
1.普通解法:运用了普通计算机加法计算方法,C与C++代码如下:
//c语言解法 #include<cstdio> using namespace std; int main(){ int a, b; scanf("%d%d", &a, &b); printf("%d%d", a + b); return 0; }
//c++语言解法 #include<bits/stdc++.h> using namespace std; int main(){ int a, b; cin >> a >> b; cout << a + b; return 0; }
2.LCT(Link-Cut Tree)解法:使用动态树来解这题,是较
简单难的,不多说,代码奉上::#include<iostream> #include<cstring> #include<cstdio> #include<cstring> using namespace std; 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; } int main() { scanf("%d%d",&a,&b); node *A=getnew(a); node *B=getnew(b); connect(A,B); cut(A,B); connect(A,B); printf("%d\n",query(A,B)); return 0; }
3.树状数组解法:也很“简单”,代码如下:
#include<iostream> #include<cstring> using namespace std; int lowbit(int a) { return a&(-a); } int main() { int n=2,m=1; int ans[m+1]; int a[n+1],c[n+1],s[n+1]; int o=0; memset(c,0,sizeof(c)); s[0]=0; for(int i=1;i<=n;i++) { cin>>a[i]; s[i]=s[i-1]+a[i]; c[i]=s[i]-s[i-lowbit(i)]; } for(int i=1;i<=m;i++) { int q=2; if(q==1) { int x,y; cin>>x>>y; int j=x; while(j<=n) { c[j]+=y; j+=lowbit(j); } } else { int x=1,y=2;//求a[1]+a[2]的和 int s1=0,s2=0,p=x-1; while(p>0) { s1+=c[p]; p-=lowbit(p); } p=y; while(p>0) { s2+=c[p]; p-=lowbit(p); } o++; ans[o]=s2-s1; } } for(int i=1;i<=o;i++) cout<<ans[i]<<endl; return 0; }
4.Splay解法:因为加法满足交换律,所以我们可以把序列翻转一下,所求的总和不变,代码如下:
#include <bits/stdc++.h> #define ll long long #define N 100000 using namespace std; int sz[N], rev[N], tag[N], sum[N], ch[N][2], fa[N], val[N]; int n, m, rt, x; void push_up(int x){ sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1; sum[x] = sum[ch[x][1]] + sum[ch[x][0]] + val[x]; } void push_down(int x){ if(rev[x]){ swap(ch[x][0], ch[x][1]); if(ch[x][1]) rev[ch[x][1]] ^= 1; if(ch[x][0]) rev[ch[x][0]] ^= 1; rev[x] = 0; } if(tag[x]){ if(ch[x][1]) tag[ch[x][1]] += tag[x], sum[ch[x][1]] += tag[x]; if(ch[x][0]) tag[ch[x][0]] += tag[x], sum[ch[x][0]] += tag[x]; tag[x] = 0; } } void rotate(int x, int &k){ int y = fa[x], z = fa[fa[x]]; int kind = ch[y][1] == x; if(y == k) k = x; else ch[z][ch[z][1]==y] = x; fa[x] = z; fa[y] = x; fa[ch[x][!kind]] = y; ch[y][kind] = ch[x][!kind]; ch[x][!kind] = y; push_up(y); push_up(x); } void splay(int x, int &k){ while(x != k){ int y = fa[x], z = fa[fa[x]]; if(y != k) if(ch[y][1] == x ^ ch[z][1] == y) rotate(x, k); else rotate(y, k); rotate(x, k); } } int kth(int x, int k){ push_down(x); int r = sz[ch[x][0]]+1; if(k == r) return x; if(k < r) return kth(ch[x][0], k); else return kth(ch[x][1], k-r); } void split(int l, int r){ int x = kth(rt, l), y = kth(rt, r+2); splay(x, rt); splay(y, ch[rt][1]); } void rever(int l, int r){ split(l, r); rev[ch[ch[rt][1]][0]] ^= 1; } void add(int l, int r, int v){ split(l, r); tag[ch[ch[rt][1]][0]] += v; val[ch[ch[rt][1]][0]] += v; push_up(ch[ch[rt][1]][0]); } int build(int l, int r, int f){ if(l > r) return 0; if(l == r){ fa[l] = f; sz[l] = 1; return l; } int mid = l + r >> 1; ch[mid][0] = build(l, mid-1, mid); ch[mid][1] = build(mid+1, r, mid); fa[mid] = f; push_up(mid); return mid; } int asksum(int l, int r){ split(l, r); return sum[ch[ch[rt][1]][0]]; } int main(){ n = 2; rt = build(1, n+2, 0); for(int i = 1; i <= n; i++){ scanf("%d", &x); add(i, i, x); } rever(1, n); printf("%d\n", asksum(1, n)); return 0; }
5.Dijkstra+STL的优先队列优化:代码如下:
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cctype> #include <climits> #include <algorithm> #include <map> #include <queue> #include <vector> #include <ctime> #include <string> #include <cstring> using namespace std; const int N=405; struct Edge { int v,w; }; vector<Edge> edge[N*N]; int n; int 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]; } int main() { int a,b; scanf("%d%d",&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("%d",Dijkstra(0,2)); return 0; }
6.模拟:模拟人工运算方法,代码如下:
#include <iostream> #include <cmath> using namespace std; int fu=1,f=1,a,b,c=0; int main() { cin>>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){cout<<b;return 0;} if(b==0){cout<<a;return 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; cout<<c; return 0; }
7.字典树:代码如下:
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; struct node{ int str[26]; int sum; }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; } int main() { for(int i=1;i<=2;i++) { f1=false; scanf("%s",str1); built(); if(f1) ss-=query(); else ss+=query(); } printf("%d",ss); return 0; }
8.二进制:用二进制的计算方法计算,代码如下:
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> using namespace std; int main() { int a,b,s=0,s1=0,i=0,na=0,nb=0; cin>>a>>b; if(a<=0) na=1,a*=-1; while(a!=0) { if(a%2!=0) s+=pow(2,a%2*i); a/=2; i++; } i=0; if(na==1) s*=-1; if(b<=0) nb=1,b*=-1; while(b!=0) { if(b%2!=0) s1+=pow(2,b%2*i); b/=2; i++; } if(nb==1) s1*=-1; cout<<s+s1;; return 0; }
9.最小生成树:代码如下:
#include <cstdio> #include <algorithm> #define INF 2140000000 using namespace std; 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];} int main(){ for (i=1;i<=10;i++) f[i]=i; for (i=1;i<=2;i++){ scanf("%d",&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("%d\n",ans); }
其他语言解法
1.Pascal
var a, b: longint; begin readln(a,b); writeln(a+b); end.
2.Python2
s = raw_input().split() print int(s[0]) + int(s[1])
3.Python3
s = input().split() print(int(s[0]) + int(s[1]))
4.Java
import java.io.*; import java.util.*; public class Main { public static void main(String args[]) throws Exception { Scanner cin=new Scanner(System.in); int a = cin.nextInt(), b = cin.nextInt(); System.out.println(a+b); } }
5.JavaScript (Node.js)
const fs = require('fs') const data = fs.readFileSync('/dev/stdin') const result = data.toString('ascii').trim().split(' ').map(x => parseInt(x)).reduce((a, b) => a + b, 0) console.log(result) process.exit()
6.php
<?php $input = trim(file_get_contents("php://stdin")); list($a, $b) = explode(' ', $input); echo $a + $b;
以上是我想出来的亿种方法,希望大家点个赞支持一下
信息
- ID
- 56
- 时间
- 1000ms
- 内存
- 1024MiB
- 难度
- 1
- 标签
- 递交数
- 9073
- 已通过
- 4043
- 上传者