CF45B题解

Lyrella · 2022-08-15 20:08:30 · 题解

前言

复杂度是玄学的，过是能过的。（后面滴保持队型）

思路

可以用 \text{while} 循环记忆化搜索（暴力），再用一个 max 数组记录每条消息的最大值。

对于每个消息的热度 b_i，如果 b_i<max_i，则 i 之前被算过，退出循环。如果 max_i=0 则 i 还未接收过消息，ans+1。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n, m, g[N], v[N], b, res, ma[N];
signed main()
{
    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++)
    {
        int a = (v[i] + res - 1) % n + 1;
        scanf("%d", &b); res = 0;
        while(ma[a] < b and b)
        {
            if(!ma[a])res++;
            ma[a] = b--; a = g[a];
        }
        printf("%d\n", res);
    }
    return 0;
}