题解：P17274 [eJOI 2026] Elevator

lailai0916 · 2026-08-31 09:20:29 · 题解

题意简述

电梯从第 0 层开始，只在按钮已被按下的楼层停靠。

每名被访问的住户知道当前按钮集合和自己的值。住户只能按下更高楼层的按钮。到达屋顶后，需要仅根据最终按钮集合恢复尽量多的住户值。

解题思路

设最终按下的按钮集合为 S，并令：

把 0 加入 S 后，将其中元素从小到大记为：

这些位置就是住户被访问的顺序。电梯停在 f=s_j 时，记当前按钮集合中不超过 f 的元素个数为 c。由 s_j 的定义可知 c=j。住户可以用 upper_bound 求出 c，也就得到了自己的访问序号。整个过程不依赖任何共享变量。

后面的构造把若干连续按钮分成编码块。访问序号决定当前使用哪个编码块。码字中每个 1 都会产生一次后续停靠。限制码字的最小重量，便能保证后续编码者一定被访问。

子任务一

在第 i 层执行如下操作：

• 若 v_i=1，按下 i+1；
• 若 v_i=0，按下 i+2。

超出第 60 层的按钮不按。若 v_i=0，题目保证 v_{i+1}=1。因此，跳过第 i+1 层不会丢失未知信息。

对所有 0\le i<60，按钮 i+1 当且仅当 v_i=1 时被按下。又因为 v_{60}=1 已知，所以可以恢复全部 61 个值。

子任务二

先按下按钮 1。对 0\le i<19，用按钮 3i+2 至 3i+4 编码 v_{s_{2i}} 和 v_{s_{2i+1}}。

设这两个值依次为 x,y。第一次访问该组时，只按下一个由 x 决定的按钮。若 x=0，按下该组的第三个按钮；若 x=1，按下第一个按钮。这样既能让第二名住户辨认 x，也能保证第二名住户会被访问。

第二次访问该组时，根据 x,y 补全下表中的码字。各位按按钮编号从低到高排列：

四个码字互不相同，并且都至少包含两个 1。前 19 组与按钮 1 一共至少按下 39 个按钮，所以一定能访问 s_1 至 s_{39}。

第 i 组开始编码前，已有编码只使用不超过 3i+1 的按钮。因此，两名编码者均位于不超过第 3i+1 层，新按下的按钮都严格高于当前楼层。

前 38 个值由分组编码恢复。此时 s_{38},s_{39}\le58。最后令按钮 59 和 60 分别表示这两个位置的值。这样共恢复 40 个值。

子任务三

对 0\le j<30，用按钮 2j+1,2j+2 编码 v_{s_j}。三种取值采用如下码字：

三个码字互不相同，并且都至少包含一个 1。所以，每编码一个值都会产生下一次停靠，可以连续处理前 30 名住户。

处理 s_j 前，旧编码只使用前 2j 个按钮，故 s_j\le2j。新编码使用按钮 2j+1,2j+2，按键操作一定合法。

子任务四

先按下按钮 1。对 0\le i<8，用按钮 5i+2 至 5i+6 编码 v_{s_{2i}} 和 v_{s_{2i+1}}。

设这两个值依次为 x,y。第一次访问该组时，按下一个由 x 决定的按钮。x=0,1,2,3 时，分别按下组内的第五、第四、第三、第二个按钮。第二名住户可以据此唯一确定 x，再按照下表补全码字：

表中 16 个码字互不相同，并且都至少包含三个 1。八组编码与按钮 1 一共至少按下 25 个按钮。因此，一定能访问 s_1 至 s_{25}。

第 i 组开始编码前，已有分组编码只使用不超过 5i+1 的按钮。因此，该组的五个按钮都严格高于两名编码者所在楼层。

前 16 个值由分组编码恢复。此时 s_{16} 至 s_{24} 均不超过 41。对 16\le j<25，再用按钮 42+2(j-16) 和 43+2(j-16) 保存 v_{s_j} 的二进制表示，共恢复 25 个值。

正确性证明

先证明所有按键操作均合法。各编码区间互不相交，且每个新区间都位于对应编码者上方。辅助函数 put 还会排除已经按下的按钮。因此，返回的按钮编号均严格大于当前楼层，且不会重复。

子任务二和四的每个完整码字分别至少包含两个和三个 1。子任务三的每个码字至少包含一个 1。所以，开始处理一组后，码字产生的停靠次数足以访问该组后续的编码者。结合每个构造开头额外按下的按钮，可以依次处理目标数量的住户。

对于子任务一，按钮 i+1 当且仅当 v_i=1 时被按下。若 v_i=0，则题目已保证被跳过的 v_{i+1}=1。故可由最终按钮集合恢复 v_0 至 v_{59}，再补上已知的 v_{60}=1。

对于子任务二，每组的四种 (x,y) 与四个码字一一对应。第一次按下的指定按钮包含在对应码字中，第二名住户可以确定 x 并补全码字。屋顶查表即可恢复每组的两个值，最后两个值则由按钮 59,60 直接恢复。

对于子任务三，三种取值对应三个不同码字。屋顶读取每组的两个按钮后，可以唯一恢复该组表示的值。

