115 条题解

  • 6
    @ 2023-8-27 8:30:20

    这题是入门的基础题,可以用很多方法求解,下面是最简单的几种方法,讲解与代码奉上。

    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;
    

    以上是我想出来的亿种方法,希望大家点个赞支持一下

    • @ 2024-5-6 13:51:40

      请不要抄袭洛谷题解,谢谢

信息

ID
56
时间
1000ms
内存
1024MiB
难度
1
标签
递交数
7089
已通过
3116
上传者