玩蛋仔派对的可以加我 蛋仔名：#U摆烂小猫 #是英文的# U是大写

一、题目大意 机器人有 vvv 项能源指标，第 jjj 项指标至少要达到 need[j]。 现在有 ggg 个能源模块，第 iii 个模块能够为每一项指标提供一定的增益。每个模块最多只能选择一次。 我们需要找到一组模块，使得： 1. 每一项能源指标的总和都不小于最低需求； 2. 选择的模块数量尽可能少； 3. 如果最少模块数量相同，选择的模块编号序列要字典序最小。 输出时，模块编号按照从小到大的顺序输出。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、观察数据范围 题目中： g≤15g \le 15 g≤15 每个模块只有两种状态： * 不选择； * 选择。 因此，所有选择方案的数量为： 2g2^g 2g 当 g=15g=15g=15 时： 215=327682^{15}=32768 215=32768 只有三万多种方案，可以把每一种方案都检查一遍。 所以这道题可以直接使用 二进制枚举所有子集。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、什么是二进制枚举子集 假设一共有 3 个模块。 我们可以使用一个二进制数表示模块的选择情况： 二进制状态 选择的模块 000 一个都不选 001 选择模块 1 010 选择模块 2 011 选择模块 1、2 100 选择模块 3 101 选择模块 1、3 110 选择模块 2、3 111 选择模块 1、2、3 对于一个整数 mask，如果： 等于 1，就表示选择第 i+1i+1i+1 个模块。 之所以是 i+1i+1i+1，是因为程序中的下标从 0 开始，而题目中的模块编号从 1 开始。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、如何判断一个方案是否合法 枚举出一个方案后，我们计算它在每一项能源指标上的总增益。 假设当前方案选择了若干模块，我们用： 表示这些模块在第 jjj 项指标上提供的总增益。 如果对于所有指标都满足： sum[j]≥need[j]sum[j] \ge need[j] sum[j]≥need[j] 那么当前方案就是一个可行方案。 只要有一项不满足要求，当前方案就不能使用。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、如何选择最优答案 对于每一个可行方案，我们需要按照以下顺序比较。 1. 先比较模块数量 模块数量更少的方案一定更优。 例如： * 方案 A 选择 2 个模块； * 方案 B 选择 3 个模块。 那么无论它们的模块编号是什么，方案 A 都更优。 2. 模块数量相同时比较字典序 例如有两个方案： 比较第一个位置： * 第一个方案是 1； * 第二个方案是 2。 因为 1<21<21<2，所以： 的字典序更小。 再例如： 第一个位置相同，继续比较第二个位置： * 3 小于 4； 所以第一个序列字典序更小。 在 C++ 中，vector<int> 可以直接使用 < 比较，比较规则就是字典序： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 六、完整思路 依次枚举从 0 到 2g−12^g-12g−1 的每一个二进制状态。 对于每个状态： 1. 统计选择了多少个模块； 2. 记录选择的模块编号； 3. 计算每一项能源指标的总增益； 4. 判断是否满足全部最低要求； 5. 如果满足要求，就与当前最优方案比较： * 模块数量更少，则更新答案； * 模块数量相同但编号序列字典序更小，也更新答案。 题目保证至少存在一个可行方案，所以最后一定能够找到答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 七、样例推演 最低需求为： 三个模块分别提供： 只选择一个模块时： * 模块 1 不满足； * 模块 2 的第 3、4 项不满足； * 模块 3 的第 2、4 项不满足。 因此至少需要选择两个模块。 选择模块 1 和模块 3 后，总增益为： 50+900=95050+900=950 50+900=950 50+150=20050+150=200 50+150=200 50+389=43950+389=439 50+389=439 50+399=44950+399=449 50+399=449 即： 所有指标都达到了要求，因此这是一个可行方案。 最终输出：

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 小鸟在树上欢乐地叽叽喳喳 你叫你🐴 你叫你🐴呀 呜呜呜 在这个季节 雨后的落叶 在不停落下 你落你🐴 呜呜呜 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 天那这要是能上榜我把电脑吃了

