NOIP2022模拟赛 1

,

NOIP2022 模拟赛 1 题解

T1

Description

$p_i$ 为第 $i$ 个质数。

$S_i=(p_i\times i)\mod w$

$P_i=S_i+S_{i/10+1}$，$i/10$ 向下取整。

$M(i,j)$ 表示 $P_i,P_{i+1},…,P_j$ 的中位数。

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

$w\le k\le n\le 1e7$

2s，512G。

Solution

首先，2s 是可以筛 2e8 个数中的质数的。大约为 1.1e7 个。

所以可以 $O(2e8)$ 的时间内求出 $S,P$ 。

因为 $S,P$ 非常随机，可以看为在 $w$ 中的随机分布。

每次更改两个点，对中位数的影响可以看为常数级别的。暴力即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define maxn 20000005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int n,k,mod;
bitset<200000005>vis;
int prime[maxn],cnt;
inline void oula(int n) {
	int i,j;vis[1]=1;
	for (i=2;i<=n;i++) {
		if (!vis[i]) prime[++cnt]=i;
		for (j=1;j<=cnt&&i*prime[j]<=n;j++){
			vis[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
}
inline int S(int x) {
	return 1ll*prime[x]*x%mod;
}
inline int S2(int x) {
	return S(x)+S(x/10+1);
}
int t[maxn];
signed main(void){
    int i,j;ll ans=0;
    srand(time(0));
	read(n);read(k);read(mod);
	oula(200000000);
	int now=0,sum=0,now2=0,sum2=0;
	for (i=1;i<k;i++) t[S2(i)]++;
	if (k%2==1) {
		for (i=k;i<=n;i++) {
			t[S2(i)]++;
			if (S2(i)<=now) sum++;
			while (sum<(k+1)/2) now++,sum+=t[now];
			while (sum-t[now]>=(k+1)/2) sum-=t[now],now--;
			if (k&1) ans+=now;
			t[S2(i-k+1)]--;
			if (S2(i-k+1)<=now) sum--; 
		} 
		if (k&1) printf("%lld.0",ans);
	}
	else {
		for (i=k;i<=n;i++) {
			t[S2(i)]++;
			if (S2(i)<=now) sum++;
			if (S2(i)<=now2) sum2++;
			while (sum<k/2) now++,sum+=t[now];
			while (sum-t[now]>=k/2) sum-=t[now],now--;
			while (sum2<k/2+1) now2++,sum2+=t[now2];
			while (sum2-t[now2]>=k/2+1) sum2-=t[now2],now2--;
			ans+=now+now2;
			t[S2(i-k+1)]--;
			if (S2(i-k+1)<=now) sum--; 
			if (S2(i-k+1)<=now2) sum2--; 
		}
		printf("%.1lf",1.0*ans/2);
	}
	return 0;
}

反思：2s 是可以筛 2e8 个数中的质数的。不确定的情况下打代码验证。

T2

同 P6294 [eJOI2017]游戏

Solution

暴力的复杂度显然是 $O(nk\log n)$ 的。用堆模拟即可。

类似于 prufer 序列的求解。不需要考虑人类智慧数据结构。

把 $a_1$ 到 $a_{p_i}$ 放入一个桶中。指针 id 指向最大的权值。若新加入的数 $x$ 大于当前指针，则直接选新加入的数；否则 $x$ 对应的桶更新，指针更新到当前第二小的权值。

注意到指针是只会越来越小，扫一遍的复杂度是 $O(n)$ 的。

$k$ 次询问，复杂度就是 $O(nk)$ 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int n,k,a[maxn];
namespace BL{
	priority_queue<int>q;
	inline void solve(void) {
		int i,m,x,ans1=0,ans2=0;
		while (!q.empty()) q.pop();
		read(m);
	    for (i=1;i<=m;i++) q.push(a[i]);
	    for (i=1;i<=n;i++) {
	    	if (i&1) ans1+=q.top(),q.pop();
	    	else ans2+=q.top(),q.pop();
	        if (i<=n-m) q.push(a[i+m]);
		}
		printf("%d\n",ans1-ans2);
	} 
    inline void main(void) {
    	int i;
		while (k--) solve();
	}
}//暴力
namespace STD{
	int t[maxn];
    inline void main(void) {
    	int i,now,m;
    	while (k--) {
    		now=0;ll ans=0;
    		read(m);
    		for (i=1;i<=m;i++) t[a[i]]++,now=max(now,a[i]);
			ans+=now;t[now]--;
			for (i=2;i<=n;i++) {
				if (i<=n-m+1) {
					if (a[i+m-1]>=now) {ans+=(i%2==0?-1:1)*a[i+m-1];continue;}
				    t[a[i+m-1]]++;
				}
				while (t[now]==0) now--;
				ans+=(i%2==0?-1:1)*now;t[now]--;
			}
			printf("%lld\n",ans);  
		}
	}
}
signed main(void){
	int i;
	read(n);read(k);
	for (i=1;i<=n;i++) read(a[i]);
	STD::main();
	return 0;
}

T3

同 P4657 [CEOI2017]Chase

Solution

设 $f[i][j]$ 表示 $i$ 到 $i$ 子树内的一点的最多撒 $j$ 的最大权值，$g[i][j]$ 表示 $i$ 子树内一点到 $i$ 最多撒 $j$ 的最大权值。

$in_i$ 表示 $i$ 周围的点（不包括 $i$ ） 的权值。

容易得到转移方程：

$f_{i,j}=\max(f_{i,j},f_{i,j-1},f_{son,j},f_{son,j-1}+in_i-w_{son})$

$g_{i,j}=\max(g_{i,j},g_{i,j-1},g_{son,j},g_{son_j}+in_i-w_{fa})$

更新答案：

$ans=\max(ans,f_{i,j}+g_{son,v-j},f_{i,v},g_{i,v})$

注意到两条路径不能同时经过 $i$ 的同一个儿子，所以正反做一遍。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define maxn 100005
#define int long long
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
	int f=1;x=0;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
	x*=f;
}
int in[maxn],w[maxn],n,v,ans=0;
vector<int> to[maxn];
int f[maxn][105],g[maxn][105];
inline void dfs(int x,int pre) {
	int i,j,y;
	f[x][0]=g[x][0]=0;for (i=1;i<=v;i++) f[x][i]=in[x],g[x][i]=in[x]-w[pre];
	for (auto y:to[x]) 
	    if (y^pre) {
	    	dfs(y,x);
			for (j=0;j<=v;j++) ans=max(ans,f[x][j]+g[y][v-j]);
	    	for (j=1;j<=v;j++) {
	    		f[x][j]=max(max(max(f[x][j-1],f[x][j]),f[y][j]),f[y][j-1]+in[x]-w[y]);
	    		g[x][j]=max(max(max(g[x][j-1],g[x][j]),g[y][j]),g[y][j-1]+in[x]-w[pre]);
			}
		}
	f[x][0]=g[x][0]=0;for (i=1;i<=v;i++) f[x][i]=in[x],g[x][i]=in[x]-w[pre];
	for (i=to[x].size()-1;i>=0;i--){
		y=to[x][i];
		if (y^pre) {
			for (j=0;j<=v;j++) ans=max(ans,f[x][j]+g[y][v-j]);
	    	for (j=1;j<=v;j++) {
	    		f[x][j]=max(max(max(f[x][j-1],f[x][j]),f[y][j]),f[y][j-1]+in[x]-w[y]);
	    		g[x][j]=max(max(max(g[x][j-1],g[x][j]),g[y][j]),g[y][j-1]+in[x]-w[pre]);
			}
		}
	}
	ans=max(ans,max(f[x][v],g[x][v]));
}
signed main(void){
	freopen("ex_chase2.in","r",stdin);
	int i,x,y;
	read(n);read(v);
	memset(f,-0x3f,sizeof(f));
	memset(g,-0x3f,sizeof(g));
	for (i=1;i<=n;i++) read(w[i]);
	for (i=1;i<n;i++) {
		read(x);read(y);
		to[x].push_back(y);
		to[y].push_back(x);
	}
	for (i=1;i<=n;i++) {
		for (auto y:to[i]) in[i]+=w[y];	
		f[i][1]=g[i][1]=in[i];f[i][0]=g[i][0]=0;
	}
	dfs(1,0);
	printf("%lld\n",ans);
	return 0;
}