CF45B School 题解

小杨小小杨 · 2022-02-18 22:08:02 · 题解

前言

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

（其实也不是玄学，似乎复杂度是能分析出来的）

题意

就是一大堆小朋友玩分糖，当前这个人如果有 x 个糖，他就会拿走一个，然后让他的朋友拿到 x-14 个。
好了这就是核心问题。

思路

搜索都学过吧。

由于每个人都只有一个朋友，所以可以直接循环去找。运用类似记忆化搜索的思路，保存每一个位置最大得热度，如果当前的热度过小，就停止搜索，不然就继续搜索下去。如果当前这个人是第一次知道消息，那就把这个能传的人数增加。

记得初始化！！！

（不支持hack数据，原OJ能通过）

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,i,a,sum,t,g[100010],v[100010],b[100010],f[100010];
int main(){
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&g[i]);
    for (i=1;i<=m;i++) scanf("%d",&v[i]);
    for (i=1;i<=m;i++) scanf("%d",&b[i]);
    for (i=1;i<=m;i++){
        a=(v[i]+sum-1)%n+1;t=b[i];sum=0;
        while (f[a]<t&&t!=0){
            if (!f[a]) sum++;
            f[a]=t;a=g[a];t--;
        }
        printf("%d\n",sum);
    }
    return 0;
}