- 二分
- 模板
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
ll n,m;
const ll N =2e5+9;
ll a[N];
ll v[N];
int f(ll mid){
ll ans=0,pre=-1e9;
for(int i=1;i<=n;i++){
if(a[i]-pre>=mid) ans++,pre=a[i];
}
return ans;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
ll l=0,r=2*1e9+10;
//二分模板，我自己学的
while(l+1!=r){
ll mid=(l+r) >> 1;
if(f(mid)>=m) l=mid;
else r=mid;
}
cout<<l<<' ';
return 0;
}//这种写法错误概率小
一般利用二分首先要排序，其次找到方程关于l,r的关系（如牛奶那道题目）。 如果遇到你想找像连续不同最大子串个数可以用二分解决，
但是你要想清楚怎么去寻找，我学到的一种方法是动态去维护子串的最大值，如下（还可以利用双指针，双指针要确保方向不然会超时，就是方向不能出现从两侧分开，双指针的话你需要一个前一个后，并且考虑i，j需不需要从头开始还是保持不变继续往下，代码如下下）
bool check(int mid){
for(int i=1;i<=n;i++) c[a[i]]=0;
int cnt1=0;
for(int i=1;i<=mid;i++){
c[a[i]]++
if(c[a[i]]==1) cnt1++;
else if(c[a[i]]==2)cnt1--;
if(cnt1==mid) return true;
}
//下面这个部分是实时维护子串中为一的个数
for(int i=1;j=mid;j<n;++i,++j){
c[a[i]]--;
if(c[a[i]]==1)cnt1++;
else if(c[a[i]]==0) cnt1--;
c[a[j+1]]--;
if(c[a[j+1]]==1)cnt1++;
else if(c[a[j+1]]==2)cnt1--;
if(cnt1==mid) return true;
}
return false;
}
就刚刚写的ABC-353，就可以利用二分，当时写的时候找不到思路，我对二分怎么用还是有点问题
（虽然当时想到用二分解决，但是思路错了）。
https://atcoder.jp/contests/abc353/tasks/abc353_c
补题代码：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 100000000;
ll n,m;
const ll N =3e5+9;
ll a[N],v[N];
ll ans=0,sum=0,pd=0;
/*
每个数字都相当于加了（n-1）遍
，但是如果出现俩个数相加大于1e8
，就要减一个1e8，我们只要将所有的数*n-1·
然后在计算一下剪掉1e8的个就行，排序
，然后二分或者lower_bound都行
*/
int check(int x){
ll l=0,r=n+1;
while(l+1!=r){
ll mid = (l+r) >> 1;
if(a[mid]>=x) r=mid;
else l=mid;
}
return r;//找每一个数从右边开始数多少个满足。
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
sum+=(n-1)*a[i];
}
sort(a+1,a+n+1);
ans=sum;
for(int i=1;i<n;i++){
if(a[i]+a[n]<MOD) continue;
int res=check(MOD-a[i]);
if(res<=i)res=i+1; if(res>n) continue;
ans-=(n-res+1)*MOD;
}
cout<<ans;
return 0;
}
*双指针
这个就是从头找到尾巴，看范围如果很大容易超时，双指针写法很多，只能慢慢一个一个去学。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
const ll N =2*1e5+9;
ll a[N];
ll v[N];
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
ll n;
cin>>n;
while(n--){
memset(v,0,sizeof v);
ll m;
cin>>m;
for(int i=1;i<=m;i++)cin>>a[i];
ll ans =0;
for(ll i=1,j=0;i<=m;i++){
while(j<m&&!v[a[j+1]])v[a[++j]] ++;
ans=max(ans,j-i+1ll);
v[a[i]] --;
}
cout<<ans<<'\n';
}
return 0;
}
xor前缀和
题目链接https://www.starrycoding.com/problem/53
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N =2e5+8;
int prexor[N];
void solve()
{
int a,b;
cin>>a>>b;
int y=prexor[a-1]^b;
if(y==a) cout<<a+2<<'\n';
else if(y==0) cout<<a<<'\n';
else cout<<a+1<<'\n';
}
int main ()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(int i=1;i<=2e5;i++) prexor[i] = prexor[i-1]^i;
int t;
cin>>t;
while(t--) solve();
return 0;
}