| 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 \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. 构造方法的有效性
目标：按照
的方式进行构造，证明若 \(c_{i_1,j_1} = c_{i_2,j_2}\)，则 \(i_1 = i_2\) 且 \(j_1 = j_2\)。
中国剩余定理（CRT)
因 \(\gcd(n, m) = 1\)，故：
1：证明 \(i_1 = i_2\)
由 \(c_{i_1,j_1} = c_{i_2,j_2}\)，结合 CRT 得：
计算 \(b_j \bmod n\)：
代入式 \((1)\)：
计算 \(a_i \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 \bmod m\)：
代入式 \((2)\)：
计算 \(b_j \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
T4 猜点权【NOIP2025模拟赛T4】
题目传送门
题目难度：\({\color{#9D3DCF} 省选/NOI− }\)
算法标签：搜索，线性代数，高斯消元，交互
