题解 P2921 [USACO08DEC]在农场万圣节Trick or Treat on the Farm

水过这题一看题解发现大部分都是Tarjan之类~~我不会~~复杂的算法，要不就是一些不够优良、不够易懂的算法。于是发这篇题解，希望帮助一下和我一样的蒟蒻。 --- 在做提高试炼场时看到了这题:  （~~实在找不到没有通过的图片了~~） 作为一个板块里的题，自然是连着做的，于是产生了一种神奇的惯性思维。在看到题面的第一眼就发现这道题与[P2611 信息传递](https://www.luogu.org/problem/P2661)十分相像，就尝试使用与信息传递类似的方法来求解。 根据题意，一只奶牛停止的条件是来到她所经过过的房间，所以奶牛想要停下来必须要找到一个环。我们从一个点开始搜索的时候用s数组记录下依次到达每个房间的糖果数并用vis数组记录访问过的房间，在找到已经访问过的房间的时候，用现在到达这个房间应该得到的糖果数s[n]减去已经上次来到时得到的糖果数s[m]，用h数组记录下来，就可以得知这个环上获得的糖果数。 ```cpp void dfs(int now,int nowc) { if(vis[now]==true) //如果已经访问过 { h[now]=nowc-s[now]; //环上的糖果数 return; } vis[now]=true; //记录访问过 s[now]=nowc; //记录现在的糖果数 dfs(a[now],nowc+1); return; } ``` 那记录下环上的糖果数有什么用呢？你看这里有一个又大又圆的环：  因为一个房间通向的房间都是唯一的，不难发现一但来到环上的任何一个房间，必定会绕这个环一圈回到原点。则对于每一个环上的房间，之后会获得的糖果数就是确定的。所以我们可以根据这个特点，标记环上的每一个房间，一但到达这些房间就直接返回环上的糖果数。 ```cpp int dfs(int now,int nowc) { if(h[now]!=0) return nowc-1+h[now]; //如果这个房间在环上，直接返回环上糖果数 if(vis[now]==true) { h[now]=nowc-s[now]; flag=now; //记录现在环上的终点 return nowc-1; //返回现在的糖果数 } vis[now]=true; s[now]=nowc; int ans=dfs(d[now],nowc+1); //因为还需要标记所以不直接返回值 if(flag!=0) //如果房间还在环上 { if(now==flag) flag=0; //如果回到起点，就清空记录 else h[now]=h[flag]; //否则标记这个房间在环上 } vis[now]=false //清除记录，省好多个memset() return ans; } ``` 然后开开心心交一发。   好像有些不对劲，果然蓝题不是那么好水的。。。仔细一想原因应该是可能出现有好多小环的情况，这样的情况下基本就等同于暴力。 于是我开动我的小脑瓜，发现TLE的原因正是思考的不够全面。既然一个房间通向的房间是唯一的，那么来到任意一个房间，接下来的结局都是固定哒！！！所以我们只要在回溯的时候对于不在环上的房间记录下之后获得的糖果数，在下一次到达的时候直接返回即可。 ```cpp int dfs(int now,int nowc) { if(h[now]!=0) return nowc-1+h[now]; if(vis[now]==true) { h[now]=nowc-s[now];flag=now; return nowc-1; } vis[now]=true;s[now]=nowc; int ans=dfs(d[now],nowc+1); if(flag!=0) { if(now==flag) flag=0; else h[now]=h[flag]; } else h[now]=h[d[now]]+1; //如果不在环上就记录下一个房间的糖果数加1 vis[now]=false; return ans; } ``` 轻轻的敲上一行代码，再一次提交。  这回就舒服了，比之前高到不知道哪里去了。忍不住看了一发最优解，结果发现竟然只排在第9页？仔细一看前面，竟然都加快读和开O2，哼哼，那就由不得我了。经过一番尝试，终于搞到了第2页的第一个，才敢来发题解。 完整代码 ```cpp // 快读请自行添加 #include <iostream> #include <cstdio> using namespace std; int n,d[100008],s[100008],h[100008],flag; bool vis[100008]; int dfs(int now,int nowc) { if(h[now]!=0) return nowc-1+h[now]; if(vis[now]==true) { h[now]=nowc-s[now];flag=now; return nowc-1; } vis[now]=true;s[now]=nowc; int ans=dfs(d[now],nowc+1); if(flag!=0) { if(now==flag) flag=0; else h[now]=h[flag]; } else h[now]=h[d[now]]+1; vis[now]=false; return ans; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&d[i]); for(int i=1;i<=n;i++) printf("%d\n",dfs(i,1)); return 0; } ```