P1001 A+B Problem

· · 题解

P1001 - A+B Problem

输入两个整数 a,b，输出它们的和（|a|,|b|\leq 10^9）。

注意

  1. Pascal 使用 integer 会爆掉哦！
  2. 有负数哦！
  3. C/C++ 的 main 函数必须是 int 类型，而且最后要 return 0。这不仅对洛谷其他题目有效，而且也是 NOIP/NOI/CSP 比赛的要求！

好吧，同志们，我们就从这一题开始，向着大牛的路进发。

任何一个伟大的思想，都有一个微不足道的开始。

神题，做法多种多样。

首先，我们可以发现这题有个最简单的做法，就是读入 a,b，输出 a+b 即可。代码如下：

namespace solver1
{
    int a,b;

    inline void solve()
    {
        a=read(),b=read();
        cout << a+b << endl;
    }
}

虽然能 AC，但是洛谷上很多神题，因此我觉得这题不应该这么简单。

首先，这个题很明显可以不用加号，因此有如下做法（自欺欺人）：

namespace solver2
{
    int a,b;

    inline void solve()
    {
        a=read(),b=read();
        cout << a-(-b) << endl;
    }
}

我们还可以考虑如何不用 +,- 两个符号完成这个题。考虑一下进行加法的本质是每一个位上的进位，而要产生进位，也就是两个对应位上都是 1 才会产生进位。这个是可以通过 a&b 得到的。而如果我们进行 a^b 则可以得到两个位在不考虑其他位上的进位的时候的加法计算结果。因为 0^1=1^0=1，相当于没有进位的加 1，而 1^1=0，相当于 1+1 产生进位，而 0^0=0 相当于两位都是 0，相加也是 0。因此我们可以使用异或以及与运算完成加法。具体请看代码。

namespace solver3
{
    int a,b;

    inline void solve()
    {
        a=read(),b=read();
        while (b!=0)
        {
            int _a=a^b;
            int _b=(a&b)<<1;
            a=_a;
            b=_b;
        }
        cout << a << endl;
    }
}

接下来有一些别的方法。

首先，如果我们有两个集合 \{A\},\{B\}，其中 |A|=a,|B|=b，我们把两个集合合并，得到集合的秩的大小，那么就可以很好地完成了。

反正我们也不知道我们集合里面是什么东西就干脆用并查集吧，不用开个 set。

namespace solver4
{
    int a[5],fa[5],size[5];

    inline void Init()
    {
        for (int i=1;i<=2;i++)
        {
            fa[i]=i;
            size[i]=a[i];
        }
    }

    inline int Find(int x)
    {
        return fa[x]==x?x:fa[x]=Find(fa[x]);
    }

    inline void Merge(int x,int y)
    {
        int fx=Find(x),fy=Find(y);
        if (fx!=fy)
        {
            fa[fy]=fx;
            size[fx]+=size[fy];
        }
    }

    inline void solve()
    {
        a[1]=read(),a[2]=read();
        Init();
        Merge(1,2);
        cout << size[1] << endl;
    }
}

我们还可以考虑，如果目前有一张图，有 3 个节点 1 \to 2,2 \to 3，那么令每条边的边权分别是 a,b，那么最后的答案就是这个图的最小生成树，当然最大生成树也是可以的。因为我只会 kruskal，所以代码如下：

namespace solver5
{
    int a[5],fa[5];

    struct node
    {
        int u,v,w;
        bool operator < (const node &rhs) const
        {
            return w<rhs.w;
        }
    }edge[5];

    inline void Init()
    {
        for (int i=1;i<=2;i++)
            fa[i]=i;
    }

    inline int Find(int x)
    {
        return fa[x]==x?x:fa[x]=Find(fa[x]);
    }

    inline void Merge(int x,int y)
    {
        int fx=Find(x),fy=Find(y);
        if (fx!=fy)
            fa[fy]=fx;
    }

    inline void solve()
    {
        a[1]=read(),a[2]=read();
        Init();
        sort(a+1,a+3);
        edge[1]={1,2,a[1]};
        edge[2]={2,3,a[2]};
        int ans=0;
        for (int i=1;i<=2;i++)
        {
            auto e=edge[i];
            int u=edge[i].u,v=edge[i].v;
            int fu=Find(u),fv=Find(v);
            if (fu!=fv)
            {
                ans+=e.w;
                Merge(fu,fv);
            }
        }
        cout << ans << endl;
    }
}

当然，如果你真建立出这张图，那么我们甚至可以使用 dijkstra 跑从 1 \to 3 的最短路径，也可以算出我们要求的答案。注意：dijkstra 其实不能跑带负权的最短路哦。

namespace solver6
{
    struct node
    {
        int to,dis;

