洛谷P9088 「SvR-2」1+2=3 题解

题意：

你有一些木棒，每个木棒左边有一个数，右边有一个数，数只有 \(0,1,2\)，你要将所有木棒拼起来，使相邻的数和为 \(3\) 的对数最大。

例如，\(1\text{ - }2\) 和 \(1\text{ - }0\) 两个木棒，如果按 \(1\text{ - }0,1\text{ - }2\) 这样拼，相邻的数和为 \(3\) 的对数是 \(0\)；而按 \(1\text{ - }{\textbf2},{\textbf1}\text{ - }0\) 这样拼相邻的数和为 \(3\) 的对数是 \(1\)，因为 \(2+1=3\)。

输入格式：

本题有多组数据。

输入的第一行一个正整数表示数据组数 \(T\)。

对于每组数据，一行 \(9\) 个非负整数，分别表示 \(0\text{ - }0,0\text{ - }1,0\text{ - }2,1\text{ - }0,1\text{ - }1,1\text{ - }2,2\text{ - }0,2\text{ - }1,2\text{ - }2\) 型木棒的个数。

输出格式：

\(T\) 行，每行一个整数表示答案。

数据规模与约定：

对于全部数据，保证 \(1\le T\le 10^5\)，记 \(a_{i,j}\) 表示 \(i\text-j\) 木棒的个数，保证 \(0\le a_{i,j}\le 10^9\)。

考虑用分类讨论来构造最优解。

容易发现，不产生答案的拼接是劣的，因此我们优先考虑可以产生贡献的拼接。

手动模拟一下，可以发现有以下几个性质：

设有 \(n\) 个 1-2 或 2-1 型的木棒，考虑以 1-2 + 1-2 + ... + 1-2 的形式合并，则可以产生 \(n-1\) 的贡献
设有 \(a\) 个 1-1 和 \(b\) 个 2-2 。不妨设 \(a > b\) ，则我们可以以 1-1 + 2-2 + 1-1 + ... + 1-1 的形式合并，此时 \(a\) 变成了 \(a-b\) ，\(b\) 变成了 \(0\) ，贡献为 \(2b\) ；当 \(a < b\) 时同理。

特别地，当 \(a=b\) 时，我们可以任意合并为一个 1-2 或 2-1。
若 \(a,b\) 不同时为 \(0\) ，且 1-2 或 2-1 也不同时为 \(0\) ，则可以通过 1-1 + 1-2 = 1-2 的方式合并，此时贡献为 \(1\)
0-0 对结果不会产生任何影响。

另外，我们可以从中得出一些结论：

在合并后，1-1 和 2-2 至多有其中一种，且 1-2 和 2-1 不同时为 \(0\) 当且仅当 1-1 和 2-2 的数量相等。

考虑分类讨论 1-1 和 2-2 的情况：

\(a > b\)
\(a < b\)
\(a=b > 0\)
\(a=b=0\)

对于剩余的少量 1-1, 2-2, 1-2, 2-1，尽可能将它们与 0-X 或 X-0 配对。

尽可能如此配对后，只需将剩余的 0-2 + 1-0 = 0-0 以及 0-1 + 2-0 = 0-0 配对，就是最优解。

时间复杂度 \(\mathcal{O}(T)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int a[5][5];
void solve()
{
    int res = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++) cin >> a[i][j];
    if(a[1][2]) { res += a[1][2] - 1; a[1][2] = 1; }
    if(a[2][1]) { res += a[2][1] - 1; a[2][1] = 1; }

    if(a[1][1] > a[2][2])
    {
        res += a[2][2] * 2; a[1][1] -= a[2][2];
        if(a[1][2]) ++res;
        if(a[2][1]) ++res;
        int t = min(a[0][2], a[1][1]);
        res += t; a[0][1] += t; a[0][2] -= t; a[1][1] -= t;
        t = min(a[1][1], a[2][0]);
        res += t; a[1][0] += t; a[1][1] -= t; a[2][0] -= t;
        res += min(a[0][1], a[2][0]) + min(a[0][2], a[1][0]);
    }else if(a[1][1] < a[2][2])
    {
        res += a[1][1] * 2; a[2][2] -= a[1][1];
        if(a[1][2]) ++res;
        if(a[2][1]) ++res;
        int t = min(a[0][1], a[2][2]);
        res += t; a[0][2] += t; a[0][1] -= t; a[2][2] -= t;
        t = min(a[2][2], a[1][0]);
        res += t; a[2][0] += t; a[2][2] -= t; a[1][0] -= t;
        res += min(a[0][1], a[2][0]) + min(a[0][2], a[1][0]);
    }else
    {
        if(a[1][1])
        {
            if(a[1][2]) ++res;
            if(a[2][1]) ++res;
            res += a[1][1] * 2 - 1;
            if(a[0][2] || a[1][0] || a[0][1] || a[2][0]) ++res;
            res += min(a[0][2], a[1][0]) + min(a[0][1], a[2][0]);
        }else
        {
            res += 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]);
            res += 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]);
            res += min(a[0][2], a[1][0]) + min(a[0][1], a[2][0]);
        }
    }
    cout << res << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int Q; cin >> Q; while(Q--) solve();
    return 0;
}