冒 泡 排 序

字节跳动9.6后端笔试ak笔记 没有选择题，爷青回！ 不过居然不给用ide，我又一次没带草稿纸，只能用编辑器的注释来记一下了。。 下面的代码仅供参考，因为不是现场写的代码，不一定能ac，因为不给用ide代码存不下来。 1 题意 一个人跳楼梯，可以跳一格，可以跳两格，但不能连续跳两格，问跳到层有多少种方式。（） Solution 表示跳到第层表示上一次跳跃是不是两格，显然有。 那么答案即。 首先需要令，然后从递推上去即可。 然后要特判，我也不知道为什么的时候答案是，题目也没说，很迷。 Code #include <bits/stdc++.h> using namespace std;...

选择题完全看不懂，完全乱选，没什么好记的。 实际比赛中是写在一个class里面的，本质是一样的。 1 题意：给定一个序列，要把这个序列变成一个数，每次将相邻两个数合成一个数，贡献为新合成的数，求最小贡献。 区间dp 。 int solve(const int *gz, int gzLen) { const int n = gzLen; vector<int> a(n + 1), b(n + 1); for (int i = 1; i <= n; i++) { a[i] = gz[i - 1]; b[i] = b[i - 1] + a[i]; }...

题目链接 A - 攀登 简单模拟所有情况即可。 标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299107 B - Badeline 模拟即可。 假设第秒时Madeline的位置时，用一个数组存第秒时Madeline的位置，这样Badeline的位置都可以知道。 标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44299111 C - Celestial Resort 表示求这一堆数的最大公倍数，表示这一堆数的最小...

摸鱼

题解 要求复杂度在内，很显然这样的复杂度应该是用状压dp。 令表示已经放了的状态下，最后放入的是第个字符串的最小答案。（这里的下标从开始） 那么就有这样的状态转移： 首先如果状态中只有一个字符串，那么。（表示第个字符串的长度） 那么对于状态中不止有一个字符串的，且有的有： 这里表示的意思是当前是要放第个字符串，然后上一个字符串是第个字符串，然后转移。其中的意思是前面先放第字符串后面放字符串所能缩短的最多字符大小。 状压dp部分的复杂度就已经到达了，如果再在里面再求tmp数组的话复杂度会很高。 很显然需要预处理tmp数组。如何去预处理呢？ 最暴力的方式就是直接枚举前缀后缀进行比较，但是这样的话...

Solution 非常显然的离线+优先队列求解，先处理更加“宽容”的人（希望士兵团不超过的人数更多的人），那么那些不那么“宽容”的被分配到团中时，比这个人更加“宽容”的人也能分配到团中。 限定一个值，让都堆在一起后，选择前大的求和即是此时所能安排的最大值。这是经典的topK问题。 的取值有个，所以直接枚举的复杂度是的。但如果从大的开始安排的话，会发现枚举的元素是在原来的基础上增加而已。那么问题就变成了动态的topK问题了。复杂度变为了。 他给的输入不是按照递减的顺序给的，那么排一下序就可以了。 Code #include<bits/stdc++.h> using namespace...

Solution 这公式看起来挺吓人，但转换一下就发现好像并没有那么难。 会发现后面式子中的是原来数组中的下标，与新构成的子序列并没有任何关联。 那么显然用高中导数题中经常使用的分离参数法解决： 两边取对数（任意底均可）： 即 令，那么就是找b数组的严格上升子序列的个数了。 那么就是个经典动态规划了，表示以第个位置为结尾的严格上升子序列的个数，那么有： 时间复杂度 Code #include<bits/stdc++.h> using namespace std; const int N = 100 + 10, MOD = 1e9 + 7; int dp[N]; double a[N...

打ACM的蒟蒻一个。 笔试 题目的全貌没有，把记得到的题意写一下。 T1 题意 给一个矩阵，有一个人站在某一个点上，一开始他有一把长度为的大刀，每个格点有个点权，且。如果大刀能砍到这个格点（欧几里得距离小于大刀长度），大刀长度加。问最后大刀的最长长度。 Solution 如果某个时刻大刀能砍到某个位置，大刀加长后还是能砍得到那个位置。 那我们不妨先砍离站的位置最近的格点，如果近的格点都砍不到那远的格点就更加砍不到。非常简单的贪心思想。 Code #include<bits/stdc++.h> using namespace std; typedef long long ll; vo...

Solution 看完题目就能想到这个题也许可以二分答案。 但是需要知道这个题目的答案可不可以满足单调性。即对于所有满足条件，则也满足条件。 很显然这是满足单调性的，如果满足条件，即 那么对于而言，显然有 那么这个题就可以二分答案了。 还有一个点是答案可能会到。于是二分范围直接是区间即可。 本题check的时候可以加一个小小的剪枝。 不过这个题有一点没有说清楚，即使答案不存在的时候要输出，所以当的时候也不满足输出即可。 时间复杂度 Code #include<bits/stdc++.h> using namespace std; int a[200005], n, k; bool ...

A - Jelly Solution 非常裸的三维bfs。 仅仅只是从经典的四连通变成了六连通然后跑个最短路就可以了。 一开始想用dfs搞，然后发现可能走的不是最短路。于是乖乖地去写bfs去了。 时间复杂度 Code #include<bits/stdc++.h> using namespace std; char a[101][101][101]; int dis[101][101][101]; const int fx[6][3] = {{-1, 0, 0}, {1, 0, 0}, {0, -1, 0}, {0, 1, 0}, {0, 0, -1}, {0, 0, 1}}; i...

Description 一棵个点的有根树，号点为根，相邻的两个节点之间的距离为。树上每个节点i对应一个值。每个点都有一个颜色，初始的时候所有点都是白色的。你需要通过一系列操作使得最终每个点变成黑色。每次操作需要选择一个节点，必须是白色的，然后到根的链上（包括节点与根）所有与节点距离小于的点都会变黑，已经是黑的点保持为黑。问最少使用几次操作能把整棵树变黑。 Solution 很显然叶子节点是一定要选择的，但是被这些叶子节点能覆盖的点有时也是需要选择的，比如下面的这种情况。 虽然每次选择的节点一定要是白色节点，如果先选择了叶子节点就不能选择被这个节点覆盖的节点。但是可以先选择深度小的节点，...