带权无向图中按位与旅途的最小代价 一、题目要求 给定一个带权无向图。 一趟旅途可以： * 重复经过同一个节点； * 重复经过同一条边； * 绕路之后再回到原来的位置。 一趟旅途的代价，是经过的所有边权的按位与： 对于每个询问 s t，要求从 s 到 t 的所有旅途中，代价最小是多少。 如果 s 和 t 不连通，输出 -1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、你的代码原本想做什么 你的思路是： 1. 从起点 s 开始 DFS； 2. 每走过一条边，就把当前答案和边权进行按位与； 3. 到达终点 t 时，更新最小答案。 也就是： 这个思路的问题在于：题目允许重复经过节点和边，所以可能存在无限多趟旅途。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、原代码存在的问题 1. 没有使用 VIS，会无限递归 这是无向图。 假设存在一条边： 从 0 走到 1 后，DFS 又可以从 1 走回 0： 因此程序会无限递归，最终栈溢出。 虽然你定义了： 但是在 DFS 中并没有使用它。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 不能简单地用 VIS 禁止重复访问 可能会想到这样修改： 但这样也不正确。 因为题目明确允许重复经过节点和边，而且最优旅途可能必须绕路。 例如样例一： 从 0 到 3 的简单路径是： 代价为： 但是我们可以绕路： 代价为： 所以如果禁止重复访问节点，就可能找不到最优答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. 第一次到达终点时不能直接停止 你的代码中： 但第一次到达 t 后，还可以离开 t，经过一些权值更小的边，再回到 t。 例如： 从 s 直接到 t，代价是： 但是可以走： 代价为： 因此到达终点不代表旅途必须立刻结束。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. 每个询问都 DFS，时间复杂度无法接受 数据范围为： 如果每个询问都遍历整张图，时间复杂度大约是： 最坏情况下接近： 一定会超时。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、按位与运算的特点 按位与有一个重要性质： > 参与按位与的数字越多，结果只可能不变或者变小，不可能变大。 例如： 每多经过一条边，代价中的某些二进制位可能从 1 变成 0。 一旦某一位变成了 0，以后不可能重新变成 1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、关键结论 对于同一个连通块中的任意两个节点 s 和 t： > 从 s 到 t 的最小旅途代价，等于这个连通块中所有边权的按位与结果。 假设一个连通块中的所有边权为： 那么这个连通块中任意两个节点之间的答案都是： 如果两个节点不在同一个连通块中，答案就是 -1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 六、为什么答案是整个连通块的边权按位与 可以从二进制的每一位分别考虑。 假设我们正在研究二进制的第 k 位。 情况一：连通块中所有边的第 K 位都是 1 无论选择怎样的旅途，经过的每条边在这一位都是 1。 所以最终按位与结果的第 k 位一定是 1。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 情况二：连通块中至少有一条边的第 K 位是 0 由于整个连通块是连通的，我们可以从 s 出发，绕路经过这条边，然后再走到 t。 一旦经过了这条第 k 位为 0 的边，最终答案的第 k 位就会变成 0。 因此，只要连通块中存在一条边的某一位是 0，我们就能让答案的这一位变成 0。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 所以最终： * 某一位在所有边中都是 1，答案中这一位才是 1； * 某一位只要在某条边中是 0，答案中这一位就可以是 0。 这正是对整个连通块的所有边权进行按位与。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 七、为什么一定可以经过连通块中的所有边 因为题目满足两个重要条件： 1. 图是无向图； 2. 旅途允许重复经过节点和边。 假设我们现在位于某个节点，想去经过连通块中的某条边。 由于连通块内部任意两个节点之间都存在路径，所以我们一定可以： 1. 从当前位置走到这条边的一个端点； 2. 经过这条边； 3. 再继续走向其他边； 4. 最后走到终点 t。 中间即使重复经过其他节点或边也没有关系。 因此，我们能够构造一趟旅途，使它经过连通块中的所有边。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 八、DFS 应该怎样使用 原本你的 DFS 是： > 对每个询问，搜索从 s 到 t 的所有旅途。 这个做法无法实现。 我们把它改成： > 对整张图进行 DFS，找出每个连通块，并计算每个连通块中所有边权的按位与。 需要记录两个信息： 表示节点 i 属于哪个连通块。 表示编号为 id 的连通块中，所有边权的按位与。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 九、DFS 的实现 这里有一个非常重要的细节： 必须放在： 的外面。 也就是不能写成： 因为这样只会计算 DFS 树上的边，而不会计算连通块中形成环的其他边。 例如： DFS 可能只通过两条边访问所有节点，但第三条边同样属于这个连通块，也必须参与按位与。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十、为什么同一条无向边计算两次没有问题 建立无向图时，一条边会存储两次： 因此 DFS 会对同一个权值计算两次： 但按位与满足： 所以： 重复计算不会影响答案，不需要专门判断每条边是否已经处理。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十一、初始值为什么使用 -1 每个连通块开始时，可以令： 在二进制补码中，-1 的所有二进制位都是 1： 所以： 例如： 这样第一次遇到边权时，cost[id] 就会变成这条边的权值。 之后再继续与其他边权： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十二、询问的处理 对于一个询问： 先判断： 不在同一个连通块 说明不存在从 s 到 t 的旅途： 在同一个连通块 答案就是： 每个询问只需要常数时间。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十三、完整代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十四、样例一分析 边为： 节点 0、1、2、3 属于同一个连通块。 这个连通块中所有边权的按位与为： 因此，只要询问的两个节点都在这个连通块中，答案就是 1。 对于询问： 答案为： 节点 4 是孤立点，所以询问： 两个节点不连通，答案为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十五、样例二分析 所有边权为： 进行按位与： 写成二进制： 所以： 最终结果为： 因此询问 1 2 的答案是 0。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十六、复杂度分析 预处理 DFS 会访问每个节点一次，每条无向边会被处理两次： 回答询问 每个询问只需要判断两个节点的连通块编号： 一共有 q 个询问： 总时间复杂度 空间复杂度 邻接表以及辅助数组的空间复杂度为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十七、总结 这道题最容易产生的错误是： > 尝试搜索从起点到终点的所有路径。 但题目求的并不是普通路径，而是可以重复经过节点和边的旅途，因此旅途数量可能是无限的。 真正的关键是： > 在同一个连通块中，我们可以通过绕路经过任意边。 按位与参与的边越多，结果越小，所以同一连通块中任意两个节点之间的最小代价，都是： 因此只需要： 1. 用 DFS 划分连通块； 2. 用 DFS 计算每个连通块所有边权的按位与； 3. 每个询问根据连通块编号直接回答。

