HackerRank Week of Code 26

时间:2021-07-09 09:28:00

好像这次week of code不是很难= =

A

int main(){
int n;
int m;
cin >> n >> m;
cout<<(n+1)/2*int((m+1)/2)<<"\n";
return 0;
}

B

求n的因数中数字和最大的前提下最小的数,n<=10^5,大模拟。

int n;
pii qwq;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
if(n%i) continue;
int cur=0;
for(int j=i;j;j/=10) cur+=j%10;
qwq=max(qwq,pii(cur,-i));
}
printf("%d\n",-qwq.se);
}

C

求[n,m]之间的孪生素数对数,1<=n,m<=10^9,m-n<=10^6。

暴力rabin-miller好像卡不过去= = 只要用根号m以内的素数来筛就行。

bool rp[2333333];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int s=2;s*s<=m;s++)
{
int g=n/s;
for(int p=g*s;p<=m;p+=s)
{
if(p>=n&&p>s) rp[p-n]=1;
}
}
if(n<=1) rp[1-n]=1;
int qwq=0;
for(int j=n+2;j<=m;j++)
{
if(!rp[j-n]&&!rp[j-n-2]) ++qwq;
}
printf("%d\n",qwq);
}

D

有n个点把数轴分成了n+1段,要求选出一段长度为m的线段使得经过的每一段长度在hmin~hmax之间,输出任意一个起始点,保证有解。n<=10^6,输入都是1e9范围。

如果hmin<=m<=hmax的话特判一发,否则可以发现左右端点一定与某一个点重合,二分找到段的位置,注意细节...

这题好像数据比较弱,部分错误做法也能过(我也不知道我交的第一发是怎么过的= =)

下面这个应该是对的(拍过)

#define SZ 2333333
int n;
ll a[SZ],h1,h2,m;
bool safe(int x)
{
return h1<=a[x+1]-a[x]&&a[x+1]-a[x]<=h2;
}
int qzs[SZ];
void chk(int i,int r)
{
//cout<<i<<","<<r<<"chk\n";
if(i>=r||i<0||r<0||r>n||i>n) return;
//cout<<i<<","<<r<<"chk2\n";
if(qzs[r-1]-qzs[i]!=r-i-1) return;
//cout<<i<<","<<r<<"chk3\n";
int s=m-(a[r]-a[i+1]);
ll l1=h1,r1=min(h2,a[i+1]-a[i]);
ll l2=h1,r2=min(h2,a[r+1]-a[r]);
//cout<<l1<<","<<r1<<" "<<l2<<","<<r2<<" "<<s<<"\n";
if(l1<=r1&&l2<=r2);else return;
int l=max(s-r2,l1),R=min(s-l2,r1);
if(l>R) return;
cout<<a[i+1]-l<<"\n";
exit(0);
}
//(a[i],a[i+1]]
int bl(int x)
{
return lower_bound(a+1,a+1+n,x)-a-1;
}
int main()
{
scanf("%d",&n);
a[n+1]=1e13; a[0]=-1e13;
for(int i=1;i<=n;i++) scanf("%lld",a+i);
scanf("%lld%lld%lld",&m,&h1,&h2);
for(int i=0;i<n;i++) qzs[i]=(i?qzs[i-1]:0)+safe(i);
if(h1<=m&&m<=h2)
{
puts("1000000000");
return 0;
}
for(int i=0;i<n;i++)
{
int bx;
bx=bl(a[i+1]-1-m); chk(bx,i);
bx=bl(a[i+1]-m); chk(bx,i);
bx=bl(a[i+1]+1-m); chk(bx,i+1);
bx=bl(a[i]+m); chk(i-1,bx);
bx=bl(a[i]+1+m); chk(i,bx);
bx=bl(a[i]-1+m); chk(i-1,bx);
}
puts("-233333333");
}

E

给出一个整数n,求正整数对(a,b) (a<b)的对数使得x*a+y*b=n,x、y为正整数。n<=30W。

我们考虑对于一个a,枚举x*a,然后对于y*b判一下n-x*a。

那么问题来了,一个a可能会被算多次。

我们有一个简单粗暴的方式,把这些a全记下来unique一下。

然后好像跑的挺快的就过了[滑稽]

所以说我们要相信玄学

int n;
vector<int> tt[300005];
bool rs[300005];
int main()
{
ll qwq=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
vector<int> rp;
for(int j=i;j<=n;j+=i)
{
vector<int>& cc=tt[n-j];
for(int g:cc) rp.pb(g);
}
for(int g:rp) rs[g]=1;
for(int g:rp) qwq+=rs[g], rs[g]=0;
for(int j=i;j<=n;j+=i) tt[j].pb(i);
}
printf("%lld\n",qwq);
}

我们来讲讲道理,前30W个数平均有15.9385个因数,这样做的复杂度大致就是225*30W,应该还是很快的 [滑稽]

题解好像十分奥妙重重,看不懂啊= =

F

求sin(x)+sin(y)+sin(z)的最大值,x+y+z=n且x、y、z均为正整数,n<=3000000,显然是弧度制。

我们假装x+y=s,那么z=n-s。

sin(x)+sin(y)=sin(x)+sin(s-x)=sinx+sinscosx-cosssinx=sinx(1-coss)+cosxsins

我们用一下辅助角公式,令α=atan(sins/(1-coss)),那么sin(x)+sin(y)就等于K*sin(x+α)(K是多少就不管了)

