题解 CF45B School

Rosmarinus · 2021-05-19 09:20:24 · 题解

时间复杂度是玄学的，过是能过的。

思路分析

采用类似记忆化搜索的方法，记录 vis_i 数组表示传到 i 的消息的热度的最大值。若在第 t 天传到第 i 个人的消息的热度 b'_i\le vis_i，那么不比再继续搜索；否则则更新 vis_i。若 vis_i=0，则表示这个消息是第 i 个人收到的第一条消息，令 ans+1。

考虑到一个人只有一个朋友，我们可以直接把搜索的过程放到循环中，即用 while。

极限时间复杂度是 \text{O}(nm)，但是跑不满，能过。

AC 代码

#include<iostream>
using namespace std;
int b[1100000], v[1100000], g[1100000], vis[1100000];
int main()
{
    int n, m, ans = 0;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i ++) scanf("%d", &g[i]);
    for(int i = 1; i <= m; i ++) scanf("%d", &v[i]);
    for(int i = 1; i <= m; i ++) scanf("%d", &b[i]);
    for(int i = 1; i <= m; i ++)
    {
        int a = (v[i] + ans - 1) % n + 1, t = b[i];
        ans = 0;
        while(vis[a] < t && t)
        {
            if(vis[a] == 0) ans ++;
            vis[a] = t;
            a = g[a];
            t --;
        }
        printf("%d\n", ans);
    }
    return 0;
}