启发式题解：AT_arc212_a [ARC212A] Four TSP

· · 算法·理论

:::info[启发式题解说明]{open}

这是一篇启发式题解。

本题解会通过适当的提示，带领大家一步步吃透本题。

:::

依旧 ARC T1 放水。

:::info[Hint 1]

先打暴力，然后优化。

:::

:::info[Hint 2]

合理利用顶点数为 4 这个性质。

:::

:::info[Hint 3]

是不是可以合并一些边的枚举？

:::

::::success[题解]

接着 Hint 3。

我们设图上四个点从左上开始依次为 A、B、C、D。

则很明显，可以合并对 AB、CD 的枚举，对 AC、BD 的枚举，对 AD、BC 的枚举。

因此，其实只需要枚举前 2 组边权值和 v_1、v_2，第 3 组边权值和 v_3 即可确定。计算答案时要乘上 v_1-1、v_2-1、v_3-1，这相当于拆这些组为两条单边。注意取 \max，以及判重。

:::info[参考代码]

#include<bits/stdc++.h>
using namespace std;
typedef long long li;
const int moi=998244353;
int h(int x, int y) {
    return (x%moi+y%moi)%moi;
}
int g(int x, int y) {
    return ((x%moi-y%moi)%moi+moi)%moi;
}
int f(int x, int y) {
    return (((1ll*x)%moi)*(y%moi))%moi;
}
int ans;
int main() {
    int n;
    cin >> n;
    int lm=n/3;
    for(int k1=2; k1<=lm; k1++) {
        int ly=((n-k1)>>1);
        for(int k2=k1; k2<=ly; k2++) {
            int ci=1;
            int cnt=0;
            if(k1^k2) cnt++;
            if(k1^(n-k1-k2)) cnt++;
            if((n-k1-k2)^k2) cnt++;
            if(cnt>2) ci=6;
            else if(cnt) ci=3;
            ans=h(ans, f(f(f(k1-1, k2-1), f(n-k1-k2-1, ci)), k1+k2));
        }
    }
    cout << ans;
    return 0;
}
//咕咕咕！

:::

::::