noip模拟21

开题发现这场考过，定睛一看，发现是省选前最后一场，没改过呀……但是还是讲武德的赛时没提交

A. Median

神奇之处在于 \(1e7\) 个质数居然能线性筛出来~

那么 \(S2\) 可以直接筛出来

接着就是求一个值域 \(2*10^7\) 的数列的固定区间动态中位数

首先各种 \(log\) 算法很好想但是过不了

必须是线性

如果排不了序很难受，可以用桶排来实现

由于数据等同于随机，那么每次暴力移动指针期望复杂度很低，直接暴力扫即可

但是写起来非常难写……

对于 \(k\) 为偶数时考虑维护两个指针，对应两个中位数，并维护出小于等于两个指针的值的个数，如果有一边大于 \(k/2\) 那么移动即可

代码实现

#include<bits/stdc++.h>

using namespace std;

const int MAXN=180000000;

const int MAX=2e7;

const int maxn=1e7+15;

int vis[MAXN+10],pri[maxn],tot,n,k,w,s[maxn],a[maxn],cnt[maxn],cnt1,cnt2,tp1,tp2,sum;

long long ans;

void pre(){

	for(int i=2;i<=MAXN;i++){

		if(!vis[i]){

			vis[i]=i;

			pri[++tot]=i;

		}

		for(int j=1;j<=tot;j++){

			if(1ll*pri[j]*i>MAXN||pri[j]>vis[i])break;

			vis[pri[j]*i]=pri[j];

		}

	}

	return ;

}

int main(){

//	freopen("shuju.in","r",stdin);

//	freopen("my.out","w",stdout);

	pre();

	cin>>n>>k>>w;

	for(int i=1;i<=n;i++){

		a[i]=1ll*pri[i]*i%w;

		s[i]=a[i]+a[i/10+1];

//		cout<<s[i]<<" ";

	}

//	cout<<endl;

	for(int i=1;i<=k;i++){

		cnt[s[i]]++;

	}

	if(k&1){

		for(int i=1;i<=MAX;i++){

			sum+=cnt[i];

			if(sum>=k/2+1){

				if(k&1){

					cnt1=sum-cnt[i];

					cnt2=k-sum;

					tp1=tp2=i;

				}

				break;

			}

			if(cnt[i])tp1=i;

		}

		ans+=tp1+tp2;

		int num=k/2;

		for(int i=1;i<=n-k;i++){

			int last=s[i];

			int now=s[i+k];

			cnt[last]--;

			cnt[now]++;

			cnt1+=-(last<tp1)+(now<tp1);

			cnt2+=-(last>tp1)+(now>tp1);

			while(cnt1>num){

				cnt2+=cnt[tp1];

				tp1--;

				cnt1-=cnt[tp1];

			}

			while(cnt2>num){

				cnt1+=cnt[tp1];

				tp1++;

				cnt2-=cnt[tp1];

			}

			ans+=tp1*2;

//			cout<<tp1<<endl;

		}

	}

	else{

		int num=k/2;

		tp1=tp2=-1;

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

			if(i!=k)cnt[s[i]]++;

			if(s[i]<=tp1)cnt1++;

			if(s[i]<=tp2)cnt2++;

			if(i>k){

				cnt[s[i-k]]--;

				if(s[i-k]<=tp1)cnt1--;

				if(s[i-k]<=tp2)cnt2--;

			}

			while(cnt1<num)cnt1+=cnt[++tp1];

			while(cnt2<num+1)cnt2+=cnt[++tp2];

			while(cnt1>=num+cnt[tp1])cnt1-=cnt[tp1--];

			while(cnt2>=num+1+cnt[tp2])cnt2-=cnt[tp2--];

			ans+=tp1+tp2;

		}

	}

	if(ans&1)printf("%lld.5",ans/2);

	else printf("%lld.0",ans/2);

	return 0;

}

B. Game

首先题意理解清楚了随便打个 \(log\) 算法比较轻松，但是这题还是得 \(O(n)\) 过

相当于维护一个数集，支持加数、取最大值操作，这个还用桶排实现即可

C. Park

神奇的 \(dp\) 题

首先发现作为起点是独特的，贡献为周围点权和，其他地方都需要减去父亲节点的权值

那么需要区分起点和终点，可以设 \(f[u][i]\) 表示以 \(u\) 为根的子树里从某个点为起点到点 \(u\) 的路径撒了 \(i\) 次的最大收获

\(g[u][i]\) 表示从 \(u\) 开始到从 \(u\) 到以 \(u\) 为根子树内一点作为终点的的路径撒了 \(i\) 次的最大收获

那么更新答案为 \(f[u][i]+g[v][m-i]\)，考虑更新：

\[f[u][i]=max(f[v][i],f[v][i-1]+sum[u]-a[v])
\]

\[g[u][i]=max(g[v][i],g[v][i-1]+sum[u]-a[father])
\]

初始化为 \(f[u][i]=sum[u]\)，\(g[u][i]=sum[u]-a[father]\)

实现的时候还有一个问题：由于一个是起点另一个是终点，更新答案是根据儿子的顺序来更新的，那么遍历的顺序是有影响的，还需要倒的扫一遍

代码实现

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int maxn=1e5+5;

const int maxm=2e5+5;

int n,m,hd[maxn],cnt,f[maxn][105],g[maxn][105],ans,x,y,a[maxn],sta[maxn],tp,sum[maxn];

int read(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch)){

		x=x*10+ch-48;

		ch=getchar();

	}

	return x*f;

}

struct Edge{

	int nxt,to;

}edge[maxm];

void add(int u,int v){

	edge[++cnt].nxt=hd[u];

	edge[cnt].to=v;

	hd[u]=cnt;

	return ;

}

void dfs(int u,int father){

	for(int i=1;i<=m;i++){

		f[u][i]=sum[u];

		g[u][i]=sum[u]-a[father];

	}

	for(int i=hd[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==father)continue;

		dfs(v,u);

		for(int j=0;j<=m;j++){

			ans=max(ans,f[u][j]+g[v][m-j]);

		}

		for(int j=1;j<=m;j++){

			f[u][j]=max(f[u][j],max(f[v][j],f[v][j-1]+sum[u]-a[v]));

			g[u][j]=max(g[u][j],max(g[v][j],g[v][j-1]+sum[u]-a[father]));

		}

	}

	for(int i=hd[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==father)continue;

		sta[++tp]=v;

	}

	for(int i=1;i<=m;i++){

		f[u][i]=sum[u];

		g[u][i]=sum[u]-a[father];

	}

	while(tp){

		int v=sta[tp--];

		for(int j=0;j<=m;j++){

			ans=max(ans,f[u][j]+g[v][m-j]);

		}

		for(int j=1;j<=m;j++){

			f[u][j]=max(f[u][j],max(f[v][j],f[v][j-1]+sum[u]-a[v]));

			g[u][j]=max(g[u][j],max(g[v][j],g[v][j-1]+sum[u]-a[father]));

		}

	}

	return ;

}

signed main(){

	n=read();

	m=read();

	for(int i=1;i<=n;i++){

		a[i]=read();

	}

	for(int i=1;i<=n-1;i++){

		x=read();

		y=read();

		add(x,y);

		add(y,x);

		sum[x]+=a[y];

		sum[y]+=a[x];

	}

	dfs(1,0);

	cout<<ans;

	return 0;

}

巴特西

noip模拟21

A. Median

B. Game

C. Park

最新文章

热门文章