        bool operator < (const node &rhs) const
        {
            return dis<rhs.dis;
        }
    };

    priority_queue <node> q;

    vector <node> G[5];

    int dis[5],vis[5];

    inline void Dijkstra()
    {
        memset(dis,0x7f,sizeof(dis));
        q.push({1,0});
        dis[1]=0;
        while (!q.empty())
        {
            node rhs=q.top();
            q.pop();
            int u=rhs.to;
            if (vis[u])
                continue;
            for (int i=0;i<G[u].size();i++)
            {
                rhs=G[u][i];
                int v=rhs.to,d=rhs.dis;
                if (dis[v]>dis[u]+d)
                {
                    dis[v]=dis[u]+d;
                    q.push({v,dis[v]});
                }
            }
        }
    }

    inline void solve()
    {
        int a=read(),b=read();
        G[1].push_back({2,a});
        G[2].push_back({3,b});
        Dijkstra();
        cout << dis[3] << endl;
    }
}

当然，有一些很奇妙的方法。我们考虑一下网络流解法。当然因为里面有负权，所以应该取绝对值然后判断要不要减回去。

第一种解法是最大流。两条边流量分别是 a,b，这样的确就可以得到 a+b。

namespace solver7
{
    int head[50],tail[50],next[50],r[50],ecnt=1,s=1,t=4,d[50],cur[50],flow;

    inline void link(int u,int v,int w)
    {
        next[++ecnt]=head[u];
        head[u]=ecnt;
        tail[ecnt]=v;
        r[ecnt]=w;
        next[++ecnt]=head[v];
        head[v]=ecnt;
        tail[ecnt]=u;
        r[ecnt]=0;
    }

    inline bool BFS()
    {
        queue <int> q;
        q.push(t);
        memset(d,0,sizeof(d));
        d[t]=1;
        while (!q.empty())
        {
            int u=q.front();
            q.pop();
            for (int i=head[u];i;i=next[i])
            {
                int v=tail[i];
                if (d[v]==0 && r[i^1]>0)
                {
                    d[v]=d[u]+1;
                    q.push(v);
                }
            }
        }
        return d[s]>0;
    }

    inline int DFS(int u,int budget)
    {
        if (u==t)
            return budget;
        int res=0;
        for (int &e=cur[u];e;e=next[e])
        {
            int v=tail[e];
            if (d[v]+1==d[u] && r[e]>0)
            {
                int delta=DFS(v,min(r[e],budget));
                if (delta)
                {
                    r[e]-=delta;
                    r[e^1]+=delta;
                    flow+=delta;
                    budget-=delta;
                    res+=delta;
                }
            }
        }
        return res;
    }

    inline int Dinic()
    {
        int ans=0;
        while (BFS())
        {
            for (int i=s;i<=t;i++)
                cur[i]=head[i];
            ans+=DFS(s,1145141919);
        }
        return ans;
    }

    inline void solve()
    {
        int f=0;
        int a=read(),b=read();
        if (a<0)
        {
            a=abs(a);
            f|=1;
        }
        if (b<0)
        {
            b=abs(b);
            f|=2;
        }
        link(1,2,a);
        link(1,3,b);
        link(2,4,1145141919);
        link(3,4,1145141919);
        int ans=Dinic();
        if (f&1)
            ans-=2*a;
        if (f&2)
            ans-=2*b;
        cout << ans << endl;
    }
}

第二种解法是费用流。我们考虑一条边的费用是 a，一条边的费用是 b，单位流量的费用为 1，则可以使用最小费用最大流解决，在这里我采用的是原始对偶 （primal-dual） 算法求费用流。好像写原始对偶是不用判负了（

namespace solver8
{
    struct node
    {
        int to,dis;
        bool operator < (const node &rhs) const
        {
            return dis>rhs.dis;
        }
    };

    int d[10],preu[10],pree[10];

    bool inq[10];

    int e=1,w[10],r[10],first[10],next[10],cost=0,flow=0,tail[10],h[10];

    void link(int u,int v,int re,int weight)
    {
        next[++e]=first[u];
        first[u]=e;
        tail[e]=v;
        r[e]=re;
        w[e]=weight;
        next[++e]=first[v];
        first[v]=e;
        tail[e]=u;
        r[e]=0;
        w[e]=-weight;

    }

    int s=1,t=3;

    bool vis[100050];

    inline void dijkstra()
    {
        for (int i=1;i<=5;i++)
        {
            vis[i]=0;
            d[i]=INT_MAX;
        }
        d[s]=0;
        priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
        q.empty();
        q.push(pair<int,int>(0,s));
        while (!q.empty())
        {
            pair <int,int> rhs=q.top();
            q.pop();
            int u=rhs.second;
            if (vis[u])
                continue;
            for (int i=first[u];i;i=next[i])
            {
                int v=tail[i];
                if (r[i]>0 && d[v]>d[u]+w[i]+h[u]-h[v])
                {
                    d[v]=d[u]+w[i]+h[u]-h[v];
                    preu[v]=u;
                    pree[v]=i;
                    q.push(pair<int,int>(d[v],v));
                }
            }
        }
    }