团队的主题是有关三角洲行动的，只要玩这个游戏的都可以找我私信，我审核一下，审核过关，我会说一点点另外要求，然后转让。 已经有人先答出来了，队伍已转。

顶一下

加入者必回关 管理员先到先得 谢谢

熟人分组题解 题目大意 一共有 N 名同学，编号为 1 ~ N。 题目给出 M 条关系，每条关系为： 表示同学 x 和同学 y 属于同一个熟人圈。 熟人关系具有传递性。 例如： * 1 和 2 属于同一个熟人圈； * 2 和 3 属于同一个熟人圈； 那么 1、2、3 都属于同一个熟人圈。 现在要把所有同学分成若干组，并且要求： > 同一个熟人圈中的任意两名同学不能被分到同一组。 求至少需要多少组。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、如何理解这道题 我们可以把每一名同学看成一个点。 如果两名同学属于同一个熟人圈，就在他们之间连接一条边。 例如关系为： 可以画成： 因此可以得到两个熟人圈： 在图论中，一个熟人圈就是一个连通块。 所谓连通块，可以简单理解为： > 从其中任意一个点出发，沿着边可以到达这个集合中的所有点。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 二、为什么答案是最大的熟人圈人数 假设有两个熟人圈： 第一个熟人圈有 3 个人。 因为同一个熟人圈中的任意两个人都不能放在同一组，所以 1、2、5 必须分别放进不同的组。 因此至少需要 3 组： 第二个熟人圈只有 2 个人，他们可以放入前面已经建立的组中： 这是合法的，因为 1 和 3 不属于同一个熟人圈，2 和 4 也不属于同一个熟人圈。 所以： > 不同熟人圈可以重复使用相同的组。 因此，只需要找到人数最多的熟人圈。 如果最大的熟人圈有 k 个人，那么答案就是 k。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 三、解题思路 我们使用邻接表保存同学之间的关系。 其中： 保存所有与同学 x 有直接关系的同学。 因为同学关系是双向的，所以输入一条关系 x y 时，需要添加两条边： 接下来枚举每一名同学。 如果某名同学还没有被访问过，就从这名同学开始进行一次深度优先搜索。 一次完整的深搜可以找到一个完整的熟人圈。 在深搜过程中，每访问到一名新的同学，就让： 深搜结束后，sum 就是当前熟人圈的人数。 最后用： 记录最大的熟人圈人数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 四、深搜函数怎么写 深搜函数如下： 下面逐句解释。 1. 判断当前同学是否已经访问过 如果同学 f 已经被访问过，就直接返回。 这样可以防止重复搜索，也可以防止在无向图中无限递归。 例如存在一条边： 从 1 搜索到 2 后，2 又能搜索回 1。 如果没有 vis 数组，就会变成： 程序会一直递归下去。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 标记当前同学已经访问 表示同学 f 已经被找到，以后不需要再次搜索。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. 统计当前熟人圈的人数 每第一次访问一名同学，就把当前熟人圈的人数加一。 这里的 sum++ 一定要放在访问节点的位置，而不能放在遍历边的位置。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. 继续搜索与当前同学有关系的人 a[f] 中保存了所有与同学 f 有直接关系的人。 我们继续对这些人进行深搜，就可以找到整个熟人圈。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 五、你的原代码有什么问题 你的深搜部分原来是： 问题出在： 你把它放在了遍历邻接表的循环里面。 这意味着： > 每遍历一条边，sum 就加一。 但是我们需要统计的是熟人圈中的人数，而不是边数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 六、为什么统计边数是错误的 假设只有两名同学： 因为这是无向图，所以建立邻接表后会保存： 也就是： 虽然这个熟人圈中只有 2 个人，但是邻接表中有两条记录。 而且题目允许重复输入关系。 例如： 实际上仍然只有两名同学属于这个熟人圈。 但是邻接表中会保存很多条重复边。 如果按照边数进行统计，答案就会错误。 因此应该写成： 也就是： > 每访问到一名新的同学时，才让 sum 加一。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 七、完整代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 八、样例分析 输入： 建立的关系为： 程序首先从同学 1 开始深搜。 搜索顺序可能是： 所以第一个熟人圈的人数为： 然后继续枚举。 同学 2 已经访问过，同学 3 没有访问过，所以从同学 3 开始深搜： 第二个熟人圈人数为： 因此： 最终输出： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 九、为什么每次深搜前要把 SUM 清零 sum 表示当前熟人圈的人数。 假设第一个熟人圈有 3 个人，搜索结束后： 接下来搜索第二个熟人圈之前，必须执行： 否则第二个熟人圈的人数会继续加在第一个熟人圈后面。 正确写法是： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十、没有关系的同学怎么处理 假设某名同学没有任何关系。 例如一共有三名同学，但是只有一条关系： 那么同学 3 自己也构成一个熟人圈。 程序枚举到同学 3 时，会执行： 进入 dfs(3) 后会执行： 所以同学 3 所在的熟人圈大小为 1。 因此孤立的同学也可以被正确统计。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十一、重复关系会不会影响答案 题目中可能出现重复关系，例如： 这些关系都会被保存到邻接表中。 但是深搜中有： 所以同一名同学只会在第一次访问时执行： 之后即使通过重复边再次搜索到他，也会直接返回。 因此重复关系不会影响最终答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十二、正确性说明 每次从一个没有访问过的同学开始深搜，深搜会沿着关系边找到所有与他属于同一个熟人圈的同学。 每找到一名新的同学，就让 sum 加一，因此深搜结束后，sum 就是当前熟人圈的人数。 程序对每一个熟人圈都进行一次深搜，并使用 ans 保存最大的熟人圈人数。 同一个熟人圈中有多少人，就至少需要多少个不同的组。 不同熟人圈之间可以重复使用这些组。 所以最少组数等于最大熟人圈的人数。 因此程序输出的 ans 就是正确答案。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十三、复杂度分析 每名同学最多被深搜访问一次。 每条关系在无向图中会被检查两次。 因此时间复杂度为： 邻接表和访问数组占用的空间复杂度为： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 十四、总结 这道题的对应关系为： 最关键的一点是： 应该在第一次访问一个节点时执行，而不是每遍历一条边时执行。 因此答案就是：

