P10445 「MYOI-R3」签到题目背景Updated on 2024/5/12新增两组 hack 数据位于 Subtask #5 的 #31 和 #32。Updated on 2024/5/13由于争议过大目前难度已降绿。暂时不考虑再次变动本题难度。题目描述这一场比赛为了选手顺利完成签到题设置有nnn个签到处你和它们都在一条笔直的公路上我们不妨把这条笔直的公路看作成一条数轴你现在在数轴原点的位置上即坐标为000第iii个签到处在坐标为xix_ixi​的地方你在每个时间单位内最多可以移动111个单位长度。你需要去尽量多的签到处签到然后在mmm个时间单位内回到数轴原点。签到的时间可以忽略不计而且你可能在同一地点瞬间完成位于同一位置的多个不同签到处的签到。出题人为了让各位选手们更方便、更顺利地签到还在场上第ppp个签到处放置了签到礼物。如果选手在这里签过到那么回到原点的时间限制可以被推迟到m5m5m5个单位时间。注你可以在第mmm个时刻后才获得礼物但你必须在m5m5m5个单位时间前回到原点。求选手最多可以在多少个不同的签到处签到并在此前提下最小化签过到的签到处的编号的集合的字典序如果有多解输出任意一个方案即可。注集合的字典序等价于把集合内的元素从小到大排序之后的序列的字典序。输入格式第一行三个整数n,m,pn,m,pn,m,p。第二行一共nnn个整数第iii个整数表示xix_ixi​。输出格式第一行一个整数ansansans表示你最多能去签到的签到处的数量。第二行输出ansansans个正整数表示依次要去签到的签到处的编号。本题采用 Special Judge如果有多解输出任意一个即可。输入输出样例 #1输入 #13 11 3 1 -3 4输出 #13 1 2 3输入输出样例 #2输入 #25 15 3 -5 -10 0 5 10输出 #23 2 1 3说明/提示样例1\small\text{1}1解释很显然可以去所有的签到处签到输出一个耗时不超过161616的行动方案即可。样例2\small\text{2}2解释要去333个签到处签到一共有333种不同的选择方案111222333、111333444、333444555显然第一种选择最优选择以下四种行动方案111222333、222111333、333111222、333222111皆可。数据规模与约定本题采用捆绑测试。本题采用「Special Judge」。Subtask\textbf{Subtask}SubtaskSpecial conditions\textbf{Special conditions}Special conditionsPoints\textbf{Points}Points000是样例000111n≤15n\leq 15n≤15101010222n≤300n\leq 300n≤300151515333n≤7×103n\leq 7\times 10^3n≤7×103202020444n≤105n\leq 10^5n≤105252525555无303030请注意大量数据的输入输出对程序效率的影响。保证本题的时间限制足够长。对于100%100\%100%的数据1≤p≤n≤1061\leq p\leq n\leq 10^61≤p≤n≤1060≤m≤10180\leq m\leq 10^{18}0≤m≤1018−1018≤xi≤1018-10^{18}\leq x_i\leq 10^{18}−1018≤xi​≤1018。C实现#includebits/stdc.husingnamespacestd;constlonglongN1e65;structsign_in{longlongx,id;}a[N];longlongn,m,p,now[N],len,cnt,ans[N];boolcmp(sign_in x1,sign_in x2){returnx1.xx2.x;}intmain(){cinnmp;for(longlongi1;in;i){cina[i].x;a[i].idi;//存下编号}sort(a1,an1,cmp);//按照位置排序for(longlongi1;in;i)now[a[i].id]i;//存下他现在在哪里longlongj1;//右端点初值pnow[p];//更新 p 为当前编号即排完序后的for(longlongi1;in;i){//枚举左端点longlongex0;if(ip){//如果有可能去到有奖励的签到处if(a[p].x0abs(a[i].x)*2m5)ex5;//i 离原点更远if(a[i].x0a[p].x0(a[p].x-a[i].x)*2m5)ex5;//i 和 p 分布在原点两侧if(a[i].x0a[p].x*2m5)ex5;//p 离原点更远}if(ex0abs(a[i].x)*2m)continue;//如果去不到有奖励的又走都走不到下一个if(ip1)ji;//如果后面再没有有奖励的了更新 j否则会没有单调性jmax(j,i);//怕出现不合法区间while(jn){//双指针if(a[j].x0)j;//如果 i 更远且 i 是去的到的直接更新elseif(a[i].x0a[j].x0(a[j].x-a[i].x)*2mex)j;//i 和 j 分别在原点两侧且去得了更新elseif(a[i].x0a[j].x*2mex)j;//j 离原点更远并且过得去更新elsebreak;//没法更新了退出}if(j-ilen)ans[cnt]i;//如果是一种可能的方案记下左端点if(j-ilen){//如果更优cnt0;//先清空lenj-i;//存下更优答案ans[cnt]i;//把这个左端点放进去}}coutlenendl;//先输出个数longlongl1,rcnt;//接着来求方案for(longlongi1;in;i){if(now[i]ans[l]||now[i]ans[r]len-1)continue;//根本不包含他下一个while(lrans[l]len-1now[i])l;//如果 l 不合法一直往右移while(lrans[r]now[i])r--;//如果 r 不合法一直往左移}for(longlongians[l];i-ans[l]1len;i)couta[i].id ;//最后输出即可return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容