好像这次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)就行了。
（很难看出）如果从x+y=s变成x+y=s+2只会多出两种x-y，例如：
我猜接下来的事情就不用我说了...分奇偶遍历的时候顺便更新最大值即可。
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);
}