简单666

题解

/ 注册

全部文章 / 题解（共41篇）

题解 | #完全平方数的尾巴#

题意：给你一个数，判断这个数是不是某个平方数对取模的结果解法一（扩展欧几里得）我们记这个平方数为由可得显然这是一个不定方程，于是我们可以用扩展欧几里得算法求解具体的，我们可以解出的解于是原方程的一个解为：我们...

C++ 数学

2021-09-13

1 561

题解 | #序列取反问题#

题意：给你一个长度为的序列，第个数字代表了一段连续的区间，其中这些区间满足要么完全覆盖，要么不相交，现在每次等概率地随机选择一个点，并且将区间全部打上标记，问期望多少次能将整个序列都打上标记（答案对998244353取模）？解法一（问题转化+暴力求解） ...

C++ 数学

2021-09-12

0 652

题解 | #牛牛摇骰子#

题意：给你一个无限长的数轴，刚开始你在位置处，你每次可以向左或者向右移动个单位，现在有次询问，第次询问给你一个数字，问从起点位置到所在位置最少需要多少步？解法一（最短路，不可AC）显然我们可以根据题意构建一张以数轴上的数字为点，边权为的无向图，边表示数字变化成数字的一次操作 ...

C++ 数学最短路

2021-09-10

0 595

题解 | #数列求值#

题意：定义数列，，，求的值解法一（暴力递推，不可AC）一个显然的做法就是直接循环一遍递推过去求的值代码： class Solution { public: const int ...

2021-09-09

0 570

题解 | #排队#

题意：有个人，第个人办理事务需要时间，刚开始（时间点为）有个空闲窗口，现在按照第个人的顺序办理事务，当某个时刻发现有空闲窗口后，第个人会到那个空闲窗口办理事务现在设第个人办理事务的截止时间为，求数组的逆序对个数解法一（优先队列+暴力枚举求逆序对，不可AC）我们设第个窗...

2021-09-09

1 487

题解 | #旋转跳跃#

题意：给你一个的排列和个数对，每对数对表示可以将和两个元素交换，你可以交换任意多次，问任意操作次后能得到的字典序最小的排列是什么？解法一（BFS，不可AC）用BFS枚举所有可能的排列，最后取字典序最小的排列判重可以将排列转换成字符串再用unordered_map进行判...

C++ 并查集

2021-09-08

0 523

题解 | #路径数目#

题意：给你一棵个节点的有根树，根节点为1，每个节点的权值为0或者1，问有多少条从根节点到叶子节点的路径，使得所经过的节点权值和不超过2 ？解法一（深度优先搜索）从根节点对整棵树进行dfs，然后计算答案具体的：我们定义递归函数表示当前...

C++ 深度优先搜索广度优先搜索

2021-09-07

0 453

题解 | #父子情深#

题意：给你一棵个节点的有根树，给你个操作，每次你需要将以为根节点的子树所有节点的权值加上最后返回所有节点的权值解法一（暴力算法，不可AC）首先对整棵树进行一次dfs，预处理出每个节点的父节点然后对于第个操作，我们直接一遍dfs将对应子树节点的权值加上对应的值...

C++ 深度优先搜索

2021-09-07

1 593

题解 | #新集合#

题意：给你一个的整数集合，再给你个限制条件，条件的形式如下：第个条件给你两个数，表示和不能在同一个集合中现在问你总共有多少种选法，使得所选集合满足条件？解法一（暴力枚举）发现本题中数据范围，于是我们可以直接枚举每一个数字选或者不选两...

C++ 深度优先搜索

2021-09-07

1 529

题解 | #中序序列#

题意：给定一棵节点数为的二叉树的前序遍历和后序遍历的序列，求出该二叉树中序遍历的序列解法一（递归求解）我们考虑表示求解前序遍历的序列为，后序遍历的序列为的一棵子二叉树的答案 1. 根据前序遍历的性质，我们知道当前子树的根节点为 &nb...

C++ 二叉树

2021-09-06

2 769