时津风的资源收集时间限制1秒 空间限制256M知识点广度优先搜索(BFS)网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述时津风曾沉迷于页游Kancolle。在游戏中有一项日常任务需要玩家使用油、弹药、钢材、铝这4 44种资源来开发装备。现给定目标资源量a , b , c , d a,b,c,da,b,c,d时津风进入开发界面时4 44种资源均为10 1010单位。她可以对单一资源执行以下任意一种操作资源总量始终保持在区间[ 10 , 300 ] [10,300][10,300]将该资源± 1 ±1±1将该资源± 10 ±10±10将该资源± 100 ±100±100直接将该资源设为上限300 300300直接将该资源设为下限10 1010。在保证所有资源始终处于合法范围的前提下求使四种资源同时恰好达到( a , b , c , d ) (a,b,c,d)(a,b,c,d)所需的最少操作次数。输入描述第一行输入整数T ( 1 ≦ T ≦ 10 5 ) T(1≦T≦10^5)T(1≦T≦105)—— 测试组数。接下来T TT行每行输入4 44个整数a , b , c , d ( 10 ≦ a , b , c , d ≦ 300 ) a,b,c,d (10≦a,b,c,d≦300)a,b,c,d(10≦a,b,c,d≦300)。输出描述对每组数据输出一个整数表示最少操作次数。示例1输入2 10 100 200 300 10 10 10 10输出5 0说明样例1第一组测试数据可能的操作是初始[ 10 , 10 , 10 , 10 ] [10,10,10,10][10,10,10,10]将弹药增加100 100100变成[ 10 , 110 , 10 , 10 ] [10,110,10,10][10,110,10,10]将弹药减少10 1010变成[ 10 , 100 , 10 , 10 ] [10,100,10,10][10,100,10,10]将钢材增加到上限变成[ 10 , 100 , 300 , 10 ] [10,100,300,10][10,100,300,10]将钢材减少100 100100变成[ 10 , 100 , 200 , 10 ] [10,100,200,10][10,100,200,10]将铝增加到上限变成[ 10 , 100 , 200 , 300 ] [10,100,200,300][10,100,200,300]可以发现无法使用5 55次以下的操作来达到开发所需的资源量所以答案为5 55。第二组测试数据开发所需的资源量就为资源初始值所以不需要进行任何操作。解题思路本题核心是资源独立性分解 单状态BFS预处理将四维最短路问题降为一维通过预处理实现海量查询的秒级响应。问题降维资源独立性质每次操作仅针对单一资源四种资源的调整互不影响因此总最少操作次数等于每种资源从初始值10调整到目标值的最少操作次数之和。问题简化为求从10出发通过允许的操作到达数值x的最少步数其中x ∈ [10, 300]。单资源最短路建模将每个资源数值视为图的节点每个合法操作对应一条权值为1的边数值 ±1、±10、±100若结果在 [10, 300] 范围内则构成合法转移任意数值可直接跳转至10下限和300上限各对应一步操作。由于所有操作步数均为1使用BFS广度优先搜索可以天然求出从起点10到所有节点的最短路径。预处理 批量查询数值范围仅 10~300共291个节点一次BFS即可预处理出所有目标值的最少步数数组dis。对于 T 组查询只需将四个目标值对应的dis值相加即可 O(1) 得到每组答案完美适配T ≤ 10^5的大数据量查询。算法总时间复杂度预处理为常数级查询为 O(T)整体效率极高。总结核心逻辑利用资源独立性拆分四维问题通过BFS预处理单资源最少操作步数查询时直接累加四个维度的结果。关键操作单资源最短路建模、BFS层序遍历求最短步数、预处理数组加速批量查询。效率保障数值范围极小预处理常数开销查询O(1)轻松应对十万级测试用例。代码简要说明预处理函数pre初始化距离数组dis为 -1标记未访问起点10的距离设为0并入队。定义6种数值加减的偏移量遍历每个出队节点时尝试所有加减操作结果合法且未访问则更新距离并入队。处理直接设置上限300的操作若300未被访问则更新其距离为当前步数1并入队BFS保证首次到达即为最短路径。直接设置下限10的操作因起点就是10最优路径不会用到回退操作故不影响最终结果。主函数逻辑提前调用pre完成全局预处理仅执行一次。读取测试用例数 T逐组读取四个目标资源值累加对应距离后直接输出。关闭同步流加速输入输出适配十万级查询的IO效率要求。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll dis[305];queuellq;ll dx[]{1,-1,10,-10,100,-100};voidpre(){memset(dis,-1,sizeof(dis));dis[10]0;q.push(10);while(!q.empty()){ll uq.front();q.pop();for(ll i0;i6;i){ll vudx[i];if(v10v300dis[v]-1){dis[v]dis[u]1;q.push(v);}}if(dis[10]-1){dis[10]dis[u]1;q.push(10);}if(dis[300]-1){dis[300]dis[u]1;q.push(300);}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);pre();ll T;cinT;while(T--){ll a,b,c,d;cinabcd;coutdis[a]dis[b]dis[c]dis[d]\n;}return0;}
时津风的资源收集【牛客tracker 每日一题】
时津风的资源收集时间限制1秒 空间限制256M知识点广度优先搜索(BFS)网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述时津风曾沉迷于页游Kancolle。在游戏中有一项日常任务需要玩家使用油、弹药、钢材、铝这4 44种资源来开发装备。现给定目标资源量a , b , c , d a,b,c,da,b,c,d时津风进入开发界面时4 44种资源均为10 1010单位。她可以对单一资源执行以下任意一种操作资源总量始终保持在区间[ 10 , 300 ] [10,300][10,300]将该资源± 1 ±1±1将该资源± 10 ±10±10将该资源± 100 ±100±100直接将该资源设为上限300 300300直接将该资源设为下限10 1010。在保证所有资源始终处于合法范围的前提下求使四种资源同时恰好达到( a , b , c , d ) (a,b,c,d)(a,b,c,d)所需的最少操作次数。输入描述第一行输入整数T ( 1 ≦ T ≦ 10 5 ) T(1≦T≦10^5)T(1≦T≦105)—— 测试组数。接下来T TT行每行输入4 44个整数a , b , c , d ( 10 ≦ a , b , c , d ≦ 300 ) a,b,c,d (10≦a,b,c,d≦300)a,b,c,d(10≦a,b,c,d≦300)。输出描述对每组数据输出一个整数表示最少操作次数。示例1输入2 10 100 200 300 10 10 10 10输出5 0说明样例1第一组测试数据可能的操作是初始[ 10 , 10 , 10 , 10 ] [10,10,10,10][10,10,10,10]将弹药增加100 100100变成[ 10 , 110 , 10 , 10 ] [10,110,10,10][10,110,10,10]将弹药减少10 1010变成[ 10 , 100 , 10 , 10 ] [10,100,10,10][10,100,10,10]将钢材增加到上限变成[ 10 , 100 , 300 , 10 ] [10,100,300,10][10,100,300,10]将钢材减少100 100100变成[ 10 , 100 , 200 , 10 ] [10,100,200,10][10,100,200,10]将铝增加到上限变成[ 10 , 100 , 200 , 300 ] [10,100,200,300][10,100,200,300]可以发现无法使用5 55次以下的操作来达到开发所需的资源量所以答案为5 55。第二组测试数据开发所需的资源量就为资源初始值所以不需要进行任何操作。解题思路本题核心是资源独立性分解 单状态BFS预处理将四维最短路问题降为一维通过预处理实现海量查询的秒级响应。问题降维资源独立性质每次操作仅针对单一资源四种资源的调整互不影响因此总最少操作次数等于每种资源从初始值10调整到目标值的最少操作次数之和。问题简化为求从10出发通过允许的操作到达数值x的最少步数其中x ∈ [10, 300]。单资源最短路建模将每个资源数值视为图的节点每个合法操作对应一条权值为1的边数值 ±1、±10、±100若结果在 [10, 300] 范围内则构成合法转移任意数值可直接跳转至10下限和300上限各对应一步操作。由于所有操作步数均为1使用BFS广度优先搜索可以天然求出从起点10到所有节点的最短路径。预处理 批量查询数值范围仅 10~300共291个节点一次BFS即可预处理出所有目标值的最少步数数组dis。对于 T 组查询只需将四个目标值对应的dis值相加即可 O(1) 得到每组答案完美适配T ≤ 10^5的大数据量查询。算法总时间复杂度预处理为常数级查询为 O(T)整体效率极高。总结核心逻辑利用资源独立性拆分四维问题通过BFS预处理单资源最少操作步数查询时直接累加四个维度的结果。关键操作单资源最短路建模、BFS层序遍历求最短步数、预处理数组加速批量查询。效率保障数值范围极小预处理常数开销查询O(1)轻松应对十万级测试用例。代码简要说明预处理函数pre初始化距离数组dis为 -1标记未访问起点10的距离设为0并入队。定义6种数值加减的偏移量遍历每个出队节点时尝试所有加减操作结果合法且未访问则更新距离并入队。处理直接设置上限300的操作若300未被访问则更新其距离为当前步数1并入队BFS保证首次到达即为最短路径。直接设置下限10的操作因起点就是10最优路径不会用到回退操作故不影响最终结果。主函数逻辑提前调用pre完成全局预处理仅执行一次。读取测试用例数 T逐组读取四个目标资源值累加对应距离后直接输出。关闭同步流加速输入输出适配十万级查询的IO效率要求。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll dis[305];queuellq;ll dx[]{1,-1,10,-10,100,-100};voidpre(){memset(dis,-1,sizeof(dis));dis[10]0;q.push(10);while(!q.empty()){ll uq.front();q.pop();for(ll i0;i6;i){ll vudx[i];if(v10v300dis[v]-1){dis[v]dis[u]1;q.push(v);}}if(dis[10]-1){dis[10]dis[u]1;q.push(10);}if(dis[300]-1){dis[300]dis[u]1;q.push(300);}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);pre();ll T;cinT;while(T--){ll a,b,c,d;cinabcd;coutdis[a]dis[b]dis[c]dis[d]\n;}return0;}
（支持资料、图片参考_相关定制）_可以扫码)