来聊天吧

如果你独自刷题缺少交流、想要找到同好讨论算法题目，欢迎加入我们！ ✅ 团内氛围轻松，新手友好，大佬乐于答疑 ✅ 日常交流题库题目、分享解题思路 ✅ 相约参加 ACGO 天梯、欢乐赛，组队训练 📌入团要求：喜爱编程算法，积极交流，不潜水摆烂。 申请入口：

🔥团队招人｜寻找一起刷题的伙伴！ 无论入门新手还是正在备战信息学竞赛的同学都欢迎加入。 团内可以交流题目、讨论思路，组队参加欢乐赛，互相督促刷题。 没有严苛门槛，热爱编程、愿意交流即可。 申请直接点击链接：【粘贴你的团队链接】 申请备注 ACGO 昵称，看到会尽快通过！ https://www.acgo.cn/application/2073379344479748096

ACGO 算法团队招募成员！ 欢迎所有刷题爱好者，日常交流 C++、探讨错题，组队打天梯与欢乐赛。 有意向直接打开下方链接申请入团： https://www.acgo.cn/application/2073379344479748096

🔥团队招人｜寻找一起刷题的伙伴！ 无论入门新手还是正在备战信息学竞赛的同学都欢迎加入。 团内可以交流题目、讨论思路，组队参加欢乐赛，互相督促刷题。 没有严苛门槛，热爱编程、愿意交流即可。 申请直接点击链接：【粘贴你的团队链接】 申请备注 ACGO 昵称，看到会尽快通过！

