切排列
题意简化
给定两个长度为 $ n $ 的 1~n的排列 $ A $ 和 $ B $,需将 $ A $ 切成若干段,再按任意顺序拼接得到 $ B $,求最少需要切的段数 $ k $ 的最小值。
数据范围
- 测试组数 $ T : 1 \leq T \leq 10^4 + 5 $;
- 每组排列长度 $ n : 1 \leq n \leq 2 \times 10^5 $;
- 所有测试用例的 $ n $ 之和:$ \sum n \leq 5 \times 10^5 + 16 $;
- $ A 、 B $ 均为$ 1 \sim n $的排列(每个数恰好出现一次)。
思路
直接贪心,枚举a中每一个数,检验他在b数组中是否连续
点击查看代码
#include<bits/stdc++.h>using namespace std;
int t;
const int maxn=2e5+10;
int n;
int a[maxn],b[maxn];
int c[maxn]; void solve(){cin>>n;for(int i=1;i<=n;++i){cin>>a[i];c[a[i]]=i;} for(int i=1;i<=n;++i) cin>>b[i];int ans=0;for(int i=1;i<=n;++i){while(c[b[i]]==c[b[i+1]]-1){++i;}++ans;}cout<<ans<<endl;return ;
}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>t;while(t--){solve();} return 0;
}
k-MEX
题意简化
给定正整数 $ n $ 和 $ k $,从 $ 0,1,\dots,n-1 $ 中随机选取 $ k $ 个不同的整数组成集合,求该集合的 MEX(最小未出现的自然数) 的期望。结果以最简分数 $ \frac{x}{y} $ 形式给出,需对 $ 10^9+7 $ 取模后输出。
数据范围
- 测试用例组数 $ T : 1 \leq T \leq 10^4 + 7 $;
- 每组的 $ n,k : 1 \leq k \leq n \leq 10^9 $。
思路
要计算从 $ 0,1,\dots,n-1 $ 中选 $ k $ 个不同整数的集合的 MEX(最小未出现自然数) 期望,核心过程如下:
步骤1:期望的转换
对于非负整数随机变量 $ X = \text{MEX} $,期望满足 $ E[X] = \sum_{i=1}^{\infty} P(X \geq i) $(因为 $ \text{MEX} $ 最大为 $ k $,只需求和到 $ i=k $)。
步骤2:分析 $ P(\text{MEX} \geq i) $
若 $ \text{MEX} \geq i $,则集合必须包含 $ 0,1,\dots,i-1 $ 所有元素。此时:
- 需从剩余 $ n - i $ 个元素($ i $ 到 $ n-1 $)中选 $ k - i $ 个,选法数为 $ \binom{n-i}{k-i} $;
- 总选法数为 $ \binom{n}{k} $(从 $ n $ 个中选 $ k $ 个)。
因此:
$ P(\text{MEX} \geq i) = \frac{\binom{n-i}{k-i}}{\binom{n}{k}} $
步骤3:化简求和式
对 $ i=1 $ 到 $ k $ 求和 $ \sum_{i=1}^{k} \frac{\binom{n-i}{k-i}}{\binom{n}{k}} $,重点化简分子部分 $ \sum_{i=1}^{k} \binom{n-i}{k-i} $。
利用组合数累加性质(杨辉三角递推:$ \binom{m}{r} + \binom{m}{r+1} = \binom{m+1}{r+1} $),逐步累加后,分子和最终化简为 $ \binom{n}{k-1} $。
步骤4:计算组合数比值
$ 分子为 \binom{n}{k-1} ,分母为 \binom{n}{k} $
利用组合数公式化简:
$ \frac{\binom{n}{k-1}}{\binom{n}{k}} = \frac{\frac{n!}{(k-1)!(n-k+1)!}}{\frac{n!}{k!(n-k)!}} = \frac{k}{n - k + 1} $
最终结论
MEX的期望为:
$ \boxed{\frac{k}{n - k + 1}} $
点击查看代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod= 1e9 + 7;ll power(ll a, ll b) {ll res = 1;for (; b; b /= 2, a = a * a % mod) if (b & 1) res = res * a % mod;return res;
}void solve() {ll n, k;cin >> n >> k;cout << power(n - k + 1, mod - 2) * k % mod << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int _ = 1;cin >> _;while (_--) {solve();}return 0;
}
最小值
题意
给定 $ T $ 组数据,每组包含两个长度为 $ n $ 的整数数组 $ a $ 和 $ b $,需找出所有满足 $ p \neq q $ 的下标对,计算 $ \left| \left| a_p - a_q \right| - \left| b_p - b_q \right| \right| $ 的值,并求出这些值中的最小值。
数据范围
- 测试组数 $ T \(:\) 1 \leq T \leq 10^4 $;
- 每组数组长度 $ n \(:\) 2 \leq n \leq 10^5 $,且所有测试用例的 $ n $ 之和 $ \sum n \leq 5 \times 10^5 $;
- 数组元素绝对值:$ |a_i| \leq 10^{12} \(,\) |b_i| \leq 10^{12} $。
思路
步骤1:表达式转换(分类讨论)
通过对 $ a_p 与 a_q 、 b_p 与 b_q $ 的大小关系分类讨论,可证明:
具体分类(核心逻辑):
- 当 $ (a_p - a_q)(b_p - b_q) \geq 0 $ 时,$ \left| |a_p - a_q| - |b_p - b_q| \right| = \left| (a_p - b_p) - (a_q - b_q) \right| $;
- 当 $ (a_p - a_q)(b_p - b_q) < 0 $ 时,$ \left| |a_p - a_q| - |b_p - b_q| \right| = \left| (a_p + b_p) - (a_q + b_q) \right| $;
且进一步可证,原表达式是这两个新表达式的较小值。
构造新数组并排序
根据上述结论,构造两个新数组:
- $ A_i = a_i + b_i $
- $ B_i = a_i - b_i $
对数组 $ A $ 和 $ B $ 分别排序(排序后,数组中“最小的绝对差”一定出现在相邻元素之间)。
找相邻元素的最小差
对排序后的 $ A $ 和 $ B $,分别计算相邻元素的绝对差,并记录各自的最小差。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;void sovle()
{int n;cin>>n;vector<ll> a(n),b(n),j,k;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)cin>>b[i];for(int i=0;i<n;i++){j.push_back(a[i]+b[i]);k.push_back(a[i]-b[i]);}sort(j.begin(),j.end());sort(k.begin(),k.end());ll minj=1e15,mink=1e15;for(int i=1;i<n;i++){if(j[i]-j[i-1]<minj)minj=j[i]-j[i-1];if(k[i]-k[i-1]<mink)mink=k[i]-k[i-1];}cout<<min(minj,mink)<<endl;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) {sovle();}return 0;
}
随机反馈
题意
在一场时长为 $ n $ 分钟的编程比赛中,每分钟提交一次正确代码。第 $ i $ 分钟提交的正确代码,有 $ p_i = \frac{x_i}{1000} $ 的概率被判 WA,$ 1 - p_i $ 的概率被判 AC(且第 $ n $ 分钟提交的代码必判 AC,即 $ x_n = 0 $)。
罚时定义:若第一次得到 AC 的提交时间为 $ t $,则罚时为 $ t + 20 \times (t - 1) $( t-1 是之前的提交次数);若始终未 AC,罚时为无穷大。需计算最小的罚时期望。
数据范围
- 测试组数 $ T $:正整数。
- 每组比赛时长 $ n : 1 \leq n \leq 10^5 $,所有测试用例的 $ n $ 之和 $ \leq 5 \times 10^5 $。
- 每组的 $ x_1, x_2, \dots, x_n $:满足 $ 0 \leq x_i \leq 1000 $,且 $ x_n = 0 , p_i = \frac{x_i}{1000} $。
思路
要推导比赛罚时期望的通用计算公式,可通过递推法分析:
1. 问题建模
- 第 $ i $ 分钟提交正确代码时,得 AC 的概率为 $ a_i = 1 - p_i $(其中 $ p_i = \frac{x_i}{1000} $),且第 $ n $ 分钟必 AC($ x_n = 0 $,故 $ a_n = 1 $)。
- 若第一次 AC 在第 $ t $ 分钟,罚时为 $ \text{罚时}_t = t + 20(t - 1) = 21t - 20 $。
2. 递推关系推导
定义 $ f(t) $ 为从第 $ t $ 分钟开始提交的期望罚时。需满足:
- 边界条件:第 $ n $ 分钟必 AC,故 $ f(n) = 21n - 20 $。
- 递推式($ t < n $ 时):第 $ t $ 分钟有 $ a_t $ 概率 AC(罚时 $ 21t - 20 $),有 $ p_t $ 概率 WA(后续从 $ t+1 $ 分钟开始,期望罚时为 $ f(t+1) $)。因此:\[f(t) = a_t \cdot (21t - 20) + p_t \cdot f(t+1) \]其中 $ a_t = 1 - p_t , p_t = \frac{x_t}{1000} $。
3.结论
最小期望罚时可通过从后往前的线性递推计算,递推式为:
最终结果为 $ f(1) $,时间复杂度 $ O(n) $,可高效处理 $ n \leq 10^5 $ 的数据。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n,m,k;
const int maxn=2e5+10;
double f[maxn];
int x[maxn];
void sovle(){cin>>n;for(int i=1;i<=n;++i) f[i]=1e9;for(int i=1;i<=n;++i) cin>>x[i]; f[n]=n; for(int i=n-1;i>=1;--i){double p=x[i]*1.0/1000.0;f[i]=min(f[i+1],(1.0-p)*i+p*(f[i+1]+20));}double ans=1e9;for(int i=1;i<=n;++i) ans=min(ans,f[i]);cout<<fixed<<setprecision(10)<<ans<<endl;return ;
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int T;cin >> T;while (T--) {sovle();}return 0;
}
信赖跃迁:置换轨迹计算
题意简化
给定长度为 $ n $ 的置换 $ q $,以及长度为 $ m $ 的整数序列 $ k_1, k_2, \dots, k_m $,需计算满足以下条件的长度为 $ m+1 $ 的置换序列 $ p_0, p_1, \dots, p_m $ 的数量:
(其中 $ \circ $ 表示置换的复合运算,$ p_i^{k_i} $ 表示置换 $ p_i $ 的 $ k_i $ 次幂)。
数据范围
- 测试组数 $ t : 1 \leq t \leq 10 $;
- 每组中置换长度 $ n : 1 \leq n \leq 10^5 $;
- 每组中序列长度 $ m : 1 \leq m \leq 10^5 $;
- 置换 $ q $:由 $ 0 \sim n-1 $ 组成的有效置换(元素不重复);
- 序列元素 $ k_i : 1 \leq k_i \leq 10^5 $。
思路
利用$ p_0 $ 由其余置换唯一确定”的性质,将问题转化为计算 $ m $ 个任意置换的组合数,最终得到 $ (n!)^m $ 的模结果。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;vector<ll> F(100005);void pre() {F[0] = 1;for (int i = 1; i <= 1e5; i++) {F[i] = F[i - 1] * i % mod;}
}ll power(ll a, ll b) {ll res = 1;for (; b; b /= 2, a = a * a % mod) if (b & 1) res = res * a % mod;return res;
}void solve() {ll n, m;cin >> n >> m;vector<ll> a(n), b(m);for (ll i = 0; i < n; i++) {cin >> a[i];}for (ll i = 0; i < m; i++) {cin >> b[i];}cout << power(F[n], m) << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);pre();int _ = 1;cin >> _;while (_--) {solve();}return 0;
}
题意简化
需给 $ n $ 人发放总金额为 $ m $ 元的报酬,每月发放一次。为避税,需满足三个条件:
- 每人单笔收入严格不超过 $ k $ 元;
- 每月发放人数严格不超过 $ p $ 人;
- 每人累计收入严格不超过自身的 $ a_i $ 元(即最终收到的总钱数 $ \leq a_i $)。
求收完所有报酬的最少月数。
数据范围
- 测试组数 $ T : 1 \leq T \leq 10004 $;
- 每组数据:
- 人数 $ n $、总报酬 $ m $、单笔最大金额 $ k $、每月最多发放人数 $ p : 1 \leq p \leq n \leq 2 \times 10^5 , 1 \leq k \leq m \leq 10^9 $;
- 每人的“缴税前剩余可收金额” $ a_1, a_2, \dots, a_n : 1 \leq a_i \leq 10^9 $,且 $ \sum a_i \geq m $;
- 单个测试点中,所有组的 $ n $ 之和 $ \sum n \leq 4 \times 10^5 + 14 $。
思路
很明显时间足够长一定是可以不交税的,时间很短也是必交税的
因此考虑二分答案
检验:
贪心策略最大化每月发放金额
验证某月数 mid 是否可行时,核心是计算该月数内 最多能发放的总金额,并与 m 比较。为最大化总金额,采用两步贪心:
-
优先发放“整 k 元”:每人每月最多发 k 元,优先计算所有人在mid 个月内最多能被发放 整 k 元 的总次数(最大化单次发放金额)。
-
用大额零钱填补空闲名额:若整 k 元的发放次数未填满每月 p 人的名额,则用每人剩余的零钱$ a_i % k $填补,且优先使用最大的零钱(通过提前降序排序实现),充分利用空闲名额。
预处理优化验证效率
对每人的零钱($ a_i % k $)提前降序排序,确保在填补空闲名额时能快速获取最大零钱,减少验证阶段的计算成本,使整体算法高效适配大数据范围。
点击查看代码
#include<bits/stdc++.h>using namespace std;
int t;
#define int long long
const int maxn=2e5+10;
using ll=long long ;int n,m,p,k;
int a[maxn];bool check(int mid){int cnt=0;//所有人可以给cnt次k元 在所有月份中 vector<int>s;for(int i=1;i<=n;++i){if(a[i]>=mid*k) cnt+=mid;//可以每个月都给这人k else cnt+=a[i]/k,s.push_back(a[i]%k); //这个人只能给有限次月 }// 如果每个月都能给p个人k元 if(cnt>=mid*p) return mid*p*k>=m;ll sum=cnt*k;//否则,还能在未选够p个人的月份,选入剩下的 for(int i=0;i<min(mid*p-cnt,(int)s.size());++i){sum+=s[i];} return sum>=m;}
void solve(){cin>>n>>m>>k>>p;for(int i=1;i<=n;++i) cin>>a[i];sort(a+1,a+1+n,[](auto x,auto y){return x%k>y%k;});int l=1,r=1e9;while(l<=r){int mid=(l+r)>>1;if(check(mid)) r=mid-1;else l=mid+1; }cout<<l<<endl;return ;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin>>t;while(t--){solve();} return 0;
}