元素方碑【牛客tracker 每日一题】

元素方碑时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述菲谢尔在稻妻冒险途中遇到一排神奇的元素方碑其中第i ii个方碑初始时的能量为a i a_iai​。只要她对第i ii块方碑施放雷元素就会发生能量转移正面轰击雷元素从第i − 1 i−1i−1块流向第i 1 i1i1块使a i − 1 a_{i−1}ai−1​减1 11、a i 1 a_{i1}ai1​加1 11反面轰击雷元素从第i 1 i1i1块流向第i − 1 i−1i−1块使a i 1 a_{i1}ai1​减1 11、a i − 1 a_{i−1}ai−1​加1 11。操作只能在2 ≦ i ≦ n − 1 2≦i≦n−12≦i≦n−1的方碑上进行且任何时刻所有方碑能量a i a_iai​必须保持非负。当所有方碑的能量a 1 , a 2 , … , a n a_1,a_2,…,a_na1​,a2​,…,an​全部相等时菲谢尔即可开启隐藏宝箱。菲谢尔可以无限次进行操作。请判断她是否一定能够让所有方碑能量相等。输入描述第一行输入一个整数t ( 1 ≦ t ≦ 10 4 ) t(1≦t≦10^4)t(1≦t≦104)——测试用例组数。对于每组测试数据第一行输入一个整数n ( 1 ≦ n ≦ 2 × 10 5 ) n(1≦n≦2×10^5)n(1≦n≦2×105)——方碑数量第二行输入n nn个整数a 1 , a 2 , … , a n ( 1 ≦ a i ≦ 10 9 ) a_1,a_2,…,a_n(1≦a_i≦10^9)a1​,a2​,…,an​(1≦ai​≦109)——初始能量。除此之外保证单个测试文件中全部测试用例的n nn之和不超过2 × 10 5 2×10^52×105。输出描述对每组测试数据在一行上输出Y E S YESYES或N O NONO表示能否通过若干次操作使所有方碑能量相等。示例1输入8 3 3 2 1 3 1 1 3 4 1 2 5 4 4 1 6 6 1 5 6 2 1 4 2 4 1 4 2 1 5 3 1 2 1 3 3 2 4 2输出YES NO YES NO YES NO NO NO复制说明在第一组样例中对于数组{ 3 , 2 , 1 } \{3,2,1\}{3,2,1}先对下标i 2 i2i2正面轰击一次得到2 , 2 , 2 {2,2,2}2,2,2能量已全部相等对于数组{ 1 , 2 , 5 , 4 } \{1,2,5,4\}{1,2,5,4}可依次正面轰击i 3 i3i3反面轰击i 2 i2i2最终得到{ 3 , 3 , 3 , 3 } \{3,3,3,3\}{3,3,3,3}对于数组{ 2 , 4 , 2 } \{2,4,2\}{2,4,2}无论如何操作总能量∑ a i ∑a_i∑ai​不是n nn的倍数因此无法全等答案为N O NONO。解题思路本题核心是数学规律推导奇偶分组求和通过守恒性质判断方碑能量能否均等。对中间方碑的轰击操作仅在奇偶下标位置之间转移能量因此总能量、奇数位总能量、偶数位总能量均守恒。首先判断总能量是否能被方碑数量n nn整除不满足则直接无解。将方碑按下标奇偶分组根据n nn的奇偶性确定两组的元素个数验证两组总能量可被自身个数整除且平均值相等。全部条件满足则输出 YES否则 NO。算法仅需线性遍历数组时间复杂度O ( n ) O(n)O(n)完美适配大数据规模与多组测试用例。总结核心逻辑轰击操作守恒总能量与奇偶位能量和需满足总能量均分、奇偶组平均值相等。关键操作按奇偶下标分组求和验证整除性与平均值一致性。效率保障线性时间复杂度无冗余计算高效处理题目约束的最大数据规模。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e210;constll p1e97;constll INF1e18;constll M2e310;intmain(){ll t;cint;while(t--){ll n;cinn;if(n1){cinn;coutYES\n;continue;}ll x0,y0;for(ll i0;in;i){ll a;cina;if(i1)xa;elseya;}ll mn/2;if((xy)%n||x%m||n1?y%(m1):y%m){coutNO\n;continue;}if(x/m!y/(n1?(m1):m))coutNO\n;elsecoutYES\n;}return0;}