sin(g)最大就是让|g-pi/2|最大(当然这里的g要被限制在[0,2pi]),sin(x+α)最大就是让|x+a-pi/2|最大,就是让x与pi/2-a最接近,我们把所有满足条件的x插到map里去,查询一下相邻的两个就行了。

我们从大到小枚举z,然后s是递增的,所以x的上限也是递增的,把这些x一个一个插进去然后在map里查询就行了。

尴尬的是这样是300W*log(300W)的,会被卡常。我们考虑假装z是最小的,就变成100W*log(300W)了,再结合一些优秀的卡常技巧就可以卡过= =

注意因为要保留九位小数,只能把x、y、z带入原式算不然就会炸精度。

int p;
ld pi=acos(-1);
map<ld,int> ss;
ld st2(ld x)
{
if(x<0) x+=pi+pi;
if(x>=pi+pi) x-=pi+pi;
return x;
}
int main()
{
scanf("%d",&p);
pair<ld,int> minn,maxn;
minn.fi=1e233; maxn.fi=-1e233;
ld ans=0;
int upm=min(p/3+1,p-2);
int g=1;
for(int x=p-2;x>=1;x--)
{
int n=p-x;
while(g*(pi+pi)<=n-1) ++g;
ld cc=n-1-(g-1)*(pi+pi);
minn=min(minn,make_pair(cc,n-1));
maxn=max(maxn,make_pair(cc,n-1));
ss[cc]=n-1;
if(x<=upm)
{
//sinx(1-cosn)+cosx*sinn
ld g=st2(atan(sin(n)/(1-cos(n))));
ld mx=max(sin(minn.se)+sin(n-minn.se),
sin(maxn.se)+sin(n-maxn.se));
ld r=st2(-g+pi/2);
//min|x-r|
auto aa=ss.lower_bound(r);
if(aa==ss.end());
else mx=max(mx,sin(aa->se)+sin(n-aa->se));
if(aa==ss.begin());
else
{
--aa;
mx=max(mx,sin(aa->se)+sin(n-aa->se));
}
ld cur=mx+sin(x);
if(cur>ans) ans=cur;
}
}
printf("%.9lf\n",ans);
}

当然既然敢出300W肯定有线性做法= =

官方题解不知道高到哪里去了,首先把sin(x)+sin(y)改写成2*sin((x+y)/2)*cos((x-y)/2),然后从2~n-1枚举x+y,显然z已经确定了,那么就只要查询最大的cos((x-y)/2)就行了。

HackerRank Week of Code 26(很难看出)如果从x+y=s变成x+y=s+2只会多出两种x-y,例如:

HackerRank Week of Code 26

我猜接下来的事情就不用我说了...分奇偶遍历的时候顺便更新最大值即可。

int n;
int main()
{
scanf("%d",&n);
ld mi=0,ans=0;
for(int s=2;s<n;s+=2)
{
//x+y=s max{x-y}=s-2
mi=max(mi,cos((s-2)/2));
ans=max(ans,2*sin(s/2)*mi+sin(n-s));
}
mi=0;
for(int s=3;s<n;s+=2)
{
//x+y=s max{x-y}=s-2
mi=max(mi,cos((s-2)/2.0));
ans=max(ans,2*sin(s/2.0)*mi+sin(n-s));
}
printf("%.9lf\n",ans);
}

G

题面和nim游戏有关,大概就是求n个[1,2^m)之间不同的数使异或和不为0(考虑顺序),模1e9+7输出。n,m<=10^7。

不会做...官方题解大概是这样的。

记i堆异或和为0的方案数为fi,那么:

$f_i=A(2^m-1,i-1)-f_{i-1}-(i-1)*(2^m-1-(i-2))*f_{i-2}$

A(x,y)就是x个元素选y个排列的方案数。官方题解这个公式打错了

是不是感觉这个公式有了就做完了呢?[生无可恋]

以下是讲道理环节。

首先我们考虑异或和不为0,这个简单,A(2^m-1,i-1),随便选i-1个不同的排在前面,最后一个就是它们的异或和。

然后我们考虑异或完之后肯定是在[0,2^m)之内的,但是这个0要扣掉,显然这前i-1个元素异或完为0的方案数就是f[i-1]。

尴尬了,现在重复了。那么什么情况会重复呢?显然我们选出来的前i-1个元素是两两不同的,那么只可能这个异或和和之前的元素重复了。那么除掉这个重复的元素,剩下i-2个元素异或和就要为0!这两个元素必须和剩下的i-2个元素不同,那就是有2^m-1-(i-2)种权值,前i-1个元素都可能充当这个重复元素,那么(i-1)*(2^m-1-(i-2))*f[i-2]就可以得到这部分了。

显然0不可能和之前的元素重复,那么都扣掉就行了。

int n,m;
ll MOD=1e9+7;
ll qp(ll a,ll b)
{
a%=MOD;
ll aa=1;
while(b)
{
if(b&1) aa=aa*a%MOD;
a=a*a%MOD; b>>=1;
}
return aa;
}
#define SZ 23333333
ll a[SZ],f[SZ];
int main()
{
scanf("%d%d",&n,&m);
ll tot=qp(2,m)-1;
a[1]=tot;
for(int i=2;i<=n;i++)
a[i]=a[i-1]*(tot-i+1)%MOD;
f[0]=1;
for(int i=2;i<=n;i++)
f[i]=(a[i-1]-f[i-1]-(i-1)*(tot-(i-2))%MOD*f[i-2]%MOD)%MOD;
ll ans=a[n]-f[n];
ans=(ans%MOD+MOD)%MOD;
printf("%lld\n",ans);
}