被公司安排了5级集训，写一下觉得最近5级比较难的一些题目吧。
代码中涉及二分的内容，笔者的二分习惯和常规方法不太一样，具体可以观看以下视频：

https://www.bilibili.com/video/BV1d54y1q7k7/?spm_id_from=333.337.search-card.all.click&vd_source=5b13f5dd5db58d43cf6a37d7a856f306

https://www.bilibili.com/video/BV128411M7GT/?spm_id_from=333.337.search-card.all.click&vd_source=5b13f5dd5db58d43cf6a37d7a856f306

T1：数字移动

题目链接：https://www.luogu.com.cn/problem/P14917
思路：不正经的来说，5级考察二分和贪心，又是求最值，那只考虑这两个算法就行了。正经分析一下，求的是每次移动代价的最小值，那从枚举的角度来想，枚举代价从小到大，代价非常小的时候，能移动的数字有限，凑不出题目要求的数列。当代价到达某个数值时，能使得数列符合要求，那么代价再大都可以符合要求，所以代价符合单调性，可以二分答案。难点在二分答案的check书写上。对于一个元素值>答案值的元素，是无法移动的，想要和相同的数相邻，只能移动其中元素值<=答案的元素。所以整理出元素值>答案值的元素，判断其中相邻数字是否相同即可。

#include<iostream>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,a[N],mina=1e5,maxa; 
bool check(int t){
	int b[N],len=0;//b[i]记录a中元素值>t的元素，len为b数组长度 
	for(int i=0;i<n;i++){
		if(a[i]>t){
			b[len++]=a[i];
		}
	}
	for(int i=0;i<len;i+=2){
		if(b[i]!=b[i+1]){
			return false;
		}
	}
	return true;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		mina=min(mina,a[i]);
		maxa=max(maxa,a[i]);
	}
	int l=mina-1,r=maxa+1; 
	while(l+1<r){
		int mid=l+(r-l)/2;
		if(check(mid)){
			r=mid;
		}else{
			l=mid;
		}
	}
	cout<<r<<endl;
	return 0;
} 

T2：相等序列

题目链接：https://www.luogu.com.cn/problem/P14918
思路：思路想想很简单，每个数分解质因数，相同的质因数指数求一个中位数，然后累加所有（指数-中位数）即可。但是没学过STL的话，能60分，因为这个思路容易MLE和TLE。MEL原因：有些质数是没出现过的；TLE原因：0的个数过多。使用STL，可以不用存储、遍历没出现过的质数。

#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e5+10;
map<int,vector<int>> mp;
int n,a[N];
long long ans;
void f(int num){
	if(num==1){
		return ;
	}
	for(int i=2;i*i<=num;i++){
		if(num%i==0){
			int sum=0;
			while(num%i==0){
				sum++;
				num/=i;
			}
			mp[i].push_back(sum);
		}
	}
	if(num>1){
		mp[num].push_back(1);
	}
}
int main() {
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		f(a[i]);
	}
	for(auto i:mp){
		sort(i.second.begin(),i.second.end());
		int len=i.second.size();
		int target;
		if(n-len>len){//如果0的数量>非0的数量 
			target=0;//中位数为0 
		}else{//否则中位数为数组中的数 
			target=i.second[(2*len-n)/2];
		}
		ans+=(n-len)*target;//计算0产生的数值 
		for(auto j:i.second){//计算非0产生的数值 
			ans+=abs(j-target);
		}
	}
	cout<<ans<<endl;
	return 0;
}

T3：有趣的数字和

题目链接：https://www.luogu.com.cn/problem/P14074
思路：暴力枚举一定TLE，但是考场上如果没思路一定要提交一个暴力枚举的代码拿点分数。然后找了一下规律。一个数n的二进制里有奇数个1，那么n<<1依然有奇数个1，所以以2^k长度划分区间(k=0,1,2…)，那么2的^k+1长度区间的前半部分的二进制奇偶情况和2^k长度相同。然后打表找1到128范围内，每个区间的后半部分规律，意外发现了从4开始，每4个为1组，一定有2个数字是有趣的数，再从0开始打表，0123也符合这个规律，而且4元组里，要么第1个和第4个是有趣的数，要么是第2个和第3个。设四元组分别为4n，4n+1，4n+2，4n+3，里面有趣的数和一定是8n+3。后续笔者懒得思考23333，代码直接分类讨论求解了。

#include<iostream>
using namespace std;
long long l,r,ans,ln,rn;
bool f(long long num){
	long long cnt=0;
	while(num){
		cnt+=num&1;
		num>>=1;
	}
	return cnt%2;
}
int main() {
	cin>>l>>r;
	//以下代码在补全4元组，方便计算 
	ln=l/4;//计算是第几个4元组里的数
	if(l%4!=0) { //如果l不是4元组的第1个数 
		int x=l%4;
		if(x==1) { //l是4元组的第2个
			if(!f(l)) { //如果第2个不是有趣的数
				//那么第1个是有趣的数
				ans-=l-1;
			}
		} else if(x==2) { //l是4元组的第3个
			if(f(l)) { //如果第3个是有趣的数
				//那么第2个也是有趣的数
				ans-=l-1;
			} else { //第3个不是有趣的数
				//那么第1个是有趣的数
				ans-=l-2;
			}
		} else { //l是4元组的第4个
			if(f(l)) { //如果第4个是有趣的数
				//那么第1个是有趣的数
				ans-=l-3;
			} else { //第4个不是有趣的数
				//那么第2、3个是有趣的数
				ans-=(l-1+l-2);
			}
		}
	}
	rn=r/4;//计算r是第几个4元组里的数
	if(r%4!=3) { //如果r不是4元组的末尾
		int x=r%4;
		if(x==0) {//如果r是4元组的第1个数
			if(f(r)) { //如果第1个是有趣的数
				//那么第4个也是有趣的数
				ans-=r+3;
			} else { //第1个不是有趣的数
				//那么第2、3个是有趣的数
				ans-=(r+1+r+2);
			}
		} else if(x==1) {//如果r是4元组的第2个数
			if(f(r)) { //如果第2个是有趣的数
				//那么第3个也是有趣的数
				ans-=r+1;
			} else { //第2个不是有趣的数
				//那么第4个是有趣的数
				ans-=r+2;
			}
		} else {//如果r是4元组的第3个数
			if(!f(r)) { //如果第3个不是有趣的数
				//那么第4个是有趣的数
				ans-=r+1;
			}
		}
	}
	//补全4元组之后，把所有4元组的和累加即可，符合等差数列求和
	ans+=(8*ln+3+8*rn+3)*(rn-ln+1)/2;
	cout<<ans<<endl;
	return 0;
}