打卡信奥刷题（3109）用C++实现信奥题 P7299 [USACO21JAN] Dance Mooves S

P7299 [USACO21JAN] Dance Mooves S题目描述Farmer John 的奶牛们正在炫耀她们的最新舞步最初所有的NNN头奶牛2≤N≤1052≤N≤10^52≤N≤105站成一行奶牛iii排在其中第iii位。舞步序列给定为KKK1≤K≤2×1051≤K≤2\times10^51≤K≤2×105个位置对(a1,b1),(a2,b2),…,(aK,bK)(a_1,b_1),(a_2,b_2),…,(a_K,b_K)(a1​,b1​),(a2​,b2​),…,(aK​,bK​)。在舞蹈的第i1…Ki1…Ki1…K分钟位置aia_iai​与bib_ibi​上的奶牛交换位置。同样的KKK次交换在第K1…2KK1…2KK1…2K分钟发生在第2K1…3K2K1…3K2K1…3K分钟再次发生以此类推无限循环。换言之在第111分钟位置a1a_1a1​与b1b_1b1​上的奶牛交换位置。在第222分钟位置a2a_2a2​与b2b_2b2​上的奶牛交换位置。……在第KKK分钟位置aKa_KaK​与bKb_KbK​上的奶牛交换位置。在第K1K1K1分钟位置a1a_1a1​与b1b_1b1​上的奶牛交换位置。在第K2K2K2分钟位置a2a_2a2​与b2b_2b2​上的奶牛交换位置。以此类推……对于每头奶牛求她在队伍中会占据的不同的位置数量。输入格式输入的第一行包含NNN、KKK。以下KKK行分别包含(a1,b1)…(aK,bK)(a_1,b_1)…(a_K,b_K)(a1​,b1​)…(aK​,bK​)1≤aibi≤N1≤a_ib_i≤N1≤ai​bi​≤N。输出格式输出NNN行第iii行包含奶牛iii可以到达的不同的位置数量。输入输出样例 #1输入 #15 4 1 3 1 2 2 3 2 4输出 #14 4 3 4 1说明/提示奶牛111可以到达位置{1,2,3,4}\{1,2,3,4\}{1,2,3,4}。奶牛222可以到达位置{1,2,3,4}\{1,2,3,4\}{1,2,3,4}。奶牛333可以到达位置{1,2,3}\{1,2,3\}{1,2,3}。奶牛444可以到达位置{1,2,3,4}\{1,2,3,4\}{1,2,3,4}。奶牛555从未移动所以她没有离开过位置555。测试点性质测试点 1-5 满足N≤100,K≤200N≤100,K≤200N≤100,K≤200。测试点 6-10 满足N≤2000,K≤4000N≤2000,K≤4000N≤2000,K≤4000。测试点 11-20 没有额外限制。供题Chris ZhangC实现#includebits/stdc.husingnamespacestd;intn,k,a[100005],fa[100005];vectorintv[100005];setintans[100005];intfind(intx){//并查集找父亲if(fa[x]x)returnx;returnfa[x]find(fa[x]);}intmain(){cinnk;for(inti1;in;i){//并查集和原数组重置fa[i]i;a[i]i;}for(inti1;ik;i){intx,y;cinxy;swap(a[x],a[y]);//交换v[a[x]].push_back(y);//载入经过的点v[a[y]].push_back(x);}for(inti1;in;i)v[a[i]].push_back(i);//载入改点的原点for(inti1;in;i)fa[find(i)]find(a[i]);//合并并查集for(inti1;in;i){for(intj0;jv[a[i]].size();j){ans[find(a[i])].insert(v[a[i]][j]);//用set载入a[i]的答案}}for(inti1;in;i)coutans[find(i)].size()endl;//输出答案return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容