题解 P9088 1+2=3

· · 题解

原题链接

你说得对，但是《分类讨论》……后面忘了。

提供一个分类讨论的构造做法。

思路

首先木棒只有 9 种，要做的就是尽可能凑出 1+2=3 这样的数对，并求出最多配对数目，我们考虑用什么方式能简化这个问题。

目标就是尽可能地多配对，直到无法配对为止。

可以发现有这样三个性质：

  1. 假设有 k 个 1-2 或 2-1 型的木棒，那么我们能将它们通过首尾相接的方式变为 1 个 1-2 或 2-1 型的木棒，并且造成 k-1 的贡献；
  2. 假设有 a 个 1-1 和 b 个 2-2，不妨设 a>b，那么我们可以用 b+1 个 1-1 和 b 个 2-2 交错相接，变为 1 个 1-1，即 a \leftarrow a-b，并造成 2b 的贡献（a<b 时同理，特别地，a=b 时可在 1-2 与 2-1 中任选其一）；
  3. 若 1-1 和 2-2 中有一种初始数目不为 0，且此时 1-2 或 2-1 的数目不为 0，可以通过与 1-1 或 2-2 连接的方式消去，该操作不会影响 1-1 和 2-2 的数目，造成 1 的贡献（根据性质 1，最多剩 1 个）。

此外，0-0 不会对答案造成任何影响，这一点显然。

按以上性质操作，此时 1-1 和 2-2 最多只会有其中一种，且 1-2 和 2-1 的数目不为 0 当且仅当 1-1 和 2-2 的数目相等。

于是我们按照以下情况分类讨论：

对于剩余的 1-1,2-2,1-2,2-1，尽可能多地让 0-?,?-0 类型的木棒与之配对，在此之后，这些木棒若仍剩余，不会造成更多贡献，此时尽可能多地进行 0-1 与 2-0 以及 0-2 与 1-0 的配对即可。

以上是大概做法，写起来还是有不少细节，具体见代码。

代码

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define gc getchar
#define pc putchar
#define lowbit(x) (x&-x)
#define mp make_pair
#define fs first
#define sc second
using namespace std;
int T;
ll a[3][3],ans;
ll read()
{
    ll x=0,f=1;
    char ch=gc();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;
        ch=gc();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+(ch^48),ch=gc();
    }
    return x*f;
}
void print(ll x)
{
    if(x<0)pc('-'),x=-x;
    if(x>9)print(x/10);
    pc(x%10+48);
}
int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);

    T=read();
    while(T--)
    {
        ans=0;
        for(int i=0;i<=2;i++)
            for(int j=0;j<=2;j++)a[i][j]=read();

        if(a[1][2])ans+=a[1][2]-1,a[1][2]=1;
        if(a[2][1])ans+=a[2][1]-1,a[2][1]=1;

        if(a[1][1]>a[2][2])
        {
            ans+=a[2][2]*2,a[1][1]-=a[2][2];

            if(a[1][2])ans++;
            if(a[2][1])ans++;

            ll tmp=0;

            tmp=min(a[0][2],a[1][1]);
            ans+=tmp;
            a[0][1]+=tmp,a[0][2]-=tmp,a[1][1]-=tmp;

            tmp=min(a[1][1],a[2][0]);
            ans+=tmp;
            a[1][0]+=tmp,a[1][1]-=tmp,a[2][0]-=tmp;

            ans+=min(a[0][1],a[2][0])+min(a[0][2],a[1][0]);
        }
        else if(a[1][1]<a[2][2])
        {
            ans+=a[1][1]*2,a[2][2]-=a[1][1];

            if(a[1][2])ans++;
            if(a[2][1])ans++;

            ll tmp=0;

            tmp=min(a[0][1],a[2][2]);
            ans+=tmp;
            a[0][2]+=tmp,a[0][1]-=tmp,a[2][2]-=tmp;

            tmp=min(a[2][2],a[1][0]);
            ans+=tmp;
            a[2][0]+=tmp,a[2][2]-=tmp,a[1][0]-=tmp;

            ans+=min(a[0][1],a[2][0])+min(a[0][2],a[1][0]);
        }
        else
        {
            if(a[1][1])
            {
                if(a[1][2])ans++;
                if(a[2][1])ans++;

                ans+=a[1][1]*2-1;

                if(a[0][2]||a[1][0]||a[0][1]||a[2][0])ans++;

                ans+=min(a[0][2],a[1][0])+min(a[0][1],a[2][0]);
            }
            else
            {
                ans+=min(a[1][2],a[1][0])+min(a[0][1],a[2][1]);
                a[1][2]-=min(a[1][2],a[1][0]);
                a[2][1]-=min(a[0][1],a[2][1]);

                ans+=min(a[0][2],a[1][2])+min(a[2][1],a[2][0]);
                a[1][2]-=min(a[0][2],a[1][2]);
                a[2][1]-=min(a[2][1],a[2][0]);

                ans+=min(a[0][2],a[1][0])+min(a[0][1],a[2][0]);
            }
        }
        print(ans),pc('\n');
    }
    return 0;
}