学校的作业题。
非常好题目，思考过程非常自然。
CF2114G
首先如果数组中有相邻的数相等，直接输出NO。
然后探讨一下合并操作性质：只有可能发生在数组边缘。发现一定是先合成一个中间的数，然后由内向外依次合成。
例如给出的数组是[1,2,3]，那我们可以先合成中间的 \(2\)，然后再合成两边的数，这个过程中，\(2\) 是一个“隔板”，是不会被合并的。
不难发现一个数可以分解成 \(2^x\cdot k\)，其中 \(k\) 是一个奇数。显然，这个数可以通过 \([1,2^x]\) 中的任意次操作合成。
但是请注意，在合并过程中，这个数可能有相邻的、已经被合成好的数。例如在上述例子中，合成好 \(2\) 后再合成 \(3\) 的时候，我们要保证这个过程中 \(3\) 这个位置的数不会和 \(2\) 相等。
如何处理这个问题？需要进行一定的分类讨论：如果两个数的 \(k\) 不相同，那么它们不可能相等。这个时候当前合成的数最多还是贡献 \(2^x\) 次操作；如果两个相等，又分以下两种情况：如果当前合成的数的 \(x\) 小于相邻的数的 \(x\)，那么肯定不会影响，还是贡献 \(2^x\) 次；否则，必须从 \(2^{x_0+1}\) 开始往后加（此处的 \(x_0\) 是指已经合成好的元素），那么最多只能贡献 \(2^x-2^{x_0+1}+1\) 次操作（此处的 \(x\) 指正在合成的元素）。
最后考虑如何快速计算以每一个位置为中心点时的总贡献。考虑到将中心位置从 \(i\) 移动到 \(i+1\)，此时 \(i\) 的相邻元素会从不存在（即没有限制）变为 \(i+1\)，同时 \(i+1\) 的限制会消除。那么通过只计算变化量的思想，这个转移可以在常数时间内实现。只要这个总贡献的最大值超过了 \(k\)，那么便输出YES。
//to kill a living book
#include<bits/stdc++.h>
#define int long long
#define ll __int128
#define double long double
using namespace std;pair<int,int> cal(int x){int res=0;while(!(x&1)) res++,x>>=1;return {x,res};
}int work(pair<int,int> i,pair<int,int> lim){auto [ix,im]=i;auto [lx,lm]=lim;if(ix!=lx||im<lm) return (1<<im);else return (1<<im)-(1<<(lm+1))+1;
}void solve(){int n,k;cin>>n>>k;vector<int> a(n+1);for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<n;i++){if(a[i]==a[i+1]){return cout<<"NO\n",void();}}vector<pair<int,int>> info(n+1,{0,0});for(int i=1;i<=n;i++){info[i]=cal(a[i]);}int res=0;for(int i=1;i<=n;i++){res+=work(info[i],info[i-1]);}//位置 0 代表限制不存在if(res>=k) return cout<<"YES\n",void();for(int i=2;i<=n;i++){res-=work(info[i-1],info[0]);res+=work(info[i-1],info[i]);res-=work(info[i],info[i-1]);res+=work(info[i],info[0]);if(res>=k) return cout<<"YES\n",void();}cout<<"NO\n";
}signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int t; cin>>t;while(t--) solve();return 0;
}
https://codeforces.com/contest/2114/submission/361649912