我发现了一个游戏，网址是www.narrow.one，想要自取[链接描述]

神之梯队_SZTD职位有生命之神，太阳神等，有很多职位都没有人，我代宁来为团队找人，只要为团队招10个以上就能参加竞选，职位有大地之神，月亮之神，题库神，题单神，作业神，竞赛神，文件神，成员神，参加竞选如果超过8人将在团队主页发出投票，要投票的私我（只能投一个） 团队链接：https://www.acgo.cn/application/2036351988307800064 截止8月10日。

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 加团 真的没有其他人知道 Attack Zone D 的意义了吗？ #Warthunder #战雷 #Kards

大家好，我是神之梯队_SZTD团队的成员兼管理员，这个团队是我的好兄弟༺དༀ༒ཌ--神--ད༒ༀཌ༻所创建，发这个帖子是

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个最小值 1.2 题目背景、允许、禁止与限制 背景： 有 nnn 种怪兽，初始时有怪兽 111，求消灭这个怪兽最少需要多少体力 允许： 对于每个怪物 iii，有两种攻击方式 * 物理攻击，需要耗费 sis_isi 的体力，尽管当前怪物会被消灭，但是会分裂出 rir_iri 个新的怪兽 * 魔法攻击，需要耗费 kik_iki 的体力，不会有任何分裂，相当于彻底消灭 限制： 1.3 题目数据范围与猜测 1≤n≤2×105,1≤∑ri≤106⟶O(∑r log n)1 \le n \le 2\times10^5,1 \le \sum r_i \le 10^6 \longrightarrow O(\sum r~log~n)1≤n≤2×105,1≤∑ri ≤106⟶O(∑r log n) 1.4 一句话概括题意 初始有一个怪兽，求通过不同攻击方式（消耗体力可能不同）将所有怪物击杀的最小体力耗费 2 题目破题推导 2.1 排除一些错误 1. 不断模拟 怪兽的数量可以理解为是无限的，模拟就永无止境 2. 构造有偏差的图 将每个点设置一条到 1 的路径权值为 k [i]，再设置连接到第 r [i] 个节点的权值为 s [i]，然后求 1~1 的最短路 这样也是不行的，因为比如分裂出来r_i个怪物，但是最短路只会走其中一条，是违背这题要求的 2.2 问题等价转化（抽象） 思考：任何一只怪兽，他的诞生时机和诞生方式都不影响彻底清除它的最小花费体力 因此，抽象出核心概念：f(i)=f(i)=f(i)= 彻底清除第 iii 种怪物所需要的最小体力 那答案本质上就是 f(1)f(1)f(1)，因为开局有的怪兽就是 111 2.3 分情况讨论 每种怪兽 iii，都只有两种可能 * 法术攻击：代价为 kik_iki ，无新怪兽产生且原怪兽死亡 * 普通攻击：代价为 sis_isi ，原怪兽死亡且产生一些新怪兽。总消耗可以理解成：si+∑f(所有新的怪物)s_i+\sum f(所有新的怪物)si +∑f(所有新的怪物) f(i)即min(ki,si+∑f(...))f(i) 即 min(k_i,s_i+\sum f(...))f(i)即min(ki ,si +∑f(...)) 3 模型匹配 > 格式为："关键词：...... ⟶\longrightarrow⟶ ......\huge{......}......" 这题到这里大家可能觉得是普通 dp\huge{dp}dp 但是，因为假设攻击怪物 aaa 会生出怪物 bbb 且能更新最佳方案，那么 f(a)f(a)f(a) 会随着 f(b)f(b)f(b) 的变化而变化，并且f(b)f(b)f(b) 也会随着 f(a)f(a)f(a) 的变化而变化 普通dp要求依赖构成DAG，这题是双向依赖关系，不能用朴素dp 因为我们每遇到一个新点，都有可能对上个节点及下个节点造成影响，因此这种不断松弛的操作，和最短路算法\huge{最短路算法}最短路算法的想法一样。 但是，由于这题没有固定起点（因为所有点都会对其他点造成影响），因此起点不固定，考虑把所有起点都纳入最短路算法实现中 4 最终代码（禁止抄袭，仅用于参考）