    inline void MinCostMaxFlow()
    {
        memset(h,0,sizeof(h));
        while (1)
        {
            dijkstra();
            if (d[t]==INT_MAX)
                break;
            else
            {
                for (int u=1;u<=3;u++)
                    h[u]+=d[u];
                int delta=INT_MAX;
                for (int u=t;u!=s;u=preu[u])
                {
                    int e=pree[u];
                    delta=min(delta,r[e]);
                }
                flow+=delta;
                cost+=delta*h[t];
                for (int u=t;u!=s;u=preu[u])
                {
                    int e=pree[u];
                    r[e]-=delta;
                    r[e^1]+=delta;
                }
            }
        }
    }

    inline void solve()
    {
        int a=read(),b=read();
        link(1,2,1,a);
        link(2,3,1,b);
        MinCostMaxFlow();
        cout << cost << endl;
    }
}

接下来我们考虑把它丢到序列上。

我们假设有一个数列 \{A_n\}，那么我们令 A_1=a,A_2=b。

我们把数列做个前缀和，再用 S_2-S_0 的差分，就可以得到 a+b 的大小。

namespace solver9
{
    int a[5],S[5];

    inline void solve()
    {
        for (int i=1;i<=2;i++)
            a[i]=read();
        for (int i=1;i<=2;i++)
            S[i]=S[i-1]+a[i];
        cout << S[2]-S[0] << endl;
    }
}

当然如果只是读入 a[i] 的话显得不高级。我们考虑几个可以维护区间的数据结构。

首先是树状数组，单点修改，区间查询和：

namespace solver10
{
    int f[10];

    inline int Lowbit(int x)
    {
        return x&-x;
    }

    inline void Change(int k,int x)
    {
        while (k<=5)
        {
            f[k]+=x;
            k+=Lowbit(k);
        }
    }

    inline int Query(int k)
    {
        int ans=0;
        while (k)
        {
            ans+=f[k];
            k-=Lowbit(k);
        }
        return ans;
    }

    inline void solve()
    {
        Change(1,read());
        Change(2,read());
        cout << Query(2) << endl;
    }
}

然后是线段树区间修改区间求和。

namespace solver11
{
    struct SegTree
    {
        int l,r;
        long long val,tag;
    }t[50];

    inline void Push_Up(int id)
    {
        t[id].val=t[id<<1].val+t[id<<1|1].val;
    }

    inline void Push_Down(int id)
    {
        if (t[id].tag)
        {
            int mid=(t[id].l+t[id].r)>>1;
            t[id<<1].tag+=t[id].tag;
            t[id<<1|1].tag+=t[id].tag;
            t[id<<1].val+=(mid-t[id].l+1)*t[id].tag;
            t[id<<1|1].val+=(t[id].r-mid)*t[id].tag;
            t[id].tag=0;
        }
    }

    inline void Build(int id,int l,int r)
    {
        t[id].l=l;
        t[id].r=r;
        if (l==r)
            return;
        int mid=(l+r)>>1;
        Build(id<<1,l,mid);
        Build(id<<1|1,mid+1,r);
        Push_Up(id);
    }

    inline void Change(int id,int l,int r,int val)
    {
        if (l<=t[id].l && t[id].r<=r)
        {
            t[id].tag+=val;
            t[id].val+=val*(t[id].r-t[id].l+1);
            return;
        }
        Push_Down(id);
        int mid=(t[id].l+t[id].r)>>1;
        if (r<=mid)
            Change(id<<1,l,r,val);
        else if (l>mid)
            Change(id<<1|1,l,r,val);
        else
        {
            Change(id<<1,l,mid,val);
            Change(id<<1|1,mid+1,r,val);
        }
        Push_Up(id);
    }

    inline long long Query(int id,int l,int r)
    {
        if (l<=t[id].l && t[id].r<=r)
            return t[id].val;
        Push_Down(id);
        int mid=(t[id].l+t[id].r)>>1;
        if (r<=mid)
            return Query(id<<1,l,r);
        else if (l>mid)
            return Query(id<<1|1,l,r);
        else
            return Query(id<<1,l,mid)+Query(id<<1|1,mid+1,r);
    }

    inline void solve()
    {
        Build(1,1,2);
        Change(1,1,1,read());
        Change(1,2,2,read());
        cout << Query(1,1,2) << endl;
    }
}

那么平衡树也可以做。咕咕咕。