题解 P6867 【[COCI2019-2020#5] Politicari】

· · 题解

Solution

对于 35 pts 的数据

由于 k \le 10^5，直接按题意模拟即可。

对于所有的数据

由于 1 \le k \le 10^{18}，直接模拟显然是行不通的，考虑优化。

如果将第 u 个人批评第 v 个人的定义为一个状态的话，因为一共有 n 个人，每个人可以对其他 n - 1 个人进行批评 ，那么 k 次批评最多的状态数为： n \times (n - 1) = 500 \times 499 = 249500 。

因为在确定上一次批评的批评者和被批评者时，下一次批评的批评者和被批评者是确定的。换句话说，对于已知的现有状态，有唯一确定的下一状态。如果将状态视为节点，批评的过程视为边的话，则每个节点出度均为 1。

以样例 2 为例：

3 7
0 3 2
3 0 3
2 1 0

通过模拟我们不难发现第 1 次和第 4 次批评都是第 1 个人批评第 2 个人，可见在 k 次批评中有许多状态会被重复访问。即该图中存在环，大量批评的过程在此环中重复进行，浪费了大量时间。我们只需找出此环，在进入到环中任意一节点时，将剩余批评次数对环的长度进行求余，再模拟即可，这样就省去了无数次在环中“绕圈”的过程。

code

下面给出递归实现：

#include<bits/stdc++.h>
int n,a[505][505],vis[505][505];
long long m;
void input()
{
    scanf("%d%lld",&n,&m);
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= n;j++)
            scanf("%d",&a[i][j]);
}
void dfs(int x,int y,long long k)
{
    if(vis[x][y])
        m = (m - k) % (k - vis[x][y]) + k;
    if(k == m)
    {
        printf("%d",x);
        exit(0);
    }
    vis[x][y] = k;
    dfs(y,a[y][x],k + 1);
}
int main()
{
    input();
    dfs(1,2,1);
    return 0;
}