当前位置：首页 > news >正文

NOIP2025模拟赛19

news 2025/9/14 8:26:57

T1	T2	T3	T4
\({\color{#3498DB} 提高+/省选− }\)	\({\color{#3498DB} 提高+/省选− }\)	\({\color{#9D3DCF} 省选/NOI− }\)	\({\color{#3498DB} 提高+/省选− }\)

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

T2,T4搭建未完成

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

题目传送门

题目难度：\({\color{#3498DB} 提高+/省选− }\)

算法标签：数据结构，线段树，树状数组，组合数学
，容斥原理

思路

我们发现，这个题的本质是：
求一个区间内，左端点的最小值是 \(l\)，右端点的最大值是 \(r\) 的选择数量。

包含在一个区间（不妨设这个区间的左端点是 \(x\) ，右端点是 \(y\) )内的区间（不妨设这个区间的左端点是 \(l\) ，右端点是 \(r\)）共有 \(4\) 种情况：

\(l=x\) 并且 \(r=y\) 个数为 \(a\)
\(l=x\) 并且 \(r<y\) 个数为 \(l\)
\(x<l\) 并且 \(r=y\) 个数为 \(r\)
\(x<l\) 并且 \(r<y\) 个数为 \(b\)

然后我们分别考虑他们对答案的贡献：

如果选择了情况 \(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\)

_{于是就结束了}

_然后喜提

\(30pts\)

#include <bits/stdc++.h>
#define int long long
using namespace std;const int maxn=2e5+5;
const int mod=1e9+7;
int n,Q;
int l[maxn],r[maxn];
int x[maxn],y[maxn];int p(int a,int b){int res=1;if (b==0)	res=1;else if (b==1)	res=a%mod;else if (b==2)	res=a*a%mod;else	res=p(p(a,b>>1),2)*p(a,b&1);return res;
}signed main(){
//	freopen("3.in","r",stdin);
//	freopen("t3.out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cin>>n>>Q;for (int i=1;i<=n;i++)	cin>>l[i]>>r[i];for (int i=1;i<=Q;i++)	cin>>x[i]>>y[i];for (int i=1;i<=Q;i++){int ans=0;int cnt_l=0,cnt_r=0,cnt=0,num=0;for (int j=1;j<=n;j++){if (x[i]<=l[j]&&r[j]<=y[i])	num++;else	continue;if (l[j]==x[i]&&r[j]==y[i])	cnt++;else if (l[j]==x[i])	cnt_l++;else if (r[j]==y[i])	cnt_r++;}int num_l=p(2,cnt_l)-1;int num_r=p(2,cnt_r)-1;int tot=p(2,cnt)-1;ans+=num_l*num_r%mod*p(2,num-cnt-cnt_l-cnt_r)%mod;ans%=mod;ans+=tot*p(2,num-cnt);ans%=mod;cout<<ans<<"\n";}return 0;
}

反正到这里本蒟蒻还是不会~

最后在随便优化一下：

_还在写aaa

QAQ

T2 江桥的随机字典树【NOIP2025模拟赛T2】

题目传送门

题目难度：\({\color{#3498DB} 提高+/省选− }\)

算法标签：组合数学，数论

T3 调色板【NOIP2025模拟赛T3】

题目传送门

题目难度：\({\color{purple} 省选/NOI− }\)

算法标签：其他，打表，构造

由于大样例具有明显的提示性，因此本题不提供大样例。

思路

通过打表等方式，可以发现无解当且仅当 \(\gcd(n,m)>1\)，即 \(n\) 和 \(m\) 不互质。

然后就是构造在模 \(nm\) 意义下 \(0 \dots nm\)。

我们可以发现：

\(a_{1 \dots n}=1,m+1,2\times m+1 \dots (n-1) \times m+1\)

\(b_{1 \dots m}=1,n+1,2\times n+1 \dots (m-1) \times n+1\)

AC code

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

附：严格证明--来自cpp_xhq

@cpp_xhq

我们用严格的数学语言证明代码的正确性：

1. 解的存在性条件

定理：存在数组 \(a \in [0, nm)^n\) 和 \(b \in [0, nm)^m\) 使得所有 \(c_{i,j} = (a_i \cdot b_j) \bmod (nm)\) 互不相同，当且仅当 \(\gcd(n, m) = 1\)。

必要性

假设存在合法解， \(\gcd(n, m) = d > 1\)。
令 \(n = d \cdot n',\ m = d \cdot m'\)，则 \(nm = d^2 n' m'\)。
对任意 \(a_i, b_j\)，有：

\[a_i \cdot b_j \equiv (a_i \bmod d) \cdot (b_j \bmod d) \bmod d \]

由于 \(a_i \bmod d \in \{0, 1, ..., d-1\}\) 且 \(b_j \bmod d \in \{0, 1, ..., d-1\}\)，乘积模 \(d\) 最多有 \(d^2\) 种可能。
但需要覆盖 \(nm = d^2 n' m'\) 个不同值，根据抽屉原理，必存在 \(c_{i,j} = c_{i',j'}\)，矛盾。故 \(\gcd(n, m) = 1\)。

下证此构造满足所有 \(c_{i,j}\) 互不相同。

2. 构造方法的有效性

目标：按照

\[\begin{align*} a_i &= (i \cdot m + m - 1) \bmod (nm) \quad (1 \leq i \leq n) \\ b_j &= (j \cdot n + n - 1) \bmod (nm) \quad (1 \leq j \leq m) \\ c_{i,j} &= (a_i \cdot b_j) \bmod (nm) \end{align*} \]

的方式进行构造，证明若 \(c_{i_1,j_1} = c_{i_2,j_2}\)，则 \(i_1 = i_2\) 且 \(j_1 = j_2\)。

中国剩余定理（CRT)

因 \(\gcd(n, m) = 1\)，故：

\[x \equiv y \bmod (nm) \iff x \equiv y \bmod n \text{且} x \equiv y \bmod m \]

1：证明 \(i_1 = i_2\)

由 \(c_{i_1,j_1} = c_{i_2,j_2}\)，结合 CRT 得：

\[(a_{i_1} \cdot b_{j_1}) \equiv (a_{i_2} \cdot b_{j_2}) \bmod n \tag{1} \]

计算 \(b_j \bmod n\)：

\[b_j = j \cdot n + (n-1) \implies b_j \equiv -1 \bmod n \]

代入式 \((1)\)：

\[a_{i_1} \cdot (-1) \equiv a_{i_2} \cdot (-1) \bmod n \implies a_{i_1} \equiv a_{i_2} \bmod n \]

计算 \(a_i \bmod n\)：

\[a_i = i \cdot m + (m-1) \implies a_i \equiv m \cdot i + (m-1) \bmod n \]

故：

\[m \cdot i_1 + (m-1) \equiv m \cdot i_2 + (m-1) \bmod n \implies m(i_1 - i_2) \equiv 0 \bmod n \]

因 \(\gcd(n, m) = 1\)，故 \(i_1 \equiv i_2 \bmod n\)。又 \(i_1, i_2 \in [1, n]\)，得 \(i_1 = i_2\)。

2：证明 \(j_1 = j_2\)

同理，由 \(c_{i_1,j_1} = c_{i_1,j_2}\)，结合 CRT 得：

\[(a_{i_1} \cdot b_{j_1}) \equiv (a_{i_1} \cdot b_{j_2}) \bmod m \tag{2} \]

计算 \(a_i \bmod m\)：

\[a_i = i \cdot m + (m-1) \implies a_i \equiv -1 \bmod m \]

代入式 \((2)\)：

\[(-1) \cdot b_{j_1} \equiv (-1) \cdot b_{j_2} \bmod m \implies b_{j_1} \equiv b_{j_2} \bmod m \]

计算 \(b_j \bmod m\)：

\[b_j = j \cdot n + (n-1) \implies b_j \equiv n \cdot j + (n-1) \bmod m \]

故：

\[n \cdot j_1 + (n-1) \equiv n \cdot j_2 + (n-1) \bmod m \implies n(j_1 - j_2) \equiv 0 \bmod m \]

因 \(\gcd(n, m) = 1\)，故 \(j_1 \equiv j_2 \bmod m\)。又 \(j_1, j_2 \in [1, m]\)，得 \(j_1 = j_2\)。

结论

当 \(\gcd(n, m) \neq 1\) 时，无解（输出 "No"）。
当 \(\gcd(n, m) = 1\) 时，构造的 \(a, b\) 数组满足所有 \(c_{i,j}\) 互不相同（输出 "Yes" 及数组）。

所以

#include<bits/stdc++.h>
using namespace std;
#define int long long
long long n,m;long long gcd(long long  a,long long b) { return b==0?a:gcd(b,a%b); }
long long lcm(long long a,long long b) { return a/gcd(a,b)*b; }void solve()
{cin>>n>>m;if(gcd(n,m)!=1){cout<<"No"<<endl;return;}cout<<"Yes"<<endl;for(int i=1;i<=n;i++) cout<<(i*m+(m-1))%(n*m)<<" ";cout<<endl;for(int i=1;i<=m;i++) cout<<(i*n+(n-1))%(n*m)<<" ";cout<<endl;
}signed main()
{int TT; for(cin>>TT;TT;TT--) solve();return 0;
}

代码完全正确。

https://www.luogu.com.cn/article/d721tys7