题意 给你一个包含个数字个操作符的表达式，计算其是否值为24。是输出Yes，否则输出No 题解一 由于输入的格式是固定的，而且只有一位数以及三个操作符。三个操作符在表达式字符串中的下标位置为，并且总的表达式类型个数也只有64种。所以我们可以先用程序把这64种表达式的语句打印出来，再粘到程序里面，即 char op1[4]= {'+','-','x','/'}; char op2[4]={'+','-','*','/'}; for(int i=0; i<4; i++) for(int j=0; j<4; j++) for(int k=0; k<4; k++) { printf(...

题意 给定一个长度为的数列，用这个数列构造一棵哈夫曼树，从根节点遍历到某个节点上边权的路径值即为该节点的哈夫曼编码，现在输出某些数组元素所对应的哈夫曼编码。 题解 由于我们需要每次选择两个最小的数来构造哈夫曼树，每次进行排序肯定不行，这就需要用到小根堆，即优先队列。存入优先队列的是当前这棵哈夫曼树，并记录其根节点的权值。我们每次从优先队列中取出两个值，小的值作为左儿子，大的值作为右儿子，新树根的权值为左右儿子权值之和，并记录下子树大小，将先建的树入队，若两个节点的权值相同，子树大的作为右儿子，反之作为左儿子。这些记录值都可以在结构体或者类中实现。当队列中只有一个元素时，就说明哈夫曼树构造完成了...

题意 一些分数可以由等比小数和的形式构造，现在给你小数的公比和其在小数点后第几位，问所对应的分数是什么呢。 题解 我们可以通过定义写出式子，那么可以直接使用等比数列求和公式，就有，由于题目保证初始为小数，所以那么，其无限次幂为，那么可以化为，我们再求一下分子分母的最大公约数，化简一下即可。 时间复杂度  代码 #include<bits/stdc++.h> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int a,k; scanf("%d%d&quot...

题意 给你一个个点条边的无向图，每条边都有一个权值，问你权值和为的生成树是否存在。 题解 首先注意一下的范围，的范围只有两种，所以这样的生成树就是比较特殊了。对于这个图我们可以先求一遍最大生成树，其值记为，再求一遍最小生成树其值记为。对于任意一棵生成树来说，他的边权只有构成，但是这里有最大生成树和最小生成树，因为这两棵树是存在的，也就是说你可以从最大生成树转化到最小生成树，也就是将一条的边替换成的边，这样的转换过程是肯定存在的。那么由于可以转换，也就是说范围在之间的生成树都是存在的。故我们可以用的来查询权值为的生成树是否存在，即在范围内的输出，否则输出。 复杂度 预处理复杂度为，查询复杂度为 ...

题意 给你电子表上的时间求过了分钟之后电子表上的时间是多少。 题解 首先电子表上的时间以如下形式 **** ...* **** **** *..* **** *... **** **** **** *..* ...* ...* ...* *..* *... *... ...* *..* *..* *..* ...* **** **** **** **** **** ...* **** **** *..* ...* *... ...* ...* ...* *..* ...* *..* ...* **** ...* **** **** ...* **** **** ...* **** ...*观察...

题意 求区间内，其本身不是质数但是只有一个质因子的数有多少个。 题解 首先确定这样的数是什么，是质数的次幂形式，因为只有这样的数他本身不是质数但是其质因子只有一个。那么我们看数据范围，符合条件的数至少是质数的平方，所以我们只用找之内的质数就好了。对于每个找到的质数，我们将其小于的次幂都存在一个数组当中。由于次幂增长的很快，所以这样的数的个数大概只有个。然后我们把存下的数进行排序。然后对于给定的区间，我们用二分去找上下界，一减就是区间范围内这样数的个数了。注意的是若用c++，上界可以用，下界用去找。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> usin...

题意 给定一棵二叉树的前序和后序序列，问有多少棵树能满足这样的序列。 题解 首先确定为什么一棵树的前序和后序无法构建唯一的二叉树，因为由于，前序和后序的信息只能确定某个节点其子树的大小，那么若某个节点只有一个儿子的话，是无法确定是左儿子还是右儿子的。所以这样的二叉树也就不唯一了。那么我们只要在递归时判断一下其是不是只有一个儿子，记个数，根据乘法原理，那么最后不同种类的二叉树个数就是个了，这里用一个快速幂可以求解。那么如何递归来确定某个节点其儿子个数呢。根据前序和后序的性质：  root 儿子 前序： 3 2 1 4 5 后序： 1 5 4 2 3 儿子 root若当前前序节点下标为，那么其第一...

题意 给你一棵树的前序和中序序列，问你这棵树能否用前序和后序构造出来，若可以输出Yes，若不行输出No 题解 首先为什么前序后后序序列无法唯一确定一个二叉树呢，实际上是可以通过前序和后序序列知道，对于某个根节点其左右子树是什么的。但是若出现这样的情况，一棵子树只有一个儿子，那么它在前序和后序中确定的儿子数量也是1，但是前序和后序提供的信息无法确定该儿子是左儿子还是右儿子，这样就会导致有两种情况，树也就不唯一了。所以一棵树若可以用前序和后序序列构造出来，那么它需要符合哈夫曼树的性质，即出度只有或，要么是叶子节点，要么有两个儿子。所以我们可以在用前序和中序建树的同时来判断一下该节点左右儿子的数量，...

题意 给你一个01字符串，要求将该字符串划分为几个部分，且每个部分有且仅有一个，问一共有多少种划分方案，答案可能很大对取模。 题解 我们以每个作为分界线，由于每个部分只能含有一个，所以和之间是独立的。那么我们只用考虑相邻两个之间的划分方案数，若两个之间隔了个，那么相当于有个空可以用来插入隔板，所以两个之间的划分方案数就是，那么整体的方案数实际上就是，相邻的之间的乘积。由于是乘积会比较大，所以答案需要取模。我们可以先记录下来每个的下标，那么两个的下标之差就是他们之间的个数+1了，然后遍历一遍记录的的下标即可。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h>...

题意 给你一个数组，请能否将数组划分为几段，且段数大于1，这些的段和都要相等。问划分后的段和是多少，若无解输出。 题解 由于划分为多段，其中第一段肯定是包含第一个元素开始的，那么答案就肯定是某一个前缀和。所以我们可以先记录下数组元素的前缀和。枚举前缀和的值然后对这个值进行检验。若前缀和是，那么我们从开始检验，记作为前一段的右端点值，表示检验段的右端点。去遍历的值，其中表示这段的和，若其等于，那么令，继续检验下一段。那么判断所有段都满足情况的时，且检验的段数需要大于1。但是需要特殊考虑一种情况，就是当数组末尾是连续的组成时，需要特判一下，即时也是可行的。 复杂度 时间复杂度为 代码 #inclu...

题意 给你一个数组和，你可以将数组中的元素变为其与的异或值，问你最少操作多少次使得数组中能有两个相同值，无解输出 题解 答案只会是。根据异或的性质，时表示，所以不会出现需要数组中两个元素异或过后相等的情况，这说明数组原本就有两个元素相等了，不需要异或操作，所以答案是。若原数组中没有两个元素相等，我们先将数组中元素进行记录一下，然后依次对数组元素与的异或值进行判断是否在字典中出现过。若出现过那么答案就是，若整个数组都处理完了也没有答案，说明无解输出 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int ...

题意 给你一个数列，求从中挑选出一些数进行求和，使和在的区间内，请问有多少种方案呢。 题解 由于数组的长度只有，所以我们可以枚举所有的组合，我们可以用二进制下和的关系来表示如何选择元素，其中表示选择，表示不选。例如，表示选了，，别的不选。所有我们可以从枚举到。这样就可以包括所有的情况，然后对于每种情况我们求个和，判断其是否在的范围内，若在就答案加一。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; int a[25]; int main() { int n,l,r; scanf("%d%d%d"...

题意 给定一个和，问能否将拆成个的次幂的和，将次幂序列输出，若误解输出 题解 首先考虑无解的情况，将转化为进制，二进制中的个数是其能转化为的次幂和的最小情况，所以当小于二进制下的个数时无解，另外大于时无解，由于最多拆成个的和，所以当大于时也无解。由于题目说任意输出一个可行的序列，所以我们先将分解成二进制，用字典或者数组来存其二进制的个数和权值，由于二进制满足。我们用来记录现在有多少个二进制数了，所以我们可以对最高位每次进行分解这样每次可以多出最高位的个数，然后对应的要加上两倍的的个数，同时可以把当前最大权值进行更新。这是在时可以这样进行。当，这说明我们不用把全部的最大权值的进行分解，只用分解个...

题意 给你一个数组，求最大的区间使得 题解 首先看数据范围，，只有两种取值范围。那么转换一下题意就变成了最长的区间，这个区间中和的数量是一样多的。那么我们可以怎么处理呢，我们可以将用来替换，然后对数组求一个前缀和。然后可以分两种情况考虑。  若说明的区间内和的个数是一样的。 若说明这个区间之内和的数量是一样多的，因为前缀和是一样的，说明和的个数抵消了。  我们去记录每个和所对应的第一次出现的位置，然后再记录一下每个答案的区间大小，题目要求若区间有多个要求输出最小的那个区间。所以按从1到n的顺序遍历存下的答案即是满足题意的答案了。 复杂度 时间复杂度 代码 #include<bits/st...