P10195 [USACO24FEB] Quantum Moochanics G题目描述在空闲时间Bessie 喜欢涉猎实验物理。她最近发现了一对新的亚原子粒子命名为哞微子和反哞微子。如同标准的物质-反物质对哞微子和反哞微子相遇时会相互湮灭并消失。但这些粒子的独特之处在于每当 Bessie 看向它们时它们就会改变运动方向同时保持相同的速率。在她最新的实验中Bessie 将偶数N NN2 ≤ N ≤ 2 ⋅ 10 5 2\le N\le 2\cdot 10^52≤N≤2⋅105个这些粒子排成一行。这一行的左端以哞微子开始然后在两种类型的粒子之间交替第i ii个粒子位于位置p i p_ipi​0 ≤ p 1 ⋯ p N ≤ 10 18 0\le p_1\cdots p_N\le 10^{18}0≤p1​⋯pN​≤1018。哞微子初始时向右运动而反哞微子初始时向左运动其中第i ii个粒子以每秒s i s_isi​单位的恒定速率运动1 ≤ s i ≤ 10 9 1\le s_i\le 10^91≤si​≤109。Bessie 在以下时刻进行观察首先是实验开始后1 11秒。然后是第一次观察后2 22秒。然后是第二次观察后3 33秒。… … \ldots \ldots……然后是第n nn次观察后n 1 n1n1秒。在每次观察中Bessie 都会记下哪些粒子消失了。这个实验可能需要非常长的时间才能完成所以 Bessie 想要首先模拟一下它的结果。根据实验设置请帮助 Bessie 求出她何时即观察次数会观察到各个粒子消失可以证明所有粒子最终都会消失。输入格式每个测试点包含T TT1 ≤ T ≤ 10 1\le T\le 101≤T≤10个独立的测试用例。每个测试用例包含三行。第一行包含N NN第二行包含p 1 , … , p N p_1,\ldots,p_Np1​,…,pN​第三行包含s 1 , … , s N s_1,\ldots,s_Ns1​,…,sN​。输入保证所有N NN之和不超过2 ⋅ 10 5 2\cdot 10^52⋅105。输出格式对于每一个测试用例输出每个粒子消失时的观察次数用空格分隔。输入输出样例 #1输入 #14 2 1 11 1 1 2 1 12 1 1 2 1 11 4 6 2 1 11 4 5输出 #19 9 11 11 1 1 3 3输入输出样例 #2输入 #22 4 1 3 5 8 1 1 1 1 4 1 4 5 8 1 1 1 1输出 #21 1 3 3 7 2 2 7说明/提示样例解释 1对于第一个测试用例Bessie 在前8 88次观察中观察到以下情况哞微子初始时向右运动出现在位置2 → 0 → 3 → − 1 → 4 → − 2 → 5 → − 3 2\to 0\to 3\to −1\to 4\to −2\to 5\to −32→0→3→−1→4→−2→5→−3。反哞微子初始时向左运动出现在位置10 → 12 → 9 → 13 → 8 → 14 → 7 → 15 10\to 12\to 9\to 13\to 8\to 14\to 7\to 1510→12→9→13→8→14→7→15。然后恰好在观察9 99时两个粒子在位置6 66相遇并相互湮灭。对于第二个测试用例反哞微子的初始位置更靠右1 11单位从而两个粒子在观察11 1111之前半秒在位置6.5 6.56.5相遇。注意我们只关心观察次数不关心时刻或位置。样例解释 2对于第一个测试用例最左边的两个粒子恰好在观察1 11时在位置2 22相遇。最右边的两个粒子在观察3 33之前半秒在位置6.5 6.56.5相遇。测试点性质测试点3 33N 2 N2N2。测试点4 44N ≤ 2000 N\le 2000N≤2000且对于所有粒子p i ≤ 10 4 p_i\le 10^4pi​≤104。测试点5 − 7 5-75−7N ≤ 2000 N\le 2000N≤2000。测试点8 − 12 8-128−12没有额外限制。C实现#includebits/stdc.h#definelllonglong#definerep(i,s,t)for(intis;it;i)#definedebug(x)cerr#x:xendl;constintN200010;usingnamespacestd;intn,pre[N],nxt[N];ll p[N],s[N],res[N];voiddel(inti){nxt[pre[i]]nxt[i],pre[nxt[i]]pre[i];}llcalc(inti,intj){return(p[j]-p[i]s[i]s[j]-1)/(s[i]s[j])*2-(i1);}structcrash{inti,j;ll tim;booloperator(crash a)const{returntima.tim;}};priority_queuecrashq;voidsolve(){scanf(%d,n);rep(i,1,n)scanf(%lld,pi),pre[i]i-1,nxt[i]i1,res[i]0;nxt[n]0;rep(i,1,n)scanf(%lld,si);rep(i,1,n-1)q.push({i,i1,calc(i,i1)});while(q.size()){auto[i,j,tim]q.top();q.pop();if(res[i]||res[j])continue;res[i]res[j]tim;intiipre[i],jjnxt[j];if(iijj)q.push({ii,jj,calc(ii,jj)});del(i),del(j);}rep(i,1,n)printf(%lld%c,res[i], \n[in]);}intmain(){intT;scanf(%d,T);while(T--)solve();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容