分层图最短路 链接：https://ac.nowcoder.com/acm/problem/236176 来源：牛客网 做法：直接去连边的话因为数据范围过大，所以会出现tle的现象，也有段错误的现象不知道是为什么，所以对于层与层之间的边，我们建立一个平台，同层的点到这个平台的距离为0，层与层之间的距离为c，那注意不能建立一个双向的平台，这样的话会出现一些不存在的边，所以要建立一个向上的路径和向下的路径分别为i+n和i+2n，之后就是特殊边正常连，然后跑dij即可，spfa可能为卡，但如果数据弱的话也是能过的。 //本题代码 #include<bits/stdc++.h> #defi...

链接：https://ac.nowcoder.com/acm/problem/236173 来源：牛客网 有一片群岛，总共有30001个岛屿，编号从0到30000，其中有 n 个宝藏在这些岛屿中。Kitayuta是一位宝藏猎人，他初始在0号岛屿上。为了获得宝藏，他按照如下规则经过这些岛屿：  ​ 他第一步从 0 号岛屿跨越 d 个岛屿到达 d 号岛屿。 ​ 接下来每一步，他只能前往编号更大的岛屿。并且，假设他前一步跨越了 x 个岛屿，那么他下一步只能跨越 y 个岛屿，其中 y∈{x−1,x,x+1} 且 y>=1 。如果下一步没有可以到达的岛屿，Kitayuta就会停止寻找宝藏。  假设...

货船 链接：https://ac.nowcoder.com/acm/problem/236172 来源：牛客网 有 n个货物，需要装入货船，第 i 个货物的重量是 wi 。货船的最大载重量是 A ，请问在不超过货船最大载重量的前提下，一次最多能运送多少重量的货物。 做法：一眼是01背包，但是无论是物品数量还是重量上限都超过了复杂度和空间复杂度，所以选择去优化背包，01背包其实就是选和不选的选择，非常适合用01字符串去表示，正好可以用stl中的bitset去解决，对于两个状态的字符串，如果这个物品不选，两个状态字符串是相同的，选择这个物品的话，就是多加了a【i】这么多的重量。对于字符串来说就是每...

链接：https://ac.nowcoder.com/acm/problem/235953 来源：牛客网 给你一个数组 a ，包含 n 个整数，你需要在数组 a 中选出不相交的 m 个连续子段，每个子段的长度至少为 1 。 定义每一个子段的贡献为子段内数字的和，你需要求出这 mmm 个子段的贡献之和的最大值是多少。 做法 对于选择一个数，我们可以接到当前第j个字段的尾巴，或者另外开一个字段，那么状态就在f【i-1】【j】+a【i】，f【k】【j-1】中产生，其中k表示以第k个位置为前第一个子段，那么当前选择的数为第j个子段，那么直接去找k的话就是n^ 2的复杂度，所以我们要维护一个数组去优化复...

链接：https://ac.nowcoder.com/acm/contest/84527/C 来源：牛客网 做法 暴力解法就是对于x的每一个位置去遍历最小和最大长度，那么复杂度肯定爆炸，我们先考虑一下最小长度和最大长度的关系，对于一个数来说，如果拓展的最小长度的最小值都小于x，那么最大也只能更小，所以只需要去看最小长度即可，那么就排除了最大长度的影响，那么就需要去优化循环向左向右的过程，我们定义两个数组l，r，l代表的含义为，第i个位置最多向左延展 l【i】个单位能保证i这个位置的元素最小，r数组同理，那么只需要用一个栈去模拟这个过程就能在on的复杂度内完成预处理，因为如果前面一个值小于后面的...

链接：https://ac.nowcoder.com/acm/problem/13230 来源：牛客网 输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。 我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。 需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可 做法 区间dp题，学到的一个点就是如果范围小就考虑开多维去存储，所以dp的思维就是两个串的左右端点，那么就有四种情况，当a串左右相等时，我们看一下缩小一点的a串是否是回...

孙悟空救师傅 链接：https://ac.nowcoder.com/acm/problem/235903 来源：牛客网 师傅又被妖怪抓走了。师傅被困的宫殿可以看作一个 n×nn\times nn×n 的由字符构成的矩阵，每一个字符表示一个房间。字符'K'表示孙悟空的起始位置，'T'表示师傅被困的位置，'S'表示有蛇的房间，'.'表示空房间，'#'表示无法进入的房间。矩阵中包含且仅包含一个'K'和一个'T'。 每分钟，孙悟空都可以上下左右移动一格，如果遇到蛇，打倒蛇需要额外花费一分钟，保证地图上最多有五个有蛇的房间。此外孙悟空还需要集齐所有种类的钥匙才能救出师傅。钥匙的种类以 1,2,...,m...

草药大师 链接：https://ac.nowcoder.com/acm/problem/235951 来源：牛客网 做法1 因为最大容量有1e9，我们需要剪掉一些情况，对于每次物品我们只能拿一次，那么，其实也是从尾开始跑，只不过我们把从最大容量改成最大能放进的容量，如果总容量减去这一个物品的容量比原先的塞进去的容量大，说明可以拿当前这一个物品，那么就去把这一个物品塞进背包就行。 //本题代码 #include<bits/stdc++.h> #define endl "\n" #define int long long //dont forget to check long long...

多重背包 链接：https://ac.nowcoder.com/acm/problem/235950 来源：牛客网 做法：适用于物品数量不是无限但又不止一个的背包问题，一开始想到的是将n个相同重量的物品当作n个不同的物品，但完全背包的复杂度已经汗流浃背，所以我们需要把这个重复的n进行优化，我们尽量去把2的幂作为一组进行打包，剩下的再作为一组打包，这样我们就能用我们构造的数去凑出任何一个1到n之间的数（拆位），那么之后就是经典01背包，这里用嵌套pair去存储（懒。 //本题代码 #include<bits/stdc++.h> #define endl "\n" #define ll...

合唱队形 链接：https://ac.nowcoder.com/acm/problem/16664 来源：牛客网 N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK， 则他们的身高满足T1<...Ti+1>…>TK(1<=i<=K)。 你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 做法 要构造一个先递增后递减的序列，那么我们假设最优点为i，i其实就是最长上升子序列的结尾...

最长上升子序列 朴素dp （O(n^2)) //本题代码 #include<bits/stdc++.h> #define endl "\n" #define ll long long //dont forget to check long long //别写重变量名 //记得判越界 //别死磕 //处理字符串删掉关流 ll f[1000010]; void slove() { int n; std::cin>>n; std::vector<int> a(n+1); for(int i=1;i<=n;i++) std::cin>>a[i]; ...

传球游戏 链接：https://ac.nowcoder.com/acm/problem/16619 来源：牛客网 上体育课的时候，小蛮的老师经常带着同学们一起做游戏。这次，老师带着同学们一起做传球游戏。 游戏规则是这样的：n个同学站成一个圆圈，其中的一个同学手里拿着一个球，当老师吹哨子时开始传球，每个同学可以把球传给自己左右的两个同学中的一个（左右任意），当老师再次吹哨子时，传球停止，此时，拿着球没传出去的那个同学就是败者，要给大家表演一个节目。 聪明的小蛮提出一个有趣的问题：有多少种不同的传球方法可以使得从小蛮手里开始传的球，传了m次以后，又回到小蛮手里。两种传球的方法被视作不同的方法，当且...

链接：https://ac.nowcoder.com/acm/problem/15665 来源：牛客网 小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。 小明只能向上下左右相邻的格子移动，每移动一次花费1秒。 有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下...