恶搞开始 (新手勿进) :
目录:
- way 1 : (唯一一篇阳间的代码)
- way 2 : (LCT)
- way 3 : (SPFA)
- way 4 : (Floyd)
- way 5 : (递归)
- way 6 : (压位高精)
- way 7 : (树状数组)
- way 8 : (Splay)
- way 9 : (Dijkstra+STL的优先队列优化)
- way 10 : (二分)
- way 11 : (字典树)
- way 12 : (最小生成树)
- way 13 : (二进制)
- way 14 : (线段树)
-
way 15 : (main当函数用,没想到吧)
-
way 1 : (唯一一篇阳间的代码)
#include <iostream>
using namespace std;
int main() {
int a,b;
cin >> a >> b;
cout << a+b;
return 0;
}
//更新了亿下题解
#include <iostream>
int main(){
int a,b;
std:: cin>>a>>b;
std:: cout<<a+b;
return 0;
}
- way 2 : (LCT)
#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);
//连边 Link
connect(A,B);
//断边 Cut
cut(A,B);
//再连边orz Link again
connect(A,B);
printf("%d\n",query(A,B));
return 0;
}
- way 3 : (SPFA)
#include<cstdio>
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);//1到2为a,2到3为b,1到3即为a+b……
printf("%d",SPFA(1,3));
return 0;
}
- way 4 : (Floyd)
#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]=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]);
cout<<dis[1][3];
return 0;
}
- way 5 : (递归)
#include<iostream>
using namespace std;
long long a,b,c;
long long dg(long long a){
if(a<=3){return a;}//防超时……
return (dg(a/2)+dg(a-a/2));
}
int main(){
cin>>a>>b;
c=dg(a)+dg(b);
cout<<c;
return 0;
}
- way 6 : (压位高精)
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#define p 8
#define carry 100000000
using namespace std;
const int Maxn=50001;
char s1[Maxn],s2[Maxn];
int a[Maxn],b[Maxn],ans[Maxn];
int change(char s[],int n[]) {
char temp[Maxn];
int len=strlen(s+1),cur=0;
while(len/p){
strncpy(temp,s+len-p+1,p);
n[++cur]=atoi(temp);
len-=p;
}
if(len){
memset(temp,0,sizeof(temp));
strncpy(temp,s+1,len);
n[++cur]=atoi(temp);
}
return cur;
}
int add(int a[],int b[],int c[],int l1,int l2) {
int x=0,l3=max(l1,l2);
for(int i=1;i<=l3;i++) {
c[i]=a[i]+b[i]+x;
x=c[i]/carry;
c[i]%=carry;
}
while(x>0){c[++l3]=x%10;x/=10;}
return l3;
}
void print(int a[],int len) {
printf("%d",a[len]);
for(int i=len-1;i>=1;i--)printf("%0*d",p,a[i]);
printf("\n");
}
int main() {
scanf("%s%s",s1+1,s2+1);
int la=change(s1,a);
int lb=change(s2,b);
int len=add(a,b,ans,la,lb);
print(ans,len);
return 0;
}
- way 7 : (树状数组)
#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;{
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;
}
- way 8 : (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;
}
- way 9 : (Dijkstra+STL的优先队列优化)
#include<bits/stdc++.h>
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;
}
- way 10 : (二分)
#include<cstdio>
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\n",c),0;
}if(l!=r)return printf("%d\n",r),0;
}
- way 11 : (字典树)
#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;
}
- way 12 : (最小生成树)
#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);
}
- way 13 : (二进制)
#include<bits/stdc++.h>
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;
}
- way 14 : (线段树)
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
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));
}
- way 15 : (main当函数用,没想到吧)
#include <cstdio>
int main(int a,int b)
{return (scanf("%d%d",&a,&b),printf("%d\n",a+b))&0;}
(一页的WA,把正确题解copy了下来,累死我啦!,不点个赞再走??
。。。
啧啧啧
咋,有看不懂的~~
鹅鹅鹅!
对 ,字典树那个这么想?
这其实很简单,这个字典树是存储字符的,这里把数字换成字符操作而已,两个字符减去‘0’’再进行操作,接下来的操作就类似高精度了。
高精度加法的一个模板
你也可以选择来我boke逛逛哈哈qaq
luogu
牛逼