前缀和二分
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int a[200010];
int c2[200010],p2[200010];
int c5[200010],p5[200010];
void solve()
{int n,k; cin>>n>>k;
for(int i=0;i<=n+5;i++) c2[i]=c5[i]=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
while(a[i]%2==0)
{
a[i]=a[i]/2;
c2[i]++;
}
while(a[i]%5==0)
{
a[i]=a[i]/5;
c5[i]++;
}
p2[i]=p2[i-1]+c2[i];//前缀和
p5[i]=p5[i-1]+c5[i];
}
ll ans=0;
for(int i=1;i<=n;i++)
{
int v2=k+p2[i-1];//i处的p2前缀和+k,,后缀==v2
int v5=k+p5[i-1];
int l2=lower_bound(p2,p2+1+n,v2)-p2;
int r2=upper_bound(p2,p2+1+n,v2)-1-p2;
int l5=lower_bound(p5,p5+1+n,v5)-p5;
int r5=upper_bound(p5,p5+1+n,v5)-1-p5;
int l=max(l2,l5);
int r=max(r2,r5);
l=max(l,i);
if(l==n+1) continue;
ans+=(r-l+1);
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t; cin>>t;
while(t--)
{
solve();
}
return 0;
}
查找数字二分
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
int n,m,k,q;
vector<ll>del;
ll a[100010],b[100010];
ll num(ll mid)
{
ll cnt=0;
int r=m;
for(int i=1;i<=n;i++)
{
while(a[i]*b[r]>mid&&r) r--;
cnt+=r;
}
for(auto x: del)
{
if(x<=mid) cnt--;
}
return cnt;
}
int main()
{
cin>>n>>m>>k>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=m;i++)
cin>>b[i];
int u,v,Q;
for(int i=1;i<=k;i++)
{
cin>>u>>v;
del.pb(a[u]*b[v]);
}
sort(a+1,a+1+n);
sort(b+1,b+1+m);
for(int i=1;i<=q;i++)
{
cin>>Q;//查询的第k小
ll l=0,r=1e13;
while(r-l>1)
{
ll mid=(l+r)/2;
if(num(mid)<Q) l=mid;
else r=mid;
}
cout<<r<<endl;
}
return 0;
}
CF:::: https://codeforces.com/contest/1845/problem/C
(经典数字二分,拆除问题,,) 思路!!!
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
//typedef __int128 LL;//2的128
typedef long long ll; //2的64
// 1e9,, 1e19,,1e38
const int N=3e5+30;
int t;
string str,a,b;
vector<int> as[11];
void solve()
{
cin>>str;
str="0"+str;
int len=str.size();
//注意len溢出问题
for(int i=1;i<len;i++)
{
int d=str[i]-'0';
as[d].push_back(i);
}
int n;
cin>>n;
cin>>a; a="0"+a;
cin>>b; b="0"+b;
int pos=0;
int flag=0;
//加入len+1是每一个id都小于len+1肯定可以找到len+1的id
for(int i=0;i<=9;i++) as[i].push_back(len+1);
for(int i=1;i<=n;i++)
{
int s=pos;//就是id下标
for(char c=a[i];c<=b[i];c++)
{
int d=c-'0';
//查找这个字符里面 第一个大于s的下标;;如果该下标没找到那么退出
int x=upper_bound(as[d].begin(),as[d].end(),s)-as[d].begin();
if(as[d][x]==len+1)
{
i=n+1; //直接退出循环了
flag=1;break;
}
//本题找不符合的(一个就行),故每个数字找id最大的
pos=max(pos,as[d][x]);//找第i个数字的最大值,
}
}
if(flag) cout<<"YES";
else cout<<"NO";
cout<<endl;
for(int i=0;i<=9;i++) as[i].clear();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int t; cin>>t;
while(t--)
{
solve();
}
return 0;
}
dijk+二分
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll; //2的64
const int N=10010;
struct node
{
ll id,w;
};
struct nod
{
ll w,id;
bool operator< (const nod & qwe) const
{
return w>qwe.w;
}
};
vector<node> vec[N];
priority_queue<nod>q;
bool vis[N];
ll dis[N];
ll b,v,f[N];
int n,m,x,y;
bool check( int x)
{
if(f[1]>x) return 0;
for(int i=1;i<=n;i++)
{
dis[i]=1e18;
vis[i]=false;
}
dis[1]=0;
q.push({0,1});
while(q.size())
{
auto k=q.top();
int u=k.id;
q.pop();
if(vis[u]==1) continue;
vis[u]=true;
for(int i=0;i<vec[u].size();i++)
{
int v=vec[u][i].id;
if(f[v]>x) continue;
ll w=vec[u][i].w;
if(dis[u]+w<dis[v])
{
dis[v]=dis[u]+w;
q.push({dis[v],v});
if(v==n)
{
if(dis[v]>b) return 0;
else return 1;
}
}
}
}
return 0;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
ll maxv=-1;
cin>>n>>m>>b;
for(int i=1;i<=n;i++)
{
cin>>f[i];
maxv=max(maxv,f[i]);
}
for(int i=1;i<=m;i++)
{
cin>>x>>y>>v;
vec[x].push_back({y,v});
vec[y].push_back({x,v});
}
ll ans=-1,l=max(f[1],f[n]),r=maxv+1;
while(l<r)
{
ll mid=(l+r)/2;
if(check(mid))
{
ans=mid;
r=mid;
}
else l=mid+1;
}
/*while(l <= r){
long long mid = (l + r) / 2;
cout<<mid<<endl;
if(check(mid)) ans = mid, r = mid - 1;//更形ans
else l = mid + 1;
}*/
if(ans==-1)
cout<<"AFK";
else cout<<l;
return 0;
}