题解P6853

Binah · 2020-10-09 11:45:35 · 题解

大概是目前唯一一篇带证明的题解吧

趁着没有题解赶紧来一篇

以下 sum(f(i)) 均为 \Sigma_{i=1}^nf(i)

因为 n<=20 没有点数限制,以下证明均为 n>=21 的情况

首先,题意里面的"路径"是很丑陋的,我们尝试简化一下题意

我们尝试把每一条路径对应成一个点,两个路径相连则把他们连上一条边

显然最优情况下每个车站都经过三条路径

则:对于每一个车站,他被路径 a,b,c 经过,则相当于把 ab,bc,ca 连上

现在考虑题目的第三条限制:每两个点都有一个点和他们都相连

记三元组 (a,b,c) 为一组使 a,b 均和 c 相连的 a,b,c

其中 (a,b,c)=(x,y,z) 等价于无序对 (a,b)=(x,y) 且 c=z

由于对每个不同的 (a,b),都存在 c 与 a,b 相连

则我们有: s>=C_{n}^2

对于一个点 i,记它的度数为 p[i] (算上重边)

则使得 c=i 的 (a,b,c) 有 C_{p[i]}^2 个

所以:sum(C_{p[i]}^2))>=C_{n}^2

又每一个点 i 被至少两个车站经过,所以 p[i]>=4

由简单的数学运算(或者使用人类的直觉),可以知道: 使得 sum(p[i]) 最小且 sum(C_{p[i]}^2)>=C_{n}^2 的p满足:

由 C_{p[1]}^2+6n-6>=C(n,2)

又因为每个 m 连了三条边,即:sum(p[i])=6m (每条边从两端各计算一次)

所以 m>=sum(p[i])/6>=(5n-12)/6,即标答 ans>=5n/6-2

接下来给出一组 m 接近 5n/6 的构造:

把车站分成两组:

组 1:第 k 个车站连接 1,2k,2k+1(k<=n/2),2k=n 时将 2k+1 视为 2

组 2:第 k 个车站连接 3k-2,3k-1,3k(k<=(n+2)/3),3k-x>n 时,视为 3k-n-x

此时至多出现 (n/2+1)+(n/3+1)=5n/6+2 个车站 由 ans>=5n/6-2 得: w1>=5n/6+3>5n/6+2

所以,我们确保了这个程序完美满足要求了

最后,放代码了

#include <bits/stdc++.h>
//#include <windows.h>
//#define int long long
using namespace std;
#define N 4001
vector<int>mp[N];
int a[N],b[N],c[N];
int top=0;
int n;
int main()
{
    scanf("%d",&n);
    for(int i=2; i<=n; i+=2)//处理组1的车站
    {
        top++;
        a[top]=1;
        b[top]=i;
        c[top]=i+1;
        if(i==n)
        {
            c[top]=2;
        }
    }
    for(int i=2; i<=n; i+=3)//处理组2的车站
    {
        top++;
        a[top]=i;
        b[top]=i+1;
        if(i+1>=n+1)
        {
            b[top]-=n;
        }
        c[top]=i+2;
        if(i+2>=n+1)
        {
            c[top]-=n;
        }
    }
    for(int i=1; i<=top; i++)//把车站信息存进路径
    {
        mp[a[i]].push_back(i);
        mp[b[i]].push_back(i);
        mp[c[i]].push_back(i);
    }
    printf("%d\n",top);
    for(int i=1; i<=n; i++)
    {
        printf("%d ",mp[i].size());
        for(int j=0; j<mp[i].size(); j++)
        {
            printf("%d ",mp[i][j]);
        }
        printf("\n");
    }
    return 0;
}

修正:34行敲成了i+2>=n+2,感谢@sxw2018的指正