打卡信奥刷题（3622）用C++实现信奥题 P11827 [TOIP2024] 大步小步向前走

P11827 [TOIP2024] 大步小步向前走

题目背景

本题的 Special Judge 由 CuteMurasame 重构，以符合 -std=c++14 标准。

题目描述

五条圣是电门中学的学生，他的梦想是成为职业足球选手。虽然他因为想每天练习足球而不想去上学，但为了不违反国民教育法第二章第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​米处，则他的脚会受伤导致他不能完成他足球员的梦想，这是他一定要避免的。

给定学校坐标、坑洞位置以及五条圣练成的步法长度，五条圣想要你帮他找出最佳的迈步方式，满足下列条件：

1. 避开所有坑洞。
2. 最后恰好停在e ee米处。
3. 最大步法使用的次数越多越好。
4. 若存在多种最大步法次数最多的方式，第二大的步法使用的次数越多越好。
5. 若还有多种方法，以此类推比较第三大、第四大、⋯ \cdots⋯、第k kk大的步法次数。

输入格式

n nnk kke ee
a 1 a_1a1​a 2 a_2a2​a 3 a_3a3​⋯ \cdots⋯a n a_nan​
s 1 s_1s1​s 2 s_2s2​s 3 s_3s3​⋯ \cdots⋯s k s_ksk​

• n , k , e n, k, en,k,e分别代表坑洞数、五条圣步法种类的数量以及学校坐标。
• 第i ii个洞的坐标在a i a_iai​。
• 第j jj种步法长度为s j s_jsj​。

输出格式

m mm
p 1 p_1p1​p 2 p_2p2​p 3 p_3p3​⋯ \cdots⋯p m p_mpm​

• m mm为一正整数，代表最佳的迈步方式总共走几步。
• p i p_ipi​均为正整数，代表第i ii步落脚在p i p_ipi​米处。
• 若答案不唯一，输出任一符合所求的答案均可。

若不存在任何的迈步方式，输出一行− 1 -1−1。

输入输出样例 #1

输入 #1

3 2 8 1 3 4 4 2

输出 #1

3 2 6 8

输入输出样例 #2

输入 #2

3 2 9 3 4 1 4 2

输出 #2

-1

输入输出样例 #3

输入 #3

0 4 61 3 5 23 30

输出 #3

4 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。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=3e5+5,inf=0x3f3f3f3f;intn,k,e,a[N];boold[N],vis[N];vector<int>cnt[N];// 走到i坐标满足要求的走法intpre[N],ans[N],idd;// 从哪里来的signedmain(){cin.tie(0)->sync_with_stdio(0);cin>>n>>k>>e;for(inti=1;i<=n;i++){intx;cin>>x;d[x]=true;}for(inti=1;i<=k;i++){cin>>a[i];}sort(a+1,a+k+1,greater<int>());cnt[0].resize(k+1);vis[0]=true;for(inti=1;i<=e;i++){if(!d[i]){cnt[i].resize(k+1);for(intx=1;x<=k;x++){intj=i-a[x];if(j>=0&&!d[j]&&vis[j]){vis[i]=true;vector<int>tmp=cnt[j];tmp[x]++;if(cnt[i]<tmp){cnt[i]=tmp;pre[i]=j;}}}}}if(!vis[e]){cout<<-1;}else{intnow=e;while(now>0){ans[++idd]=now;now=pre[now];}cout<<idd<<'\n';for(inti=idd;i>0;i--){cout<<ans[i]<<' ';}}return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容