题目 有一个长为 的排列 ，与 对 。每对 表示可以将 的值与 的值互换。 对 的使用顺序与次数不限。求任意次操作之后能得到的字典序最小的排列是什么？ 输入第三个参数为初始排列 。第四个参数为 对 。 返回字典序最小的排列。 解题思路 可以将每一个下标看作图中的一个节点，把互换的关系看作是连接两个节点的边，那么由于互换操作具有传递性，即如果下标 a 和 b 的值互换，下标 b 和 c 的值互换，则下标 a 和 c 的值也可以互换。也就是说，所有互换的下标属于同一个连通分量。因此，可以使用并查集来维护这种连通分量的关系。 首先遍历 对 ，构造并查集。可以互换值的两个下标属于同...

题目 在一颗有 个结点且以 1 为根节点树上，起初每个结点的初始权值为 0。现在有 次操作，每次操作选择将以 为根节点的子树上的所有结点权值增加 。求 次操作后从 1 到 每个结点的权值。 输入第一个参数为 n，第二个参数为边 的集合，其中 表示结点 与结点 之间有一条边，第三个参数为 ，第四个参数为 次询问的 的集合， 返回从 1 到 每个结点的权值。 解题思路 使用 DFS 算法 记录与某个点相邻的所有点。 记录从 1 到 n 每个结点的权值。 一开始记录的是每个节点增加的权值，而不考虑节点的子树。 函数计算最终每个节点的权值。从根节点 1 开始，深度优先遍历...

题目 给定一颗节点编号为 1~n 的，且以 1 为根的树，给出 n 组询问，每次询问给定一个数对 (x,y) ，求 对于这 n 组询问的答案，不需要依次输出 n 个数，只需要输出它们的和对 998244353 的取模即可。树的信息以及询问不会直接给出，输入数据只包含随机种子，具体生成方式请仔细阅读备注内容。 备注： 输入数据包含5个整数，n,seed1,seed2,seed3,x. 树的信息生成伪代码如下 //////////////////////1///////////////////// 定义边集数组u[],v[] //u[i],v[i]表示第i条边的两个端点 定义变量see...

题目 有 n 件带水的衣服，干燥衣服有两种方式。一、是用烘***，可以每分钟烤干衣服的 k 滴水。二、是自然烘干，每分钟衣服会自然烘干 1 滴水。烘***比较小，每次只能放进一件衣服。注意，使用烘***的时候，其他衣服仍然可以保持自然烘干状态，求可以把衣服全烘干的最少时间。 解题思路 使用二分法： 先确定上下限：所求时间最少是 1 分钟；最多时间是数组 中的最大值，此时所有衣服自然烘干。 取上下限的中间值，调用 函数判断所有衣服是否能在 时间内烘干，根据判断结果更新时间上下限，并更新满足题意的最少时间。 函数 的作用是判断序列 中的所有衣服是否能在 分钟内完全烘干。判断方法是：...

