NOIP2025模拟赛20总结

ǒεγδφψωζ

2025-08-14 16:53:37

发布于：陕西

3阅读

0回复

0点赞

T1	T2	T3	T4
${\color{#FFC116} 普及/提高− }$	${\color{#52C41A} 普及+/提高}$	${\color{purple} 提高+/省选− }$	${\color{black} NOI/NOI+ }$

参赛网址：https://oj.33dai.cn/d/TYOI/contest/68976ba8c5d9c2f14c1e8556

简单题够简单，难题够难

T1 酸碱平衡【2025NOIP模拟赛T1】

题目传送门

题目难度： ${\color{#FFC116} 普及/提高− }$

算法标签：二阶差分

思路

_{略，直接模拟}

考虑因为每一个位置不会被后面的任何一个位置更改，所以当从左到右枚举到 $i$ 时，必须把它改成零。

然后就有了暴力 $60$

60pts

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=2e5+5;
int n,c;
int ans;
int a[maxn];

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++)	cin>>a[i];
	for (int i=1;i<=n;i++){
		int t=-a[i];
		ans+=abs(t);
		for (int j=i;j<=n;j++)	a[j]+=t*(j-i+1);
	}
	cout<<ans;
	return 0;
}

然后考虑优化：

题解是二维差分
_{可能是因为我差分学的太烂，所以没想到。} 我们考虑对于每个 $i$ 的影响，应该是 $i-1$ 的影响再加上前面的操作次数。

然后就 ${\color{#fb5555} 100 Wrong Answer}$ ...

还要开 __int128

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=2e5+5;
int n;
__int128 ans;
int a[maxn];

void print(__int128 num){
	if(num>9)	print(num/10);
	putchar(num%10+'0');
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++)	cin>>a[i];
	int las=0,c=0;
	for (int i=1;i<=n;i++){
		a[i]+=c;
		int t=-a[i];
		ans+=abs(t);
		c+=(las+2*t);
		las+=t;
	}
	print(ans);
	return 0;
}

T2 排序【2025NOIP模拟赛T2】

题目传送门

题目难度： ${\color{#52C41A} 普及+/提高}$

算法标签：贪心，优先队列

思路

20pts

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=2e5+5;
int n,p,q;
int ans;
int a[maxn],b[maxn];

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>p>>q;
	for (int i=1;i<=n;i++)	cin>>a[i];
	ans=a[q]-a[p];
	for (int l=p;l>=1;l--){
		for (int r=q;r<=n;r++){
			for (int i=l;i<=r;i++)	b[i]=a[i];
			sort(b+l,b+r+1);
			ans=max(ans,b[q]-b[p]);
		}
	}
	cout<<ans;
	return 0;
}

然后我们考虑一共其实只有 $2$ 种情况:

$l=p$
$r=q$

我们发现分别对于情况1,2,： $a_l$ 和 $a_r$ 是已知的。

所以只要开一个大根堆和一个小根堆，分别维护 $p$ 到 $r$ 的最大值和 $l$ 到 $q$ 的最小值，当堆的大小大于 $q-p+1$ 时，直接弹掉。

AC Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn=2e5+5;
int n,p,q;
int ans;
int a[maxn],b[maxn];
priority_queue<int> Q;
priority_queue<int,vector<int>,greater<int> > P;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>p>>q;
	for (int i=1;i<=n;i++)	cin>>a[i];
	int Max=a[q],Min=a[p];
	for (int i=q;i>=1;i--){
		Max=max(Max,a[i]);
		P.push(a[i]);
		if (q-p+1<P.size())	P.pop();
		ans=max(ans,Max-P.top());
	}
	for (int i=p;i<=n;i++){
		Min=min(Min,a[i]);
		Q.push(a[i]);
		if (q-p+1<Q.size())	Q.pop();
		ans=max(ans,Q.top()-Min);
	}
	cout<<ans;
	return 0;
}