Medium Demon Problem (easy version)CodeForces - 2044G1题目出处链接题目一组n nn蜘蛛聚在一起交换毛绒玩具。最初每只蜘蛛都有1 11个毛绒玩具。每年如果蜘蛛i ii至少有一个毛绒玩具他将把正好一个毛绒玩具给蜘蛛r i r_iri。否则他将什么也不做。请注意所有的毛绒玩具转移都是同时发生的。在这个版本中如果任何蜘蛛在任何时候拥有超过1 11个毛绒玩具他们将扔掉所有但保留1 11个。如果每只蜘蛛在当前年份当前年份的交换之前拥有与前一年前一年交换之前相同数量的毛绒玩具则该过程在当前年份是 稳定 的。请注意年份1 11永远不会是稳定的。找到过程变得稳定的第一年。输入格式第一行包含一个整数t tt1 ≤ t ≤ 10 4 1 \le t \le 10^41≤t≤104— 测试用例的数量。每个测试用例的第一行包含一个整数n nn2 ≤ n ≤ 2 ⋅ 10 5 2 \le n \le 2 \cdot 10^52≤n≤2⋅105— 蜘蛛的数量。接下来的行包含n nn个整数r 1 , r 2 , … , r n r_1, r_2, \dots, r_nr1,r2,…,rn1 ≤ r i ≤ n 1 \le r_i \le n1≤ri≤nr i ≠ i r_i \ne irii— 每只蜘蛛的毛绒玩具接收者。保证所有测试用例的n nn之和不超过2 ⋅ 10 5 2 \cdot 10^52⋅105。数据范围保证所有测试用例的 ( n ) 之和不超过2 ⋅ 10 5 2 \cdot 10^52⋅105。输出格式对于每个测试用例在新的一行输出一个整数表示过程变得 稳定 的第一年。样例输入522152345152142354115410439167910103输出22545样例说明对于第二个测试用例在年份1 11以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 1 , 1 , 1 ] [1, 1, 1, 1, 1][1,1,1,1,1]。然后年份1 11的交换发生。在年份2 22以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 1 , 1 , 1 ] [1,1,1,1,1][1,1,1,1,1]。由于这个数组与前一年相同因此这一年是稳定的。对于第三个测试用例在年份1 11以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 1 , 1 , 1 ] [1,1,1,1,1][1,1,1,1,1]。然后年份1 11的交换发生。在年份2 22以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 1 , 1 , 0 ] [1,1,1,1,0][1,1,1,1,0]。然后年份2 22的交换发生。请注意尽管两只蜘蛛给了蜘蛛2 22毛绒玩具但蜘蛛2 22可能只保留一个毛绒玩具。在年份3 33以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 0 , 1 , 0 ] [1,1,0,1,0][1,1,0,1,0]。然后年份3 33的交换发生。在年份4 44以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 0 , 0 , 0 ] [1,1,0,0,0][1,1,0,0,0]。然后年份4 44的交换发生。在年份5 55以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 0 , 0 , 0 ] [1,1,0,0,0][1,1,0,0,0]。由于这个数组与前一年相同因此这一年是稳定的。说明由于题目为英文所放的题目为翻译以后的中文类型为拓扑排序类型AC代码#includebits/stdc.h#defineIOSios::sync_with_stdio(0);cin.tie(0);cout.tie(0);#defineintlonglong#defineFfirst#defineSsecond#definepbpush_back#definepiipairint,int#defineendl\nusingnamespacestd;typedeflonglongll;constll N200005,MAXN0x3f3f3f3f3f3f3f3f,MOD1e97;voidsolve(){ll n;cinn;vectorllr(n1);//蜘蛛i把玩具给谁vectorllindeg(n1,0);//有多少只蜘蛛给i送玩具for(ll i1;in;i){cinr[i];indeg[r[i]];//次数}boolhas_leaffalse;//标记是否存在vectorlldist(n1,0);//存距离/长度queuellq;//存放等待处理的蜘蛛for(ll i1;in;i){if(indeg[i]0){//没人给它送玩具has_leaftrue;q.push(i);dist[i]1;//当距离为1}}ll ans1;//最大的距离//开始拓扑排序while(!q.empty()){//取出来ll uq.front();q.pop();//u要给的人ll vr[u];//更新距离dist[v]max(dist[v],dist[u]1);//max是因为v可能有很多的来源要最远的//删除 u →v 这条边indeg[v]--;if(indeg[v]0){//说明所有给 v 送玩具的蜘蛛都消失了q.push(v);//v下一轮也会消失入队ansmax(ans,dist[v]);//更新最大值}}//保证至少是 2稳定在消失的下一年所以 2if(!has_leaf)cout2\n;elsecoutans2endl;return;}signedmain(){IOS ll T;cinT;while(T--){solve();}return0;}欢迎大佬指正感谢收看与点赞
Medium Demon Problem (easy version)
Medium Demon Problem (easy version)CodeForces - 2044G1题目出处链接题目一组n nn蜘蛛聚在一起交换毛绒玩具。最初每只蜘蛛都有1 11个毛绒玩具。每年如果蜘蛛i ii至少有一个毛绒玩具他将把正好一个毛绒玩具给蜘蛛r i r_iri。否则他将什么也不做。请注意所有的毛绒玩具转移都是同时发生的。在这个版本中如果任何蜘蛛在任何时候拥有超过1 11个毛绒玩具他们将扔掉所有但保留1 11个。如果每只蜘蛛在当前年份当前年份的交换之前拥有与前一年前一年交换之前相同数量的毛绒玩具则该过程在当前年份是 稳定 的。请注意年份1 11永远不会是稳定的。找到过程变得稳定的第一年。输入格式第一行包含一个整数t tt1 ≤ t ≤ 10 4 1 \le t \le 10^41≤t≤104— 测试用例的数量。每个测试用例的第一行包含一个整数n nn2 ≤ n ≤ 2 ⋅ 10 5 2 \le n \le 2 \cdot 10^52≤n≤2⋅105— 蜘蛛的数量。接下来的行包含n nn个整数r 1 , r 2 , … , r n r_1, r_2, \dots, r_nr1,r2,…,rn1 ≤ r i ≤ n 1 \le r_i \le n1≤ri≤nr i ≠ i r_i \ne irii— 每只蜘蛛的毛绒玩具接收者。保证所有测试用例的n nn之和不超过2 ⋅ 10 5 2 \cdot 10^52⋅105。数据范围保证所有测试用例的 ( n ) 之和不超过2 ⋅ 10 5 2 \cdot 10^52⋅105。输出格式对于每个测试用例在新的一行输出一个整数表示过程变得 稳定 的第一年。样例输入522152345152142354115410439167910103输出22545样例说明对于第二个测试用例在年份1 11以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 1 , 1 , 1 ] [1, 1, 1, 1, 1][1,1,1,1,1]。然后年份1 11的交换发生。在年份2 22以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 1 , 1 , 1 ] [1,1,1,1,1][1,1,1,1,1]。由于这个数组与前一年相同因此这一年是稳定的。对于第三个测试用例在年份1 11以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 1 , 1 , 1 ] [1,1,1,1,1][1,1,1,1,1]。然后年份1 11的交换发生。在年份2 22以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 1 , 1 , 0 ] [1,1,1,1,0][1,1,1,1,0]。然后年份2 22的交换发生。请注意尽管两只蜘蛛给了蜘蛛2 22毛绒玩具但蜘蛛2 22可能只保留一个毛绒玩具。在年份3 33以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 0 , 1 , 0 ] [1,1,0,1,0][1,1,0,1,0]。然后年份3 33的交换发生。在年份4 44以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 0 , 0 , 0 ] [1,1,0,0,0][1,1,0,0,0]。然后年份4 44的交换发生。在年份5 55以下数组显示每只蜘蛛拥有的毛绒玩具数量[ 1 , 1 , 0 , 0 , 0 ] [1,1,0,0,0][1,1,0,0,0]。由于这个数组与前一年相同因此这一年是稳定的。说明由于题目为英文所放的题目为翻译以后的中文类型为拓扑排序类型AC代码#includebits/stdc.h#defineIOSios::sync_with_stdio(0);cin.tie(0);cout.tie(0);#defineintlonglong#defineFfirst#defineSsecond#definepbpush_back#definepiipairint,int#defineendl\nusingnamespacestd;typedeflonglongll;constll N200005,MAXN0x3f3f3f3f3f3f3f3f,MOD1e97;voidsolve(){ll n;cinn;vectorllr(n1);//蜘蛛i把玩具给谁vectorllindeg(n1,0);//有多少只蜘蛛给i送玩具for(ll i1;in;i){cinr[i];indeg[r[i]];//次数}boolhas_leaffalse;//标记是否存在vectorlldist(n1,0);//存距离/长度queuellq;//存放等待处理的蜘蛛for(ll i1;in;i){if(indeg[i]0){//没人给它送玩具has_leaftrue;q.push(i);dist[i]1;//当距离为1}}ll ans1;//最大的距离//开始拓扑排序while(!q.empty()){//取出来ll uq.front();q.pop();//u要给的人ll vr[u];//更新距离dist[v]max(dist[v],dist[u]1);//max是因为v可能有很多的来源要最远的//删除 u →v 这条边indeg[v]--;if(indeg[v]0){//说明所有给 v 送玩具的蜘蛛都消失了q.push(v);//v下一轮也会消失入队ansmax(ans,dist[v]);//更新最大值}}//保证至少是 2稳定在消失的下一年所以 2if(!has_leaf)cout2\n;elsecoutans2endl;return;}signedmain(){IOS ll T;cinT;while(T--){solve();}return0;}欢迎大佬指正感谢收看与点赞