对于子任务四，每组的十六种 (x,y) 与表中的十六个码字一一对应。第一次按下的指定按钮包含在该行的全部码字中，故第二名住户总能补全目标码字。屋顶查表可恢复前十六个值，其余九个值由各自的两位二进制表示恢复。

综上，四个计分子任务能恢复的值数依次为 61,40,30,25。这些值均正确，故达到满分要求。

参考代码

#include <bits/stdc++.h>
#include "elevator.h"
using namespace std;

const int key2[2]={2,0};
const int code2[2][2]={{5,6},{3,7}};
const int code3[3]={3,1,2};
const int key4[4]={4,3,2,1};
const int code4[4][4]={{19,21,22,23},{11,13,14,25},{7,15,28,29},{26,27,30,31}};
vector<int> put(int s,int n,int m,const vector<int> &p)
{
    vector<int> q;
    for(int i=0;i<n;i++)
    {
        if((m>>i&1)&&!binary_search(p.begin(),p.end(),s+i))q.push_back(s+i);
    }
    return q;
}
vector<int> press1(int f,int v)
{
    int x=f+2-v;
    if(x<=60)return {x};
    return {};
}
vector<int> press2(int f,int v,const vector<int> &p)
{
    if(!f)return {1,2+key2[v]};
    int j=upper_bound(p.begin(),p.end(),f)-p.begin();
    if(j>=40)return {};
    if(j>=38)
    {
        if(v)return {j+21};
        return {};
    }
    int s=j/2*3+2;
    if(j%2==0)return {s+key2[v]};
    int x=binary_search(p.begin(),p.end(),s+key2[0])?0:1;
    return put(s,3,code2[x][v],p);
}
vector<int> press3(int f,int v,const vector<int> &p)
{
    int j=upper_bound(p.begin(),p.end(),f)-p.begin();
    if(j>=30)return {};
    int s=j*2+1;
    return put(s,2,code3[v],p);
}
vector<int> press4(int f,int v,const vector<int> &p)
{
    if(!f)return {1,2+key4[v]};
    int j=upper_bound(p.begin(),p.end(),f)-p.begin();
    if(j>=25)return {};
    if(j>=16)
    {
        int s=(j-16)*2+42;
        return put(s,2,v,p);
    }
    int s=j/2*5+2;
    if(j%2==0)return {s+key4[v]};
    int x=0;
    while(!binary_search(p.begin(),p.end(),s+key4[x]))x++;
    return put(s,5,code4[x][v],p);
}
vector<int> answer1(const vector<int> &p)
{
    vector<int> q(61);
    for(auto x:p)q[x-1]=1;
    q[60]=1;
    return q;
}
vector<int> answer2(const vector<int> &p)
{
    vector<int> a={0};
    vector<int> b(61);
    vector<int> q(61,-1);
    for(auto x:p)
    {
        a.push_back(x);
        b[x]=1;
    }
    for(int i=0;i<19;i++)
    {
        int s=i*3+2,m=0,x=0,y=0;
        for(int j=0;j<3;j++)m|=b[s+j]<<j;
        for(int j=0;j<2;j++)
        {
            for(int k=0;k<2;k++)
            {
                if(code2[j][k]==m)x=j,y=k;
            }
        }
        q[a[i*2]]=x;
        q[a[i*2+1]]=y;
    }
    q[a[38]]=b[59];
    q[a[39]]=b[60];
    return q;
}
vector<int> answer3(const vector<int> &p)
{
    vector<int> a={0};
    vector<int> b(61);
    vector<int> q(61,-1);
    for(auto x:p)
    {
        a.push_back(x);
        b[x]=1;
    }
    for(int i=0;i<30;i++)
    {
        int m=b[i*2+1]+b[i*2+2]*2;
        q[a[i]]=find(code3,code3+3,m)-code3;
    }
    return q;
}
vector<int> answer4(const vector<int> &p)
{
    vector<int> a={0};
    vector<int> b(61);
    vector<int> q(61,-1);
    for(auto x:p)
    {
        a.push_back(x);
        b[x]=1;
    }
    for(int i=0;i<8;i++)
    {
        int s=i*5+2,m=0,x=0,y=0;
        for(int j=0;j<5;j++)m|=b[s+j]<<j;
        for(int j=0;j<4;j++)
        {
            for(int k=0;k<4;k++)
            {
                if(code4[j][k]==m)x=j,y=k;
            }
        }
        q[a[i*2]]=x;
        q[a[i*2+1]]=y;
    }
    for(int i=16;i<25;i++)
    {
        int s=(i-16)*2+42;
        q[a[i]]=b[s]+b[s+1]*2;
    }
    return q;
}
vector<int> press_buttons(int subtask,int,int f,int v,vector<int> p)
{
    if(subtask==1)return press1(f,v);
    if(subtask==2)return press2(f,v,p);
    if(subtask==3)return press3(f,v,p);
    if(subtask==4)return press4(f,v,p);
    return {};
}
vector<int> answer(int subtask,int,vector<int> p)
{
    if(subtask==1)return answer1(p);
    if(subtask==2)return answer2(p);
    if(subtask==3)return answer3(p);
    if(subtask==4)return answer4(p);
    return vector<int>(61,-1);
}