本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P2098 [USACO16DEC] Team Building P - 洛谷【题目描述】每年Farmer John 都会带着他的N NN头奶牛参加州展览会的“最佳展示”比赛。他的劲敌 Farmer Paul 也会带着他的M MM头奶牛参加比赛1 ≤ N ≤ 1000 , 1 ≤ M ≤ 1000 1 \leq N \leq 1000, 1 \leq M \leq 10001≤N≤1000,1≤M≤1000。参加比赛的N M N MNM头奶牛每头都会获得一个单独的整数得分。然而今年的最终比赛将由K KK头奶牛组成的团队决定1 ≤ K ≤ 10 1 \leq K \leq 101≤K≤10规则如下Farmer John 和 Farmer Paul 各自选择K KK头奶牛组成团队进行比赛。这两个团队的奶牛将按得分高低配对FJ 团队中得分最高的奶牛与 FP 团队中得分最高的奶牛配对FJ 团队中得分第二高的奶牛与 FP 团队中得分第二高的奶牛配对依此类推。如果在每一对中FJ 的奶牛得分都更高那么 FJ 获胜。请帮助 FJ 计算他和 FP 可以选择团队的不同方式的数量使得 FJ 能够赢得比赛。也就是说每个不同的FJ 的K KK头奶牛集合FP 的K KK头奶牛集合对只要 FJ 获胜都应被计入。输出结果对1 000 000 009 1\,000\,000\,0091000000009取模。【输入】输入的第一行包含N NN、M MM和K KK。K KK的值不会超过N NN或M MM。第二行包含 FJ 的N NN头奶牛的得分。第三行包含 FP 的M MM头奶牛的得分。【输出】输出 FJ 和 FP 可以选择团队的方式数量使得 FJ 获胜结果对1 000 000 009 1\,000\,000\,0091000000009取模。【输入样例】10 10 3 1 2 2 6 6 7 8 9 14 17 1 3 8 10 10 16 16 18 19 19【输出样例】382【核心思想】问题分析FJ 有N NN头奶牛FP 有M MM头奶牛各自选择K KK头组成团队。两团队的奶牛按得分从高到低一一配对若每一对中 FJ 的奶牛得分都严格大于 FP 的奶牛得分则 FJ 获胜。求 FJ 和 FP 选择团队的不同方式数量对10 9 9 10^9 91099取模。这是一个三维线性DP 容斥原理问题。算法选择降序排序Descending Sort将 FJ 和 FP 的得分分别按降序排序使得a [ i ] a[i]a[i]和b [ j ] b[j]b[j]分别是当前考虑范围内的最小元素三维DP3D Dynamic Programmingd p [ i ] [ j ] [ k ] dp[i][j][k]dp[i][j][k]表示从 FJ 的前i ii头奶牛和 FP 的前j jj头奶牛中选出k kk对且 FJ 每对都获胜的方案数容斥原理Inclusion-Exclusion Principle在状态转移时用容斥原理处理不选 FJ 的第i ii头和不选 FP 的第j jj头两种情况的重复计数问题关键步骤初始化读入N NN、M MM、K KK以及 FJ 的得分数组a [ 1.. N ] a[1..N]a[1..N]和 FP 的得分数组b [ 1.. M ] b[1..M]b[1..M]sort(a 1, a n 1, greaterint())FJ 得分降序排序sort(b 1, b m 1, greaterint())FP 得分降序排序边界条件d p [ i ] [ j ] [ 0 ] 1 dp[i][j][0] 1dp[i][j][0]1对于所有0 ≤ i ≤ N 0 \leq i \leq N0≤i≤N、0 ≤ j ≤ M 0 \leq j \leq M0≤j≤M选0 00对的方案数为1 11状态转移枚举团队大小k kk从1 11到K KK枚举i ii从k kk到N NNFJ 至少需要k kk头枚举j jj从k kk到M MMFP 至少需要k kk头容斥转移先计算不考虑a [ i ] a[i]a[i]和b [ j ] b[j]b[j]的方案数d p [ i ] [ j ] [ k ] d p [ i − 1 ] [ j ] [ k ] dp[i][j][k] dp[i-1][j][k]dp[i][j][k]dp[i−1][j][k]不选 FJ 的第i ii头d p [ i ] [ j ] [ k ] d p [ i ] [ j − 1 ] [ k ] dp[i][j][k] dp[i][j-1][k]dp[i][j][k]dp[i][j−1][k]不选 FP 的第j jj头d p [ i ] [ j ] [ k ] − d p [ i − 1 ] [ j − 1 ] [ k ] dp[i][j][k] - dp[i-1][j-1][k]dp[i][j][k]−dp[i−1][j−1][k]容斥去重两者都不选的情况被重复计算注意取模( x m o d ) % m o d (x mod) \% mod(xmod)%mod防止负数配对转移若a [ i ] b [ j ] a[i] b[j]a[i]b[j]可将它们作为第k kk对d p [ i ] [ j ] [ k ] d p [ i − 1 ] [ j − 1 ] [ k − 1 ] dp[i][j][k] dp[i-1][j-1][k-1]dp[i][j][k]dp[i−1][j−1][k−1]从前i − 1 i-1i−1和j − 1 j-1j−1中选k − 1 k-1k−1对再加上当前这对输出答案d p [ N ] [ M ] [ K ] dp[N][M][K]dp[N][M][K]从全部N NN头和M MM头中选K KK对的方案数时间/空间复杂度时间复杂度O ( N × M × K ) O(N \times M \times K)O(N×M×K)三维枚举K ≤ 10 K \leq 10K≤10N , M ≤ 1000 N, M \leq 1000N,M≤1000空间复杂度O ( N × M × K ) O(N \times M \times K)O(N×M×K)三维DP数组可通过滚动数组优化至O ( N × M ) O(N \times M)O(N×M)三维DP 容斥原理的核心思想降序排序的妙处排序后a [ i ] a[i]a[i]和b [ j ] b[j]b[j]是当前考虑范围内的最小值。若a [ i ] b [ j ] a[i] b[j]a[i]b[j]则对于任意p ≤ i p \leq ip≤i、q ≤ j q \leq jq≤j都有a [ p ] ≥ a [ i ] b [ j ] ≥ b [ q ] a[p] \geq a[i] b[j] \geq b[q]a[p]≥a[i]b[j]≥b[q]保证配对的单调性容斥去重技巧在计算从[ 1.. i ] [1..i][1..i]和[ 1.. j ] [1..j][1..j]中选k kk对时直接考虑不选a [ i ] a[i]a[i]和不选b [ j ] b[j]b[j]会重复计算两者都不选的情况因此需要减去d p [ i − 1 ] [ j − 1 ] [ k ] dp[i-1][j-1][k]dp[i−1][j−1][k]配对条件的处理只有在a [ i ] b [ j ] a[i] b[j]a[i]b[j]时才允许将a [ i ] a[i]a[i]和b [ j ] b[j]b[j]配成一对保证 FJ 获胜。由于降序排列当前这对的 FJ 奶牛是剩余中最弱的若能赢过 FP 最弱的则前面所有配对也一定满足条件三维状态设计d p [ i ] [ j ] [ k ] dp[i][j][k]dp[i][j][k]同时记录 FJ 前i ii头、FP 前j jj头、已选k kk对三个维度保证状态无后效性适用于组合计数、匹配方案数、带约束的选对方案类问题【算法标签】#普及 #线性DP-一维【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将 int 定义为 long long防止模运算溢出constintN1005,mod1e99;// N: 最大奶牛数量, mod: 模数intn,m,K;// n: FJ的奶牛数, m: FP的奶牛数, K: 团队大小inta[N],b[N];// a[i]: FJ第i头奶牛的得分, b[i]: FP第i头奶牛的得分// dp[i][j][k]: 从FJ的前i头奶牛和FP的前j头奶牛中选出k对使得FJ每对都获胜的方案数// 注意a和b已按降序排序所以a[i]是FJ前i头中最小的b[j]是FP前j头中最小的intdp[N][N][15];signedmain()// 使用 signed 替代 int因为 #define int long long{cinnmK;// 读入FJ奶牛数、FP奶牛数、团队大小// 读入FJ的N头奶牛得分for(inti1;in;i)cina[i];// 读入FP的M头奶牛得分for(inti1;im;i)cinb[i];// 将FJ和FP的得分按降序排序// 排序后a[i] a[i1]b[i] b[i1]// 这样dp[i][j]中a[i]和b[j]分别是当前考虑的最小元素sort(a1,an1,greaterint());sort(b1,bm1,greaterint());// 初始化选0对时方案数为1什么都不选也是一种方案for(inti0;in;i)for(intj0;jm;j)dp[i][j][0]1;// 动态规划枚举团队大小kFJ前i头FP前j头for(intk1;kK;k){for(intik;in;i)// i至少为kFJ至少需要k头奶牛{for(intjk;jm;j)// j至少为kFP至少需要k头奶牛{// 容斥原理计算不考虑a[i]和b[j]时的方案数// dp[i-1][j][k]: 不选FJ的第i头奶牛// dp[i][j-1][k]: 不选FP的第j头奶牛// 两者相加后dp[i-1][j-1][k]被重复计算了需要减去dp[i][j][k](dp[i][j][k]dp[i-1][j][k])%mod;dp[i][j][k](dp[i][j][k]dp[i][j-1][k])%mod;dp[i][j][k](dp[i][j][k]-dp[i-1][j-1][k]mod)%mod;// 如果FJ的第i头奶牛得分 FP的第j头奶牛得分// 则可以将它们配成一对作为第k对且FJ获胜// 加上从前面i-1和j-1中选k-1对的方案数if(a[i]b[j]){dp[i][j][k](dp[i][j][k]dp[i-1][j-1][k-1])%mod;}}}}// 输出答案从FJ的n头和FP的m头中选K对FJ获胜的方案数coutdp[n][m][K]endl;return0;}【运行结果】10 10 3 1 2 2 6 6 7 8 9 14 17 1 3 8 10 10 16 16 18 19 19 382