#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; // ====================== 数据结构定义 ====================== // 邻接表的边结构体：只保留基础成员，无构造函数 struct { int to; // 边的终点 int w; // 边的权值 }; // 邻接表：g<Edge>raph[u]存储u的所有邻边（vector实现） vector graph[200010]; // sum[u]：根节点(1号)到u的路径异或和 int sum[200010]; // 01字典树结构 struct TrieNode { int ch[2]; } trie[200010 * 32]; int tot = 0; // 字典树节点计数器 // ====================== 函数定义 ====================== // DFS预处理：计算每个节点到根的异或和（替换auto为下标遍历） void dfs(int u, int fa) { // 常规下标遍历：i从0到graph[u]的元素个数-1 for (int i = 0; i < graph[u].size(); ++i) { // 取第i个邻边（替代auto& edge） Edge edge = graph[u][i]; int v = edge.to; // 邻边终点 int w = edge.w; // 边权 if (v == fa) continue; // 跳过父节点 sum[v] = sum[u] ^ w; // 更新根到v的异或和 dfs(v, u); // 递归遍历子节点 } } // 01字典树插入 //trie[x].ch[0] 代表当前节点 x 下一位是 0 的路径通向哪个节点； //trie[x].ch[1] 代表下一位是 1 的路径。 void build(int val, int x) { // 从二进制的最高位(230)开始，逐位向左移动直到最后一位(20) for (int i = (1 << 30); i; i >>= 1) { bool c = val & i; // 取出 val 的当前二进制位（是0还是1） } // 01字典树查询 //在二进制异或运算中，0 ^ 1 = 1，1 ^ 0 = 1。 //只有当前位两个数不同，异或结果才是 1。 //为了找到最大异或结果，我们永远优先让更高位的异或结果变成 1。 int query(int val, int x) { int ans = 0; // 同样从最高位(2^30)开始遍历到最低位 for (int i = (1 << 30); i; i >>= 1) { bool c = val & i; // 取出 val 的当前二进制位 } // ====================== 主函数 ====================== int main() { //加快cin cout 的运行速度 //写完之后不可使用printf 和 scanf ios::sync_with_stdio(false); cin.tie(nullptr); }

