[CSP-S模拟测试]:Median（暴力+模拟）

题目描述

定义两个数列：

$$S=\{S(1),S(2),...,S(n)\}\text{和}S_2\{S_2(1),S_2(2),...,S_2(n)\}$$

$$S(k)=(p_k\times k)\mod w,where\ p_k\ is\ the\ kth\ prime\ number$$

$$S_2(k)=S(k)+S(\left\lfloor\frac{k}{10}\right\rfloor+1)$$

令$M(i,j)$表示$S_2(i)$到$S_2(j)$的中位数（个数为奇数就是中间的数，否则为中间的两个数除以二）。现给定$n,k$，求：

$$\sum \limits_{i=1}^{n-k+1}M(i,i+k-1)$$

输入格式

输入只有一行，为三个正整数$n,k,w$（同题意）。

输出格式

输出只有一行，为所求的答案。如果答案不是整数，使用$.5$表示一半，否则用$.0$

样例

样例输入1：

100 10 10007

样例输出1：

387895.5

样例输入2：

100000 10000 10007

样例输出2：

897586519.5

数据范围与提示

对于$20\%$的数据，$n,k\leqslant 6,000$
对于另外$30\%$的数据，$n,k\leqslant 10,000$
对于另外$20\%$的数据，$w=3$
对于$100\%$的数据，$w\leqslant k\leqslant n\leqslant 10^7$

题解

首先，想说一下我在考试的时候的思路（毕竟对着这道$T1$刚了一个小时……）

$10^7$的数据范围$n\log n$可能差不多，于是我想到了$Splay$……

然后我就打了，还以为$A$了这道题。

然后忽然想到筛素数不能只筛到$10^7$，我们需要$10^7$个素数，当场歇逼……

因为我发现要筛到$179424673$……

然后我就打算从$w$入手，推式子，找规律，最后啥也没发现，于是我只筛到了$10^7$，因为我觉得多了会$T$（学校$OJ$太菜）……

然而正解告诉我们，就是要筛到$179424673$……

因为$OJ$太才，于是标程$T$掉了，老师把时限开到了$4s$并重测，那些筛到$179424673$的人（本来都$T$飞了……）都拿到了$70$分，然而我差点跌出了前$10$……

擦干眼泪，笑面未来！！！

于是我们开始讲这道题……

思考一个类似莫队的思路，也类似滑动窗口叭～

维护一个指针指向中位数，挪动窗口时更新位置即可（$k$是偶数时维护两个即可）。

总之这是一道卡常题，$\Theta(n\log n)$的做法就别想了，因为它是这样的$\downarrow$

然后我去尝试了正解$\downarrow$

其实我也不知道我到底哪里把常数给写大了，总之别人的是这样的$\downarrow$

然而我就筛个素数就$\downarrow$

时间复杂度：$\Theta(179424673+n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int n,k,w;

int S1[10000001],S2[10000001];

int prime[10000001],cnt;

int t[10000001];

char vis[179424674];

double ans;

void pre_work()

{

	for(int i=2;i<179424674;i++)

	{

		if(!vis[i])prime[++cnt]=i;

		for(int j=1,x;j<=cnt&&(x=i*prime[j])<179424674;j++)

		{

			vis[x]=1;

			if(!(i%prime[j]))break;

		}

	}

}

int main()

{

	pre_work();

	scanf("%d%d%d",&n,&k,&w);

	for(long long i=1;i<=n;i++)S1[i]=prime[i]*i%w;

	for(int i=1;i<=n;i++)S2[i]=S1[i]+S1[i/10+1];

	for(int i=1;i<k;i++)t[S2[i]]++;

	if(k&1)

	{

		int median=(k>>1)+1;

		int lst=0;

		int hand=-1;

		for(int i=k;i<=n;i++)

		{

			t[S2[i]]++;

			if(S2[i]<=hand)lst++;

			if(i>k)

			{

				t[S2[i-k]]--;

				if(S2[i-k]<=hand)lst--;

			}

			while(lst<median)lst+=t[++hand];

			while(lst>=median+t[hand])lst-=t[hand--];

			ans+=hand;

		}

	}

	else

	{

		int median=(k>>1);

		int lst1=0,lst2=0;

		int hand1=-1,hand2=-1;

		for(int i=k;i<=n;i++)

		{

			t[S2[i]]++;

			if(S2[i]<=hand1)lst1++;

			if(S2[i]<=hand2)lst2++;

			if(i>k)

			{

				t[S2[i-k]]--;

				if(S2[i-k]<=hand1)lst1--;

				if(S2[i-k]<=hand2)lst2--;

			}

			while(lst1<median)lst1+=t[++hand1];

			while(lst2<median+1)lst2+=t[++hand2];

			while(lst1>=median+t[hand1])lst1-=t[hand1--];

			while(lst2>=median+1+t[hand2])lst2-=t[hand2--];

			ans+=(double)(hand1+hand2)/2;

		}

	}

	printf("%.1lf",ans);

	return 0;

}

rp++

巴特西