题解：P15630 [2019 KAIST RUN Spring] Gosu

· · 题解

link

Solution

Part 1: Floyd，Dijkstra，和 BFS

我们可以把这个当成一个图，然后对每个人跑一遍最短路，最短路中最长的路最短的那个人就是 Gosu。

结果与时间复杂度：

  1. Floyd：O(n^3)；
  2. Dijkstra：O(n^3 \log n)；
  3. BFS（普通）：O(n^3)；
  4. BFS（带剪枝）：O(n^2) 到 O(n^3)。

没有一个是过的。

Part 2: 正解

可以证明如果一个人的获胜次数最多，那么他的弱点要么是 1，要么是 2。

:::info[证明] 假设获胜最多的人 i 的弱点大于 2，那么一定有一个人 j，使得 d(i,j) > 2。如果被 i 打败的人 k 能打败 j，那么 d(i,j)=2，则 j 打败了所有 i 打败的人，还打败了 i，获胜次数比 i 还多，矛盾。

所以获胜次数最多的人的弱点要么是 1，要么是 2。 :::

如果获胜最多的人把其他人都击败了，那么他的弱点是 1，如果不是，那么是 2。因为比 2 小的正整数只有 1，所以不管怎样获胜最多的人都是 Gosu。

Code

:::success[code]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
typedef double db;
typedef __int128 i128;
const ll inf=9e18;
const i128 Inf=1e35;
str s;
ll n,mx,pos;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s;
        ll cnt=count(s.begin(),s.end(),'W');
        if(cnt==n-1)
        {
            cout<<"1 "<<i;
            return 0;
        }
        if(cnt>mx) mx=cnt,pos=i;
    }
    cout<<"2 "<<pos;
}

:::