wangyi78

摘要： P4994 终于结束的起点 解题思路 几个要点 ： 一、 不能用数组，可能会爆； 二、 由于数可能溢出，每次加之后要对M取模，我习惯叫它对于M的特征值。 这个和码蹄集有一题有点像，不过那题是找规律题 #include<iostream> using namespace std; int main() 阅读全文

摘要： P1025 [NOIP 2001 提高组] 数的划分 解题思路 方法一：DFS 一步步枚举下一个可选的数。 #include<iostream> using namespace std; int n,k; long long ans = 0; void dfs(int remain,int cnt, 阅读全文

摘要： P1192 台阶问题 题解 深搜会超时，本题最简单的方法是动态规划。ai给出了记忆化搜索的答案，但是很反直觉。 这里需要令dp[0] = 1 , dp[1] = 1; #include<iostream> using namespace std; int cnt ; int n,k; long lo 阅读全文

摘要： P1464 [PacNW 1999] Function 题解 由于递归会多次调用导致超时，显然需要记忆化搜索，省去重复调用的过程，所以这里需要一个三维数组dp[25][25][25]; 另外，本题数据很大，需要统一long long（每次涉及到这个都要调试好久） ac✅️代码 #include<io 阅读全文

摘要： P1036 [NOIP 2002 普及组] 选数 题解 理解题意 对于数组 1 1 1 4 6 ，可以选出3个1 4 6，这三个组合虽然内容相同，选的却是不同位置的数，所以算作不同组合。 选数字的时候要注意，我们只能在已经选的数后面选，保证不重选，其实如果每次都是在所有数中选，答案只需要处理一下 f 阅读全文

摘要： 数的计算 题解 动态规划 对于一个数n，例如n等于12，那么答案序列就是： 12 12 6…… 12 5…… 12 4…… ……依次类推 假设以n开头的数列一共有f[n]个，那么f[12] = 1 + f[6] + f[5] + f[4] + f[3] + f[2] + f[1]。 动态规划的思想， 阅读全文

摘要： 给出完美二叉树（或者完全二叉树）的层序遍历，转换为前中后序 对于一个层序序列中某个下标为u的数，它在二叉树中对应节点的左节点在层序遍历中的下标为2 * u，右节点为2 * u + 1。 根据这个规律，我们就可以构建出一个完美二叉树（因为每个节点在二叉树中的左右关系都清楚了） 接下来就是怎么把对应的数 阅读全文

摘要： 本题传送门 解题思路 要动态维护，我刚开始使用的是优先队列，pair，让人数为first，second为窗口编号，这样就能按照题目要求的“先找到人数最少，再找到编号最小”。然而 后面发现，这样无法确定等待的人该进哪个窗口，即什么时候有人办理好的问题我无法解决。 后来发现，可以用一个queue q[3 阅读全文

摘要： 本题传送门 解题思路 这题与天梯赛L2-013几乎一样。 就是计算连通块的数量，这里我刚开始直接看acwing的翻译题，但是acwing上的题目擅自加了一个条件：初始时所有城市连通。然而在acwing上ac的代码 在PAT上WA了，因为PAT上没有这个条件。 攻下一座城市之后，为了让所有城市连通，只 阅读全文

摘要： 本题传送门 解题思路（substr + find） 我们定a为大串，b为小串。 然后分两种情况，要么刚开始就可以在a里find b 要么经过位移才能find b 后者很容易实现，即枚举每个位移后的大串。 ac✅️代码 #include<iostream> #include<algorithm> #i 阅读全文