2022年CSP-X复赛真题及题解（T3：动物园）

2022年CSP-X复赛真题及题解T3动物园题目描述某动物园里有n nn个场馆和m mm种动物m ≤ n m \le nm≤n。n nn个场馆的编号分别用1 , 2 , 3 , ⋯ , n 1,2,3, \cdots , n1,2,3,⋯,n表示m mm种动物的编号分别用1 , 2 , 3 , ⋯ , m 1,2,3, \cdots , m1,2,3,⋯,m表示。每一个场馆中只饲养了一只动物不同的场馆可能饲养着相同种类的动物。这个动物园的门票比较特殊游客在购买门票时必须说明要参观的场馆的起止编号a aa和b bb起止编号会打印到游客购买的门票上代表游客只能参观动物园的第a aa个场馆至第b bb个场馆包含a , b a,ba,b里的动物其他的场馆不能去。门票按一个场馆十元收费。如果你购买的门票的起止场馆编号是3 33到8 88那么你需要花60 6060元钱购买门票只能观看3 , 4 , 5 , 6 , 7 , 8 3,4,5,6,7,83,4,5,6,7,8号场馆的动物。小明希望看到动物园内所有种类的动物同时小明是个非常节约的孩子他希望花最少的钱买门票。 请你帮小明计算他最少需要花费多少钱买门票才能看到所有种类的动物同一种动物他可能不止看一个。注意小明只能买一张门票。输入格式第一行两个整数n , m n,mn,m分别表示动物园内的场馆数量及动物种类数量。第二行是x 1 , x 2 , ⋯ , x n x_1,x_2, \cdots ,x_nx1​,x2​,⋯,xn​其中x i x_ixi​表示第i ii个场馆中的动物种类编号。输出格式一行一个整数p pp表示小明的门票费用。输入输出样例 1输入 112 5 2 5 3 1 3 2 4 1 1 5 4 3输出 160说明/提示对于30 % 30\%30%的数据有 $ n \le 200 , m \le 20$。对于60 % 60\%60%的数据有n ≤ 1000 , m ≤ 1000 n \le 1000 , m \le 1000n≤1000,m≤1000。对于100 % 100\%100%的数据有1 ≤ n ≤ 10 6 , 1 ≤ x i ≤ m ≤ 2 × 10 3 1 \le n \le 10^6,1 \le x_i \le m \le 2 \times 10^31≤n≤106,1≤xi​≤m≤2×103。思路分析这道题的本质是在长度为 n 的序列中找到一个最短的连续子区间使得该子区间包含所有 m 种动物即包含 1…m 的所有数字。最终门票费用 最短子区间长度 × 10。解法滑动窗口双指针窗口定义用左指针l和右指针r表示当前考察的区间[l, r]。扩展右指针每次将r右移一位把新场馆的动物加入窗口。用一个计数数组c记录每种动物在当前窗口内出现的次数。如果某种动物的数量从 0 变为 1说明窗口新覆盖了一种动物将已覆盖种类数cov加 1。收缩左指针当cov m时说明当前窗口已经包含所有动物种类。此时尝试移动左指针l来缩小窗口同时更新最短长度len。每移出左边界的一个动物将其计数减 1如果减到 0则cov减 1。重复此过程直到窗口不再包含所有种类。记录答案每次cov m时窗口长度r-l1就是一个可行解取最小值。最终费用最短长度len乘以 10 即为答案。时间复杂度 O(n)空间复杂度 O(m)满足 n ≤ 1e6, m ≤ 2000 的限制。代码实现#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,m;cinnm;vectorintx(n1);// 场馆动物种类下标1..nfor(inti1;in;i){cinx[i];}vectorintc(m1,0);// 当前窗口内每种动物的数量intcov0;// 当前窗口已包含的种类数intl1;// 窗口左边界intlenn1;// 最短窗口长度初始化为大于n的值for(intr1;rn;r){// 右指针向右扩展inttx[r];// 当前右边界动物种类c[t];// 加入窗口if(c[t]1){// 该动物第一次出现cov;// 覆盖种类数增加}while(covm){// 窗口已包含所有种类尝试收缩左边界intcurr-l1;// 当前窗口长度if(curlen){lencur;// 更新最短长度}intltx[l];// 左边界动物种类c[lt]--;// 移出窗口if(c[lt]0){// 该动物在窗口中消失cov--;// 覆盖种类数减少}l;// 左指针右移}}intplen*10;// 门票费用 场馆数 × 10元coutpendl;return0;}功能分析输入处理读取场馆数量 n、动物种类数 m以及 n 个场馆内饲养的动物种类编号保证编号在 1…m 之间。核心算法使用滑动窗口技术维护一个动态区间[l, r]通过右指针扩展和左指针收缩找到覆盖所有 m 种动物的最短连续子区间。计数与判断利用计数数组c记录窗口内每种动物的出现次数并用变量cov记录当前覆盖的种类数当cov m时满足条件。结果输出将最短子区间长度乘以 10输出最小门票费用单位元。算法效率时间复杂度 O(n)空间复杂度 O(m)。2022年CSP-X复赛真题及题解T3动物园题目描述某动物园里有n nn个场馆和m mm种动物m ≤ n m \le nm≤n。n nn个场馆的编号分别用1 , 2 , 3 , ⋯ , n 1,2,3, \cdots , n1,2,3,⋯,n表示m mm种动物的编号分别用1 , 2 , 3 , ⋯ , m 1,2,3, \cdots , m1,2,3,⋯,m表示。每一个场馆中只饲养了一只动物不同的场馆可能饲养着相同种类的动物。这个动物园的门票比较特殊游客在购买门票时必须说明要参观的场馆的起止编号a aa和b bb起止编号会打印到游客购买的门票上代表游客只能参观动物园的第a aa个场馆至第b bb个场馆包含a , b a,ba,b里的动物其他的场馆不能去。门票按一个场馆十元收费。如果你购买的门票的起止场馆编号是3 33到8 88那么你需要花60 6060元钱购买门票只能观看3 , 4 , 5 , 6 , 7 , 8 3,4,5,6,7,83,4,5,6,7,8号场馆的动物。小明希望看到动物园内所有种类的动物同时小明是个非常节约的孩子他希望花最少的钱买门票。 请你帮小明计算他最少需要花费多少钱买门票才能看到所有种类的动物同一种动物他可能不止看一个。注意小明只能买一张门票。输入格式第一行两个整数n , m n,mn,m分别表示动物园内的场馆数量及动物种类数量。第二行是x 1 , x 2 , ⋯ , x n x_1,x_2, \cdots ,x_nx1​,x2​,⋯,xn​其中x i x_ixi​表示第i ii个场馆中的动物种类编号。输出格式一行一个整数p pp表示小明的门票费用。输入输出样例 1输入 112 5 2 5 3 1 3 2 4 1 1 5 4 3输出 160说明/提示对于30 % 30\%30%的数据有 $ n \le 200 , m \le 20$。对于60 % 60\%60%的数据有n ≤ 1000 , m ≤ 1000 n \le 1000 , m \le 1000n≤1000,m≤1000。对于100 % 100\%100%的数据有1 ≤ n ≤ 10 6 , 1 ≤ x i ≤ m ≤ 2 × 10 3 1 \le n \le 10^6,1 \le x_i \le m \le 2 \times 10^31≤n≤106,1≤xi​≤m≤2×103。思路分析这道题的本质是在长度为 n 的序列中找到一个最短的连续子区间使得该子区间包含所有 m 种动物即包含 1…m 的所有数字。最终门票费用 最短子区间长度 × 10。解法滑动窗口双指针窗口定义用左指针l和右指针r表示当前考察的区间[l, r]。扩展右指针每次将r右移一位把新场馆的动物加入窗口。用一个计数数组c记录每种动物在当前窗口内出现的次数。如果某种动物的数量从 0 变为 1说明窗口新覆盖了一种动物将已覆盖种类数cov加 1。收缩左指针当cov m时说明当前窗口已经包含所有动物种类。此时尝试移动左指针l来缩小窗口同时更新最短长度len。每移出左边界的一个动物将其计数减 1如果减到 0则cov减 1。重复此过程直到窗口不再包含所有种类。记录答案每次cov m时窗口长度r-l1就是一个可行解取最小值。最终费用最短长度len乘以 10 即为答案。时间复杂度 O(n)空间复杂度 O(m)满足 n ≤ 1e6, m ≤ 2000 的限制。代码实现#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(0);intn,m;cinnm;vectorintx(n1);// 场馆动物种类下标1..nfor(inti1;in;i){cinx[i];}vectorintc(m1,0);// 当前窗口内每种动物的数量intcov0;// 当前窗口已包含的种类数intl1;// 窗口左边界intlenn1;// 最短窗口长度初始化为大于n的值for(intr1;rn;r){// 右指针向右扩展inttx[r];// 当前右边界动物种类c[t];// 加入窗口if(c[t]1){// 该动物第一次出现cov;// 覆盖种类数增加}while(covm){// 窗口已包含所有种类尝试收缩左边界intcurr-l1;// 当前窗口长度if(curlen){lencur;// 更新最短长度}intltx[l];// 左边界动物种类c[lt]--;// 移出窗口if(c[lt]0){// 该动物在窗口中消失cov--;// 覆盖种类数减少}l;// 左指针右移}}intplen*10;// 门票费用 场馆数 × 10元coutpendl;return0;}功能分析输入处理读取场馆数量 n、动物种类数 m以及 n 个场馆内饲养的动物种类编号保证编号在 1…m 之间。核心算法使用滑动窗口技术维护一个动态区间[l, r]通过右指针扩展和左指针收缩找到覆盖所有 m 种动物的最短连续子区间。计数与判断利用计数数组c记录窗口内每种动物的出现次数并用变量cov记录当前覆盖的种类数当cov m时满足条件。结果输出将最短子区间长度乘以 10输出最小门票费用单位元。算法效率时间复杂度 O(n)空间复杂度 O(m)。更多内容请关注专栏信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}