@王清楚 n²建边也能过

@王清楚 样例1解释有误。n个任务最短完成时间是22

动态规划二分优化时间复杂度 把arr[]向右偏移为下标从1开始的a[]g[i]为长度为i的最长上升子序列的最小的末尾元素的下标last[i]表示以第i个元素结束的最长上升子序列的上一个元素的下标 const int N = 100010; class Solution { public: /** * retrun the longest increasing subsequence * @param arr int整型vector the array * @return int整型vector */ int g[N], a[N], ...

A. Strange Table 原题链接： A. Strange Table 题意： 对于一个 的矩阵，按行编号指从第一行第一列开始从左往右依次编号，编号为正整数，从 开始递增，当这一行填满时从下一行的第一列继续填，直至填满整个矩阵。按列编号指从第一行第一列开始从上往下依次编号，当这一列填满时从下一列的第一行继续填。 组测试数据，每次给出一个 行 列的矩阵，询问按行编号时为 的单元格，按列编号时为几？ ； ； 考虑行列以及单元格都从 开始编号，按行编号则第 行 第 列的单元格编号为 按列编号则第 行 第 列的单元格编号为 可以先对 然后求出行列，再求...

题目描述 给出一个 个点 条边的无向图，点的编号为 ~ ，起初每个点 属于编号为 的集合共进行 次操作，每次操作给出一个 如果没有点在编号为 的集合中，那么无事发生否则把和编号为 的集合相邻的集合全部并入编号为 的集合最后求每个点所在的集合编号 输入样例 1 4 3 0 1 1 2 2 3 4 0 1 3 0输出样例 0 0 0 0 并查集 链表合并 使用存了尾节点下标的邻接表存图 每次合并集合的时候把要合并进来的那些点的邻接表连到根节点上 遍历过的边要清空一下，否则菊花图biss 时间复杂度 C++ 代码 #include<cstdio> #include...

原题链接： Happy Triangle 题目描述 维护一个可重集合，进行 次操作，操作1：插入一个数 操作2：删除一个数 操作3：给出一个数 ，判断是否能从集合中找到两个数 , 使得 这三个数组成一个三角形 输入样例 8 1 1 3 1 1 1 3 2 3 1 1 2 2 1 3 1输出样例 No No Yes No 线段树 出题人题解：首先，我们在回答询问时只考虑相邻的两个数，因为对于一组数 不妨设 如果能构成三角形的三边，那么我们把 替换成 的前驱也一定是合法的 对于上面说法的解释：对于集合中的一对数 ，如果有 则可以构成三角形三边把 替换成 的前驱 （）...

题目描述 有一个长度为N的序列。一开始，这个序列是1, 2, 3,... n - 1, n的一个排列。对这个序列，可以进行如下的操作：每次选择序列中k个连续的数字，然后用这k个数字中最小的数字替换这k个数字中的每个数字。我们希望进行了若干次操作后，序列中的每个数字都相等。请你找出需要操作的最少次数。 目标是把所有的数都替换成1贪心地想，每次选取包含一个1的长度为k的连续序列，都可以把其他的k - 1个数替换成。总共需要把其他n - 1个数全部替换成1，所以答案为 至于初始状态1的位置是否有影响，我们可以考虑用从左往右用长度为k的线段覆盖整个序列，相邻的两个线段相交的长度为1。我们发现，依次...

题目描述 在一个3×3的网格中，1~8这8个数字和一个“X”恰好不重不漏地分布在这3×3的网格中。 例如： 1 2 3 X 4 6 7 5 8在游戏过程中，可以把“X”与其上、下、左、右四个方向之一的数字交换（如果存在）。 我们的目的是通过交换，使得网格变为如下排列（称为正确排列）： 1 2 3 4 5 6 7 8 X例如，示例中图形就可以通过让“X”先后与右、下、右三个方向的数字交换成功得到正确排列。 交换过程如下： 1 2 3 r 1 2 3 d 1 2 3 r 1 2 3 X 4 6 -> 4 X 6 -> 4 5 6 -&g...