标签：prime 200005 子段 int mid cin cc 最优
- 素数的密度约为ln(n)，这就是说，1~n中素数的个数约为\(\frac {n}{ln(n)}\)
- 观察你写出来的DP转移式，可以发现检查时没有必要DP，直接贪心就好了
- 由于数据随机，最后十分钟“乱搞”两次成功过题，开心~
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int prime[20005],m;
int v[200005];
int a[200005],s[200005],f[200005];
int n,k;
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
if(cc=='-')
{
break;
}
cc=getchar();
}
bool f=false;
int s=0;
if(cc=='-')
{
f=true;
}
else
{
s=cc-48;
}
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
if(f==true)
{
s=-s;
}
return s;
}
bool check(int minn)
{
int x=lower_bound(prime+1,prime+m+1,abs(minn)/10)-prime;
int L=max(x-1200,1);
int R=min(x+1200,m);
for(int i=1;i<=n;i++)
{
f[i]=f[i-1];
for(int j=L;j<=R&&prime[j]<=i;j++)
{
if(f[i-prime[j]]+1<=f[i])
{
break;
}
if(s[i]-s[i-prime[j]]>=minn)
{
f[i]=f[i-prime[j]]+1;
break;
}
}
if(f[i]>=k)
{
return true;
}
}
return false;
}
int main()
{
for(int i=2;i<=200000;i++)
{
if(v[i]==0)
{
v[i]=i;
m++;
prime[m]=i;
}
for(int j=1;j<=m;j++)
{
if(prime[j]>v[i]||i*prime[j]>200000)
{
break;
}
v[i*prime[j]]=prime[j];
}
}
int T;
cin>>T;
while(T--)
{
cin>>n>>k;
int smax=INT_MIN,smin=INT_MAX;
int curmin=0,curmax=0;
for(int i=1;i<=n;i++)
{
a[i]=read1();
s[i]=s[i-1]+a[i];
smax=max(smax,s[i]-curmin);
smin=min(smin,s[i]-curmax);
curmin=min(curmin,s[i]);
curmax=max(curmax,s[i]);
}
if(n/2<k)
{
puts("impossible");
continue;
}
int l=smin,r=smax;
while(l<r)
{
int mid=(l+r+1)>>1;
if(check(mid))
{
l=mid;
}
else
{
r=mid-1;
}
}
cout<<l<<endl;
}
return 0;
}
标签：prime,
200005,
子段,
int,
mid,
cin,
cc,
最优
From： https://www.cnblogs.com/watersail/p/18334189