![打卡信奥刷题（3622）用C++实现信奥题 P11827 [TOIP2024] 大步小步向前走](http://pic.xiahunao.cn/yaotu/打卡信奥刷题（3622）用C++实现信奥题 P11827 [TOIP2024] 大步小步向前走)
P11827 [TOIP2024] 大步小步向前走题目背景本题的 Special Judge 由 CuteMurasame 重构以符合 -stdc14 标准。题目描述五条圣是电门中学的学生他的梦想是成为职业足球选手。虽然他因为想每天练习足球而不想去上学但为了不违反国民教育法第二章第3 33条他还是乖乖的去上学。五条圣家到学校的路是一条直线道路我们把五条圣家到学校的路以一条数线表示五条圣家在坐标0 00米处学校在坐标e ee米处。五条圣通过刻苦练习习得了k kk种前进的步法第j jj种步法可以前进恰好s j s_jsj米他希望应用这些步法在足球比赛中。为了多多练习这些步法五条圣在上学路上不会用这些步法以外的方式前进。为了避免迟到五条圣也不会往回跳只会笔直往学校前进。不幸的是这条路上有n nn个坑洞第i ii个坑洞在坐标a i a_iai米处。因此如果五条圣落脚在a i a_iai米处则他的脚会受伤导致他不能完成他足球员的梦想这是他一定要避免的。给定学校坐标、坑洞位置以及五条圣练成的步法长度五条圣想要你帮他找出最佳的迈步方式满足下列条件避开所有坑洞。最后恰好停在e ee米处。最大步法使用的次数越多越好。若存在多种最大步法次数最多的方式第二大的步法使用的次数越多越好。若还有多种方法以此类推比较第三大、第四大、⋯ \cdots⋯、第k kk大的步法次数。输入格式n nnk kke eea 1 a_1a1a 2 a_2a2a 3 a_3a3⋯ \cdots⋯a n a_nans 1 s_1s1s 2 s_2s2s 3 s_3s3⋯ \cdots⋯s k s_kskn , k , e n, k, en,k,e分别代表坑洞数、五条圣步法种类的数量以及学校坐标。第i ii个洞的坐标在a i a_iai。第j jj种步法长度为s j s_jsj。输出格式m mmp 1 p_1p1p 2 p_2p2p 3 p_3p3⋯ \cdots⋯p m p_mpmm mm为一正整数代表最佳的迈步方式总共走几步。p i p_ipi均为正整数代表第i ii步落脚在p i p_ipi米处。若答案不唯一输出任一符合所求的答案均可。若不存在任何的迈步方式输出一行− 1 -1−1。输入输出样例 #1输入 #13 2 8 1 3 4 4 2输出 #13 2 6 8输入输出样例 #2输入 #23 2 9 3 4 1 4 2输出 #2-1输入输出样例 #3输入 #30 4 61 3 5 23 30输出 #34 30 53 58 61说明/提示测试数据限制2 ≤ e ≤ 3 × 10 5 2 \le e \le 3 \times 10^52≤e≤3×105。0 ≤ n ≤ e − 1 0 \le n \le e - 10≤n≤e−1。2 ≤ k ≤ e 2 \le k \le e2≤k≤e。1 ≤ a i ≤ e − 1 1 \le a_i \le e - 11≤ai≤e−1。1 ≤ s j ≤ e 1 \le s_j \le e1≤sj≤e。1 ≤ k × ( e − n ) ≤ 3 × 10 5 1 \le k\times (e - n) \le 3 \times 10^51≤k×(e−n)≤3×105。上述变量均为整数。所有a i a_iai互不相同。所有s j s_jsj互不相同。评分说明本题共有一组子任务条件限制如下所示。每一组可有一或多组测试数据该组获得的分数 该组满分分数 × min 测试数据 ∈ 该组 评分 ( 测试数据 ) 。 该组获得的分数 该组满分分数\times \min_{测试数据 \in 该组} 评分(测试数据)。该组获得的分数该组满分分数×测试数据∈该组min评分(测试数据)。对一组测试数据考虑问题描述中提到条件的符合与否如果输出的答案不符合输出格式或不符合 1., 2., 或 3. 评分为0 00。如果输出的答案符合 1., 2., 和 3. 但不符合 4. 评分为0.2 0.20.2。如果输出的答案符合 1., 2., 3., 和 4. 但不符合 5. 评分为0.5 0.50.5。如果输出的答案符合 1., 2., 3., 4. 和 5. 评分为1 11。子任务分数额外输入限制1100 100100无额外限制。C实现#includebits/stdc.husingnamespacestd;constintN3e55,inf0x3f3f3f3f;intn,k,e,a[N];boold[N],vis[N];vectorintcnt[N];// 走到i坐标满足要求的走法intpre[N],ans[N],idd;// 从哪里来的signedmain(){cin.tie(0)-sync_with_stdio(0);cinnke;for(inti1;in;i){intx;cinx;d[x]true;}for(inti1;ik;i){cina[i];}sort(a1,ak1,greaterint());cnt[0].resize(k1);vis[0]true;for(inti1;ie;i){if(!d[i]){cnt[i].resize(k1);for(intx1;xk;x){intji-a[x];if(j0!d[j]vis[j]){vis[i]true;vectorinttmpcnt[j];tmp[x];if(cnt[i]tmp){cnt[i]tmp;pre[i]j;}}}}}if(!vis[e]){cout-1;}else{intnowe;while(now0){ans[idd]now;nowpre[now];}coutidd\n;for(intiidd;i0;i--){coutans[i] ;}}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
P11827 [TOIP2024] 大步小步向前走题目背景本题的 Special Judge 由 CuteMurasame 重构以符合 -stdc14 标准。题目描述五条圣是电门中学的学生他的梦想是成为职业足球选手。虽然他因为想每天练习足球而不想去上学但为了不违反国民教育法第二章第3 33条他还是乖乖的去上学。五条圣家到学校的路是一条直线道路我们把五条圣家到学校的路以一条数线表示五条圣家在坐标0 00米处学校在坐标e ee米处。五条圣通过刻苦练习习得了k kk种前进的步法第j jj种步法可以前进恰好s j s_jsj米他希望应用这些步法在足球比赛中。为了多多练习这些步法五条圣在上学路上不会用这些步法以外的方式前进。为了避免迟到五条圣也不会往回跳只会笔直往学校前进。不幸的是这条路上有n nn个坑洞第i ii个坑洞在坐标a i a_iai米处。因此如果五条圣落脚在a i a_iai米处则他的脚会受伤导致他不能完成他足球员的梦想这是他一定要避免的。给定学校坐标、坑洞位置以及五条圣练成的步法长度五条圣想要你帮他找出最佳的迈步方式满足下列条件避开所有坑洞。最后恰好停在e ee米处。最大步法使用的次数越多越好。若存在多种最大步法次数最多的方式第二大的步法使用的次数越多越好。若还有多种方法以此类推比较第三大、第四大、⋯ \cdots⋯、第k kk大的步法次数。输入格式n nnk kke eea 1 a_1a1a 2 a_2a2a 3 a_3a3⋯ \cdots⋯a n a_nans 1 s_1s1s 2 s_2s2s 3 s_3s3⋯ \cdots⋯s k s_kskn , k , e n, k, en,k,e分别代表坑洞数、五条圣步法种类的数量以及学校坐标。第i ii个洞的坐标在a i a_iai。第j jj种步法长度为s j s_jsj。输出格式m mmp 1 p_1p1p 2 p_2p2p 3 p_3p3⋯ \cdots⋯p m p_mpmm mm为一正整数代表最佳的迈步方式总共走几步。p i p_ipi均为正整数代表第i ii步落脚在p i p_ipi米处。若答案不唯一输出任一符合所求的答案均可。若不存在任何的迈步方式输出一行− 1 -1−1。输入输出样例 #1输入 #13 2 8 1 3 4 4 2输出 #13 2 6 8输入输出样例 #2输入 #23 2 9 3 4 1 4 2输出 #2-1输入输出样例 #3输入 #30 4 61 3 5 23 30输出 #34 30 53 58 61说明/提示测试数据限制2 ≤ e ≤ 3 × 10 5 2 \le e \le 3 \times 10^52≤e≤3×105。0 ≤ n ≤ e − 1 0 \le n \le e - 10≤n≤e−1。2 ≤ k ≤ e 2 \le k \le e2≤k≤e。1 ≤ a i ≤ e − 1 1 \le a_i \le e - 11≤ai≤e−1。1 ≤ s j ≤ e 1 \le s_j \le e1≤sj≤e。1 ≤ k × ( e − n ) ≤ 3 × 10 5 1 \le k\times (e - n) \le 3 \times 10^51≤k×(e−n)≤3×105。上述变量均为整数。所有a i a_iai互不相同。所有s j s_jsj互不相同。评分说明本题共有一组子任务条件限制如下所示。每一组可有一或多组测试数据该组获得的分数 该组满分分数 × min 测试数据 ∈ 该组 评分 ( 测试数据 ) 。 该组获得的分数 该组满分分数\times \min_{测试数据 \in 该组} 评分(测试数据)。该组获得的分数该组满分分数×测试数据∈该组min评分(测试数据)。对一组测试数据考虑问题描述中提到条件的符合与否如果输出的答案不符合输出格式或不符合 1., 2., 或 3. 评分为0 00。如果输出的答案符合 1., 2., 和 3. 但不符合 4. 评分为0.2 0.20.2。如果输出的答案符合 1., 2., 3., 和 4. 但不符合 5. 评分为0.5 0.50.5。如果输出的答案符合 1., 2., 3., 4. 和 5. 评分为1 11。子任务分数额外输入限制1100 100100无额外限制。C实现#includebits/stdc.husingnamespacestd;constintN3e55,inf0x3f3f3f3f;intn,k,e,a[N];boold[N],vis[N];vectorintcnt[N];// 走到i坐标满足要求的走法intpre[N],ans[N],idd;// 从哪里来的signedmain(){cin.tie(0)-sync_with_stdio(0);cinnke;for(inti1;in;i){intx;cinx;d[x]true;}for(inti1;ik;i){cina[i];}sort(a1,ak1,greaterint());cnt[0].resize(k1);vis[0]true;for(inti1;ie;i){if(!d[i]){cnt[i].resize(k1);for(intx1;xk;x){intji-a[x];if(j0!d[j]vis[j]){vis[i]true;vectorinttmpcnt[j];tmp[x];if(cnt[i]tmp){cnt[i]tmp;pre[i]j;}}}}}if(!vis[e]){cout-1;}else{intnowe;while(now0){ans[idd]now;nowpre[now];}coutidd\n;for(intiidd;i0;i--){coutans[i] ;}}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
