题解：P13355 [GDCPC 2024] 循环赛

· · 题解

题意简述

用一张竞赛图表示循环赛结果，结点的出度就是得分。

要求任取 z+1 个结点，导出子图中都同时存在全胜者和全败者。求合法竞赛图中最少可能出现多少种不同出度。

解题思路

先处理 z=1。此时每次只选两个结点，两者之间必有一个胜者和一个败者，所以没有额外限制。

竞赛图的出度总和为 n(n-1)/2。当 n 为奇数时，存在每个结点出度都为 (n-1)/2 的正则竞赛图，答案可以为 1。当 n 为偶数时，平均出度不是整数，所有出度不可能相同；删除一个奇数阶正则竞赛图中的结点，可以得到只含两种出度的近正则竞赛图。因此：

\operatorname{ans}=1+[2\mid n]

下面设 z\ge2。

将竞赛图的强连通分量缩点。任意两个分量之间的边方向一致，否则两个分量能够互相到达。缩点后仍是一张竞赛图，又因为它是有向无环图，所以各分量构成唯一方向的全序。

按照后面的分量战胜前面的分量排列这些强连通分量。大小为 2 的竞赛图不强连通，因此每个分量的大小为 1 或至少为 3。

需要限制非单点强连通分量的位置。

强连通竞赛图存在经过全部结点的有向环，并且存在从 3 到分量大小的每一种长度的有向环。若某个分量大小超过 z，就在其中选择一个长度为 z+1 的有向环。环上每个结点至少有一场胜利和一场失败，所选结点中便没有全胜者和全败者，与题目条件矛盾。因此每个分量的大小都不超过 z。

考虑一个大小 s\ge3 的强连通分量。设它之前、之后分别有 L,R 个结点。

若 L+s>z，选择该分量的全部 s 个结点，再从前面选择 z+1-s 个结点。分量内部的哈密顿环保证每个分量结点都会输给另一个分量结点；前面的结点又会输给整个分量。因此所选结点中没有全胜者，产生矛盾。于是：

L+s\le z

对全败者作对称讨论，可以得到：

s+R\le z

令 p=n-z。因为 n=L+s+R，上面两个不等式等价于：

\begin{aligned} L & \ge p \\ R & \ge p \end{aligned}

也就是说，任何非单点分量之前和之后都至少有 p 个结点。因此，全序中最前面的 p 个结点和最后面的 p 个结点都只能各自构成单点分量。

若 2p\ge n，前后两段已经覆盖全部结点。此时所有强连通分量都是单点，整张竞赛图只能是传递竞赛图。其出度依次为 0,1,\dots,n-1，答案为 n。该条件也就是 2z\le n。

下面考虑 2p<n。除去前后各 p 个单点分量，中间还剩：

r=n-2p=2z-n

前 p 个单点分量的出度依次为 0,1,\dots,p-1。中间每个结点都战胜前面的 p 个结点，又输给后面的 p 个结点，所以它的总出度等于内部出度加 p，取值范围为 [p,p+r-1]。最后 p 个单点分量的出度依次为 p+r,p+r+1,\dots,n-1。

三段的出度范围互不相交。因此，前后两段固定产生 2p 种出度，只需让中间竞赛图的内部出度种类尽量少。

当 r 为奇数时，中间使用正则竞赛图，只产生一种内部出度。当 r 为偶数时，平均内部出度 (r-1)/2 不是整数，至少需要两种出度；从一个 r+1 阶正则竞赛图中删除一个结点，即可构造只含两种出度的近正则竞赛图。

由于 r=2z-n 与 n 的奇偶性相同，中间最少产生 1+[2\mid n] 种出度。总答案为：

2p+1+[2\mid n]=2(n-z)+1+[2\mid n]

还需验证上述构造满足题目条件。任取 z+1 个结点，其补集只有 n-z-1=p-1 个结点，所以前 p 个单点分量中至少选到一个结点，后 p 个单点分量中也至少选到一个结点。所选结点里，全序位置最靠后的单点战胜其余所有结点，最靠前的单点输给其余所有结点，条件成立。

综上：

\operatorname{ans}= \begin{cases} 1+[2\mid n] & z=1 \\ n & z\ge2,2z\le n \\ 2(n-z)+1+[2\mid n] & z\ge2,2z>n \end{cases}

每组数据只进行常数次运算，时间复杂度为 O(1)，空间复杂度为 O(1)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
ll solve(ll n,ll z)
{
    if(z==1)return 1+(n%2==0);
    ll p=n-z;
    if(2*p>=n)return n;
    return 2*p+1+(n%2==0);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        ll n,z;
        cin>>n>>z;
        cout<<solve(n,z)<<'\n';
    }
    return 0;
}