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

元素方碑

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

菲谢尔在稻妻冒险途中遇到一排神奇的元素方碑，其中第i ii个方碑初始时的能量为a i a_iai​。只要她对第i ii块方碑施放雷元素，就会发生能量转移：

• 正面轰击：雷元素从第i − 1 i−1i−1块流向第i + 1 i+1i+1块，使a i − 1 a_{i−1}ai−1​减1 11、a i + 1 a_{i+1}ai+1​加1 11；
• 反面轰击：雷元素从第i + 1 i+1i+1块流向第i − 1 i−1i−1块，使a i + 1 a_{i+1}ai+1​减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 i=2i=2正面轰击一次，得到2 , 2 , 2 {2,2,2}2,2,2，能量已全部相等；
• 对于数组{ 1 , 2 , 5 , 4 } \{1,2,5,4\}{1,2,5,4}，可依次正面轰击i = 3 i=3i=3，反面轰击i = 2 i=2i=2，最终得到{ 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)，完美适配大数据规模与多组测试用例。

总结

核心逻辑：轰击操作守恒总能量与奇偶位能量和，需满足总能量均分、奇偶组平均值相等。
关键操作：按奇偶下标分组求和，验证整除性与平均值一致性。
效率保障：线性时间复杂度，无冗余计算，高效处理题目约束的最大数据规模。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=1e2+10;constll p=1e9+7;constll INF=1e18;constll M=2e3+10;intmain(){ll t;cin>>t;while(t--){ll n;cin>>n;if(n==1){cin>>n;cout<<"YES\n";continue;}ll x=0,y=0;for(ll i=0;i<n;i++){ll a;cin>>a;if(i&1)x+=a;elsey+=a;}ll m=n/2;if((x+y)%n||x%m||n&1?y%(m+1):y%m){cout<<"NO\n";continue;}if(x/m!=y/(n&1?(m+1):m))cout<<"NO\n";elsecout<<"YES\n";}return0;}