P1058 单舟见京杭官方题解

Gioush OJ · 单舟见京杭 · 2026/08/18 00:00

【题意分析】

用 $(x,a)$ 与 $(y,b)$ 表示两处重复景观。一次选择记为 $C$ ，其中 $C_i\in\{0,1\}$ 。
本题中称 $C$ 同时选中重复景观，当且仅当 $C_x=a$ 且 $C_y=b$ 。后文不再使用含义容易混淆的“命中”。
$W$ 是重复景观被重复计算的一份美观度，因此 $W>0$ 。
因为所有美观度均为正数，所以 $\operatorname{Travel}(C)<B(C)$ 当且仅当 $C$ 同时选中两处重复景观。
这给出一个只依赖返回值的判定函数，之后每次试探都只需判断这个不等式。

【部分分：测试点 111】

当 $n\leq 7$ 时，可以枚举一位旅客在每段水道选择的方向。
比较 Travel 的返回值与自行计算的 $B(C)$ ，即可判断当前选择是否同时选中两处重复景观。
枚举全部 $2^n$ 种选择即可确定答案。

【部分分：测试点 222】

特殊性质 A 保证两处重复景观位于同一侧。
先安排一位旅客全部向左看，再安排一位旅客全部向右看。其中恰有一种选择会同时选中两处重复景观。
固定这份选择。接下来翻转一批位置，便能判断这批位置是否与两处重复景观相交。

【部分分：测试点 333】

若两处景观方向不同，则在能够区分 $x,y$ 的二进制位上，原选择与其补集必有一个同时满足 $C_x=a,C_y=b$ 。
对每个二进制位，令第 $i$ 段水道的方向等于编号 $i$ 的这一位，再询问一次其补集。
对任意两个不同编号，总有一个二进制位能够区分它们。配合原选择与补集，总能得到一份同时选中两处重复景观的选择。
至多使用 $2+2\lceil\log_2 n\rceil$ 位旅客就能得到这样一份选择。

【部分分：测试点 444】

设当前选择 $C$ 已经同时选中两处重复景观。把候选位置的一半记为 $S$ ，同时翻转所有 $C_i\ (i\in S)$ 。
翻转后的选择不再同时选中两处重复景观，当且仅当 $S\cap\{x,y\}\neq\varnothing$ 。此时保留 $S$ ，否则保留候选集合的另一半。
不断折半即可找到第一处重复景观。将它从候选集合中删除后重复同样的过程，即可找到第二处。
每次试探后恢复 $C$ 。最后用 Answer 给出两处位置以及 $C_x,C_y$ 。
找到第一处后，从候选集合中删去它。此时每次翻转集合都不含第一处，于是同一个判定会精确告诉我们集合中是否含第二处。

【正解】

先用全左、全右、各二进制位及其补集找到一份同时选中两处重复景观的选择。
再用两次折半定位分别找到两个位置。每次试探后都恢复选择，已经得到的信息始终有效。
总调用次数不超过

2+2\lceil\log_2 n\rceil+2\lceil\log_2 n\rceil,

在 $n\leq 10^5$ 时不超过 $70$ ，可以取得满分。

【参考代码】

1#include "canal.h"2#include <vector>3using namespace std;4 5void Init(int c,int T){return;}6 7static long long Base(const vector<int> &Choice,const vector<int> &w,const vector<int> &v){8    long long Ret=0;9    for(int i=1;i<(int)Choice.size();i++) Ret+=Choice[i]?v[i]:w[i];10    return Ret;11}12 13static bool Hit(vector<int> &Choice,const vector<int> &w,const vector<int> &v){14    return Travel(Choice)<Base(Choice,w,v);15}16 17void Locate(int c,int n,vector<int> w,vector<int> v){18    vector<int> Choice(n+1,0);19    bool Found=Hit(Choice,w,v);20    if(!Found){21        for(int i=1;i<=n;i++) Choice[i]=1;22        Found=Hit(Choice,w,v);23    }24    for(int Bit=0;!Found&&(1<<Bit)<=n;Bit++){25        for(int i=1;i<=n;i++) Choice[i]=(i>>Bit)&1;26        Found=Hit(Choice,w,v);27        if(!Found){28            for(int i=1;i<=n;i++) Choice[i]^=1;29            Found=Hit(Choice,w,v);30        }31    }32    vector<int> Candidate;33    for(int i=1;i<=n;i++) Candidate.push_back(i);34    while(Candidate.size()>1){35        int Mid=Candidate.size()/2;36        for(int i=0;i<Mid;i++) Choice[Candidate[i]]^=1;37        bool Has=!Hit(Choice,w,v);38        for(int i=0;i<Mid;i++) Choice[Candidate[i]]^=1;39        if(Has) Candidate.erase(Candidate.begin()+Mid,Candidate.end());40        else Candidate.erase(Candidate.begin(),Candidate.begin()+Mid);41    }42    int x=Candidate[0],a=Choice[x];43    Candidate.clear();44    for(int i=1;i<=n;i++) if(i!=x) Candidate.push_back(i);45    while(Candidate.size()>1){46        int Mid=Candidate.size()/2;47        for(int i=0;i<Mid;i++) Choice[Candidate[i]]^=1;48        bool Has=!Hit(Choice,w,v);49        for(int i=0;i<Mid;i++) Choice[Candidate[i]]^=1;50        if(Has) Candidate.erase(Candidate.begin()+Mid,Candidate.end());51        else Candidate.erase(Candidate.begin(),Candidate.begin()+Mid);52    }53    int y=Candidate[0],b=Choice[y];54    Answer(x,a,y,b);55}