2025NOIP模拟赛19总结

ǒεγδφψωζ

2025-08-14 16:54:15

发布于：陕西

4阅读

0回复

0点赞

T1	T2	T3	T4
${\color{green}提高+}{\color{blue}/省选-}$	${\color{blue}提高+/省选−}$	${\color{purple}省选/NOI−}$	${\color{purple}省选/NOI−}$

赛场传送门点此

感谢@Zzqyoung的大力支持《==大佬

T1 人才计数【NOIP2025模拟赛T1】

题目传送门点此

题目难度： ${\color{green}提高+}{\color{blue}/省选-}$

（典型的绿的发蓝）

思路：

首先，我们发现此问题可以转化为隐问题：给定一个数组，询问q次，查找在区间 $l_i$ 和 $r_i$ 间有多少个区间。

我们可以发现一共分为4种情况:

1.和区间正好吻合( $l_i$ ==x && $r_i$ ==y)

2.(就是 $l_i$ ==x)

3.右端点重合(就是 $r_i$ ==y)

4.完全抱起( $l_i$ <x && $r_i$ >y)

不知道各位大佬怎么想的，我这个蒟蒻直接就想的暴力分。于是我们发现：首先，如果 $r<l_{逆天}$ ，则答案一定是0；其次我们可以维护一个数组，在每次询问时统计在 $x_i$ ~ $y_i$ 之间满足4种情况的区间数（全部用bt,吻合用qsc,左端点lsc,右端点rsc）;

由于每个学生都有去和不去2种情况，所以写个快速幂（qpow中a可以不要）所以我们计算ans

$ans= (2^{bt}-2^{bt-lsc}-2^{bt-rsc}+2^{bt-lsc-rsc+qsc})\%mod$

30pts（Time Exceeded）

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+5;
const int mod=1e9+7;
int n,q,x1,x2;
int l[maxn],r[maxn],qw,wq;
int qpow(int a, int b) {
	int res=1;
	while(b!=0) {
		if(b%2==1)res=res*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return res;
}
void work(){
	//freopen("4.in","r",stdin);
	//freopen("qw.txt","w",stdout);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>l[i]>>r[i];
	}
	for(int i=1;i<=q;i++){
		cin>>qw>>wq;
		if(qw>wq){
			cout<<"0\n";
			continue;
		}
		int bt=0;
		int lsc=0,rsc=0,qsc=0,ans;
		for(int u=1;u<=n;++u){
			if(l[u]>=qw && r[u]<=wq){
				bt++;
				if(l[u]==qw && r[u]==wq){
					qsc++;
				}
				if(l[u]==qw){
					lsc++;
				}if(r[u]==wq){
					rsc++;
				}
			}
		}
		ans=(qpow(2,bt)-qpow(2,bt-lsc)-qpow(2,bt-rsc)+qpow(2,bt-lsc-rsc+qsc))%mod;
		cout<<(ans+mod)%mod<<"\n";
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}

众所周知，考完试不补题会死，所以我们考虑维护一棵树状数组。这时再分别考虑他们对答案的贡献：
如果选择了情况 1那么剩下的可以随便选，共 $(2^{a}-1)(2^{b+l+r})$ 否则就必须选（至少）一个情况2和情况3: $2^b(2^l-1)(2^r-1)$ 。

$ans$

$=(2^a-1)(2^{b+l+r})+2^b(2^l-1)(2^r-1)$

$=2^{a+b+l+r}-2^{b+l+r}+2^{b+l+r}-2^{b+l}-2^{b+r}+2^b$

$=2^{a+b+l+r}-2^{b+l}-2^{b+r}+2^b$

Tips: l=x 并且 r=y 个数为 a，l=x 并且 r<y 个数为 l，x<l 并且 r=y 个数为 r，x<l 并且 r<y 个数为 b

虽然有思路了，但是本蒟蒻的手上还是空空，所以这里采纳一个大佬(Zzqyoung)的代码作为本题的：

AC code

T3 调色板【NOIP2025模拟赛T3】

题目传送门 [点此](https://oj.33dai.cn/d/TYOI/p/N0724?tid=68919c89c5d9c2f14c1a537f

题目难度： ${\color{purple}省选/NOI-}$

在此感谢 ${\color{cyan}@Lucas16}$ 为我们的文艺生活提供帮助。

思路：

直接打表。如果表打对了，很容易看出 No 的情况：若 $gcd(n,m)>1$ ，即 n,m 不互质则答案为 No。否则一定为 Yes。
构造如下：

a数组:$ 1,1+m,1+2m,...,1+(n-1)m$

b 数组:$ 1,1+n,1+2n,...,1+(m−1)n $

由于$ n,m $互质，容易证明在 $n,m \geq 2n,m\geq2$ 时上述构造在模nm意义下乘积可以构成 0,1,...,nm-10,1,...,nm−1。
需要注意 n=1n=1 或 m=1m=1 的时候需要特判：

1、n=m=1:
a 数组:0
b 数组:0

2、n=1或m=1（不妨设 n = 1):
aa 数组: 1
bb 数组: 0,1,...,m-1

总时间复杂度为 O(n)。

AC code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t;
signed main(){
	ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m;
		if(__gcd(n,m)>1){
			cout<<"No\n";
			continue;
		}
		cout<<"Yes\n";
		for(int i=1;i<=n;i++) cout<<i*m-1<<' ';
		cout<<'\n';
		for(int i=1;i<=m;i++) cout<<i*n-1<<' ';
		cout<<'\n';
		
	}
	return 0;
}