原题链接 1 题目 1.1 题目所需求出内容 对于本题，最终要求：一个最大值 1.2 题目背景、允许、禁止与限制 背景： 有 nnn 个字符串 规定两个字符串 AAA 和 BBB 的最长公共后缀长度为 LCS(A,B)LCS(A,B)LCS(A,B) 规定两个字符串 AAA 和 BBB 当 LCS(A,B)≥LCS(A,B) \geLCS(A,B)≥ 两字符串较长长度 −1-1−1，则称 AAA 和 BBB 是押韵的 允许： 求最长押韵子序列（只需要保证相邻两项押韵即可） 限制： 1.3 题目数据范围与猜测 1≤n≤5×105⟶O(n)1 \le n \le 5\times10^5 \longrightarrow O(n)1≤n≤5×105⟶O(n) 1.4 一句话概括题意 有一些字符串，求最长押韵子序列 2 题目破题推导 2.1 规律分析 首先，押韵只有可能有两种情况 * 两字符串长度相等，首位不相等 * 两字符串长度相差 111，较短字符串是较长字符串前缀 2.2 正向思维转逆向思维 因为这题要求后缀，但后缀操作起来比较麻烦，因此考虑转成前缀操作 可以理解成： 押韵变成前缀之后只有可能有两种情况 * 两字符串长度相等，末尾不相等 * 两字符串长度相差 111，较短字符串是较长字符串后缀 2.3 题意转化 （现在必须结合着字典树来说） 当我们倒着插入进字典树后，押韵的字符串有两种情况：相邻两个末尾是父子关系或者是亲兄弟关系 因此相当于在字典树上选若干个单词终点，相邻两个选出单词必须是父子/亲兄弟关系，求最多单词数量 2.4 继续找规律 因为我们不仅选出的字符串序列可能是这样： 还可以往另外一段延伸（也就是加入了波峰和波谷） 2.5 计算方案 那波谷前面的那一部分有多少呢？ 就是 uuu 子树中最大的子序列长度外加子树内的所有单词结尾数量 那这整个有多少呢？ 首先因为可以往两端扩展，因此相当于： * uuu 子树中最大的两个子序列长度 * 除了这两个子树以外的单词结尾子树数量 * 再加（本身是否为单词结尾），就算这一项不是单词结尾，也可以作为另外两个是单词结尾的孩子节点的过渡 3 模型匹配 > 格式为："关键词：...... ⟶\longrightarrow⟶ ......\huge{......}......" 关键词：字典树 ⟶\longrightarrow⟶ 字典树\huge{字典树}字典树 关键词：树上问题，动态求取最大值 ⟶\longrightarrow⟶ 树形dp\huge{树形dp}树形dp 4 最终代码（禁止抄袭，仅用于参考）