题解：P10695 [SNCPC2024] 商路

· · 题解

尝试提供比较简单的思考方式。

题意

在圆的 k 个等分点中选出 n 个关键点，一条线段合法当且仅当它连接两个关键点且对它连接的某个关键点而言，另一个点是最远关键点。

选出最多的合法线段使它们除了端点外两两不交。

分析

你手玩了几个数据，发现答案不容易很大，你思考如何让答案大一点，于是你写了一个暴力对拍：代码。

你尝试找一些答案不太小的数据，于是用：

int calc(int S)
{
    return (S&(S-1))!=0;
}

当然这样子错误率很高：k=10 时有 932 组错解。

手玩小数据即可发现，很多数据的答案最后所有的线段共用端点（尤其是你筛选出答案比较大的情况时），既然这样，求出所有的合法线段，组成一个无向图，找到入度最大的点作为答案输出似乎是一种不错的策略，于是你改成：

int b[N];
bool c[N][N];
int calc(int S)
{
    fill(b,b+k,0);
    up(i,0,k-1)fill(c[i],c[i]+k,0);
    up(i,0,k-1)if(S>>i&1)
    {
        int mx=0;
        up(j,0,k-1)
            if(S>>j&1)mx=max(mx,dis(i,j));
        up(j,0,k-1)
            if((S>>j&1)&&dis(i,j)==mx&&i!=j&&!c[j][i])
                ++b[i],++b[j],c[i][j]=1;
    }
    return *max_element(b,b+k);
}

虽然连样例都无法正确通过，但是在 k=10 的时候只有 30 个反例，且反例都只有三个点，且所有三条边都被选入。

考虑只有三个点的情况，一共有三条边，你发现如果最短边小于次短边，那么只可能用到两条边，故判断最短边是否恰好等于次短边，如果是，就在原本答案上加一。

int n,a[N],b[N];
bool c[N][N];
int calc(int S)
{
    n=0;
    up(i,0,k-1)
        if(S>>i&1)a[++n]=i;
    up(i,1,n)fill(c[i],c[i]+n+1,0);
    fill(b,b+n+1,0);
    up(i,1,n)
    {
        int mx=0;
        up(j,1,n)mx=max(mx,dis(a[i],a[j]));
        up(j,1,n)if(dis(a[i],a[j])==mx&&i!=j&&!c[j][i])
                ++b[i],++b[j],c[i][j]=1;
    }
    bool ok=n==3;
    if(ok)
    {
        int g[3]={a[2]-a[1],a[3]-a[2],a[1]+k-a[3]};
        sort(g,g+3);
        ok=g[0]==g[1];
    }
    return *max_element(b,b+n+1)+ok;
}

该代码没有拍出错，我们将原本的枚举改为双指针（因为所有点到某个点的距离先增大后减小），时间复杂度 O(n)。

#include<bits/stdc++.h>
#define up(a,b,c) for(int a=b;a<=c;++a)
const int N=11e4;
using namespace std;
int k,n,a[N],d[N],b[N];
int dis(int u,int v)
{
    u=a[u],v=a[v];
    if(u>v)swap(u,v);
    return min(v-u,u+k-v);
}
int main()
{
    cin>>k>>n;
    up(i,1,n)cin>>a[i];
    int j=1;
    up(i,1,n)
    {
        while(dis(i,j)<=dis(i,j%n+1))
        {
            if(dis(i,j)==dis(i,j%n+1)&&dis(i,j)!=d[j])++b[i],++b[j];
            j=j%n+1;
        }
        d[i]=dis(i,j);
        if(d[i]!=d[j])++b[i],++b[j];
    }
    bool ok=n==3;
    if(ok)
    {
        int g[3]={a[2]-a[1],a[3]-a[2],a[1]+k-a[3]};
        sort(g,g+3);
        ok=g[0]==g[1];
    }
    cout<<*max_element(b,b+n+1)+ok;
    return 0;
}

这份代码可以通过本题。