题目 所有的长度为 n 的数中，各个位上的数字之和为 m 的这些数的和是多少呢。给定 n 和 m，求这些数的和。 解题思路 使用暴力法：长度为 的数的范围是 。遍历该范围的数值，求出每个数的各个位上的数字之和 是否与 相等，若相等，将这个数 累计加入最终结果 。 C++代码 class Solution { public: /** * 返回这样的数之和 * @param n int整型 数的长度 * @param m int整型 各个为之和 * @return long长整型 */ long long sum(int n...

题目 在包含 n+1 个数的序列 a 中找出重复的数。序列 a 中包含从 1 到 n 的整数，且只有一个数有重复值。要求时间复杂度为 O(n)，额外空间复杂度为 O(1)。 解题思路 解法一 先排序，再找重复值排序可以直接使用 sort() 函数，其时间复杂度为 ，接着遍历数组，如果相邻两个数相等，返回重复值。因此，时间复杂度为 ，空间复杂度为 ，不符合题意。 解法二 使用集合存储已遍历过的数值遍历数组，使用 set 数据结构来保存已遍历过的值，如果当前的值已存在 set 中，表示该值重复。因此，时间复杂度为 ，空间复杂度为 ，不符合题意。 解法三 位运算（使用这个解法）求出 1 到 n...

题目 有一个长度为 序列 （序列下标从 1 开始），每次可以从任意位置 花费 的代价来把 删除。注意，删除后 后面的数会依次向前补上（下标 -1 ) 。求把整个序列删完的最小代价。 解题思路 当 是正数时，在下标 1 的位置删除代价最小，即 。当 是负数时，在其当前所在下标的位置删除代价最小，即 ，因为下标不能更大了。 C++代码 #include<cstdio> using namespace std; int main(){ int n; scanf("%d", &n); long long ans = 0; int a;...

题目 给出一个数列 ，求出一个数列 。其中 表示数列 中 右边第一个比 大的数的下标（从 1 开始计数），没有找到这一个下标 就为 0。 解题思路 在从右向左遍历数组 A 时维护一个栈。这个栈存储数列 A 的下标。如果栈非空，且栈顶的元素（下标）所代表的值小于等于当前的值，这表示栈顶下标 sta.top() 比当前的下标大，且下标值 A[sta.top()] 小于等于当前值 A[i]，就可以弹出栈顶元素，压入当前的下标。当栈为空时，表示数列 A 的右边没有元素大于当前元素，当前所求的值是 0。 C++代码 #include<cstdio> #include<vect...

题目 给定字符串 s，求一个最长的字符串 t，t 满足以下条件：它是 s 的前缀；它是 s 的后缀；除前缀和后缀外，它还在 s 中出现过至少一次。 解题思路 暴力求解：先判断前缀和后缀，再判断中间是否存在该字符串。 C++代码 #include<iostream> using namespace std; int main(){ string s; cin >> s; int n = s.size(); int i = (n-1)/3; for(; i>=0; --i){ int a = i; ...

题目 求最少要拾取多少个子弹到背包中，使得背包里的子弹个数恰好是 x 的倍数且是 y 的倍数。 解题思路 求 x 和 y 的最小公倍数。先求 x 和 y 的最大公因数 k = __gcd(x,y)，则最小公倍数为 x * y / k。 C++代码 #include<iostream> #include<algorithm> using namespace std; typedef unsigned long long ULL; int main(){ int t; cin >> t; ULL x, y; for(int i...

题目 要把 这 个数字首尾连接组成一个环，使得相邻元素互质的对数尽可能多。请输出最大对数。 解题思路 不考虑互质，一共有 n 对相邻的数。 由更相减损术知，数对 (x-1, x) 的最大公因数与 (1, x-1) 的最大公因数相同，即为 1，互质。所以，可以将 n 个数字按从小到大的顺序排列并连接，然后将 1 和 n 连接，组成一个环，每对相邻的数都互质。 C++代码 #include<iostream> using namespace std; int main(){ int n; cin >> n; cout << n &l...

题目 帕秋莉处于地图的左下角，出口在地图右上角，她只能够向上或者向右行走。现在给出森林的地图，保证可以到达出口，请问有多少种不同的方案。答案对2333取模。0 - 空地1 - 树（无法通过）保证出发点和终点都是空地。 解题思路 使用动态规划思想。地图左下角的坐标为 (m-1,0)，右上角的坐标为 (0,n-1)。dp[i][j] 表示从左下角到达坐标 (i,j) 的方案数目，dp[m-1][0] = 1。状态转移方程为如果坐标 (i,j) 是树，dp[i][j] = 0；如果坐标 (i,j) 是空地，dp[i][j] = dp[i+1][j] + dp[i][j-1]。最终 dp[0]...

题目 A 点有一个过河卒，需要走到目标 B 点。卒行走规则：可以向下、或者向右。同时在棋盘上的 C 点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。卒不能通过对方马的控制点。棋盘用坐标表示，A 点 (0,0)、B 点 (n,m)（n<21，m<21），C 点 (x,y)。约定：C 点不与 A 点或 B 点重合。现在要求计算出卒从 A 点能够到达 B 点的路径的条数。 解题思路 马跳日。计算出对方马的控制点。 运用动态规划思想：dp[i][j] 表示从点 (0,0) 到达点 (i,j) 时路径的条数。则状态转移方程为：如果 (i,j) 是对方马的控制点，那么 ...

题目 打印数字三角形，从 1 开始输出，第 i 行输出 i 个数，每个数字按 4 个位置输出。 解题思路 注意最后一行不要打印换行符。 C++代码 #include<cstdio> using namespace std; int main(){ int n; scanf("%d", &n); int k = 1; for(int i=1; i<=n; ++i){ for(int j=1; j<=i; ++j){ printf("%4d", k); ++k; ...