题意：给出一张地图和小A和小B的位置，问两个人是否能在某一个点相遇，如果能相遇，那么需要的最短时间是多少。 思路：首先肯定是要搜索了，首先分析小A，小A的行走方式简单，所以可以对小A BFS一遍，用一个数组记录小A到达这个位置所需要的最短时间，那么如果小B也能走到这个位置时，取所有可以走到公共地方时间的min即可。因此我们只需要在对小B BFS一遍，找出最小的时间就行，由于小B行走的方式比较麻烦，所以需要额外处理一下，如果最后答案不是初始值inf，说明可以相遇，否则不能，具体的见代码。 代码如下： #include<bits/stdc++.h> #define LL long lo...

题意：给出一个无向树，每一个节点代表一个城市，问从给出的城市出发，每一次到达一个城市之后都会将距离他为1的城市访问完，第二天继续访问其它没有访问的城市，问最多可以持续多少天。 思路：简单的树形dp，跟树形dp模板题没有上司的舞会一样，设dp[i][0]代表不把i作为休息点的以i为根的最大天数，dp[i][1]代表把i作为休息点的以i为根的最大天数，那么转移dp[i][0]+=max(dp[儿子][0],dp[儿子][1]),dp[i][1]+=dp[儿子][0],也就是不选择这个点作为休息点那么对于儿子节点没有要求，选择后儿子节点就不能作为休息点了。 代码如下： #include<bit...

题意：给出n头牛的运输时间和每分钟的破坏值（如果该头牛没有被运走的话，每分钟造成的损失就是该破坏值）；问将所有牛运送完造成的最小损失是多少。 解题思路：我们先假设有两头牛i和j，两头牛的运送时间和破坏力为q[i].ti,q[i].val,q[j].ti,q[j].val；那么先运送i花费较小的前提是2 * q[i].ti * q[j].val<2 * q[j].ti * q[i].val -> q[i].ti * q[j].val<q[j].ti * q[i].val。所以我们可以对所有牛按照该表达式进行排序，然后从1到n贪心的运送即可。 代码如下： #include&l...

题意：给出一组数据，让你简化这个数组，使得原数组中任意一个元素都可以被简化后的数组表示，表示的方式为从简化后的数组抽取数组中任意元素任意次累加和等于该元素，求简化后数组的最小长度。 解题思路：这道题类似于牛客的另一道题砝码，不过砝码可以相减，但是思路都差不多。首先如果一个元素能被已经选择的元素表示出来，那么这个元素就不用再取了，所以我们可以建立一个标记数组用来标记某个数是否可以被已经选择的数进行表示（类似于dp优化），因此我们可以对数组从小到大进行排序，每取一个数，就更新一下标记数组，标记的条件是若某个数被标记了，那么这个数加上本轮选取的数也会被标记。初始条件vis[0]=1。 代码如下： #...

题意：给出n个建筑的修复需要的时间和截止时间，建筑必须要在截止时间结束前修复才行，问最优的修复顺序下的最大修复建筑数量是多少。 解题思路：首先第一印象肯定是和贪心脱不了关系了，如果可以修复，我们肯定先修复截止时间早的建筑，后修复截止时间迟的建筑。所以我们首先需要对截止时间进行排序，然后从第一个到最后一个选择性的修复就行。但是我们不能直接以截止时间进行贪心，比如一个建筑截止时间早但是修复时间很大，那么就压缩了其它建筑的修复时间，因此我们需要有一种类似于反悔的策略，比如如果比如当修复到建筑i的时候，如果在此时的条件下不能修复它（也就是当前时间+修复它所需要的时间超过了他的截止时间），但是我们选择修...

题意：给你一个排列和一个数值k，问数组中存在多少以k为中位数且长度为奇数的连续段。 解题思路：首先我们可以想到的是找到k的位置，然后对k左右两边取数的方式都check一遍看是否合法，时间复杂度肯定不允许；所以需要转换一下思路，因为是要求中位数，所以我们并不关心选择的序列每一位的实际大小，只需要找到序列中比k小的和比k大的一样多就行了。所以我们可以把原序列中比k大的变成1，比k小的变成-1，k位置变成0，那么如果序列合法的话，那么该子段和需要为0，所以我们只需要开一个桶来记录k左边的累加的和出现的次数和k右边累加和出现的次数，然后对出现的数进行计算即可。比如左边累加和为2，那么当右边出现和为-2...

图的遍历：[https://ac.nowcoder.com/acm/problem/52275] 解题思路： 首先容易想到是如果是一个奇数环，那么该环上任意一点都可以被经过，因为gcd(2，奇数)==1,所以延申一下与奇数环连接的所有点也可以被经过，因为可以通过环上的的点来调节（可以选择后退一步），所以如果有奇数环答案就是联通块的数量减1； 如果没有联通块，通过奇数环的理解，我们只需要构造一个可以任意到达的环即可，所以这个时候要多加一条边，所以此时答案就是联通块的个数。 连通块的个数可以用Tarjan求也可以用染色法（标记）,因为要求奇数环，所以染色更简单一点。 代码如下： #in...