题意 给你瓶药剂，每瓶药剂都有个能量，每次要挑出两瓶药剂合成为一瓶药剂，合成后的药剂能量为。求最后合成只剩一瓶药剂时他能量最大可能值。 题解 由于先合成的实际上每次都会被减半，合成几次就减半几次，所以一开始合成能量小的是能让损耗降低的。所以考虑贪心，也就是哈夫曼树，使用一个优先队列用来存储。每次从队首取两个值，将其的和的二分之一压入队中，直至队的大小为1。输出即可，有一点是，答案可能不为小数，那么输出需要注意一下。 复杂度 时间复杂度O(nlogn) 代码 #include<bits/stdc++.h> using namespace std; priority_queue<...

题意 给你个数字，并用，次幂，阶乘，位运算这些操作让这个数变为24。求是否可行 题解 这里除了次幂和阶乘能够让数字变大之外，别的操作都会使数变小。所以我们可以利用阶乘来凑出。例如若当前个数字的和为时，而若和为，则。对于为时，任意一个数通过无限次开方趋近于1，再加上向下取整就都可以变为1，然后求和就为4了。对于都为时，的阶乘为，同样可行。所以和大于等于时都是可行的。特判一下时以及时，的情况是不行的，存在某个值大于等于时，可以将另外一个值通过不断开方与利用阶乘凑成。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; in...

题意 给你两个串，以及一个操作序列，按顺序的顺序删除上的字符，要求每次删除后都是的子序列，问最多能够删除多少次。 题解 由于是子序列而不是子串。验证的时间是的，我们可以考虑二分删除次数。将要删除的字符的地方用别的字符代替。然后遍历删除字符后的串判断是否含有子序列。若有则说明删少了，若没有说明删多了。这样进行二分即可。 复杂度 时间复杂度为 代码 #include<bits/stdc++.h> using namespace std; const int N=1e6+5; int c[N]; int f(string a,string b,int k) { for(int i=0;i...

题意 给你一个有个节点的完全图，问从这个完全图上删去一棵生成树，最多可以删除几次。 题解 若该图有n个点那么最多可以删次，对于完全图来说一共有条边，一棵生成树一共有条边，我们可以构造性的删除所有的不同的生成树，方法如下：无论是为奇数还是偶数，都可以用这样的方式进行删除生成树，也就是能把所有的边都删去，一次能删条边，也就是一共能删次。 复杂度 时间复杂度 代码 #include<iostream> using namespace std; int main() { int t; scanf("%d",&t); while(t--) { int n; sca...

题意 给你一个长度为的序列，将其分为三个子段，每个子段的和相等，问有多少种划分方法。 题解 先考虑求一个前缀和。若序列长度小于或者总的序列和不能被整除说明无解输出。然后我们再考虑有多少种方案数，我们有了前缀和，那么我们按顺序遍历序列的前缀和，记录一下前缀和为的值有多少，每次遇到一个的前缀和，之前的前缀都可以和他进行组合凑成一组，所以每遇到一次就将之前的个数加到答案中。这样遍历一次就可以得到最终的方法数了。由于可能有都是的情况，所以方案数需要开存储。 复杂度 时间复杂度 代码 #include<iostream> using namespace std; const int N = ...

题意 有一个有个点的完全图，其中有条边的边权为，剩下的边的边权为，求最小生成树的花费。 题解 由于边权只有和而且是完全图，由于是完全图说明任意两个点之间都会有一条边相连。那考虑所有边权为的边构成的子图，在这个子图中，由于边权为不需要花费，所以这些点都可以选择，这相当于原来的最小生成树就是在边权为的子图中，在各个联通分量之间添加一些边使其变成一个图，由于原图是完全图，所以这样的边肯定存在且权值为。换句话说，最小生成树的花费就是边权为的子图所构成的连通分量-1。我们可以记录一下边权为的边，然后对于每个点，我们去访问和他没有相连并且未被访问过的点，每个点一次，能够几次就说明有多少个联通分量。对于记录...

题意 有个人要来吃饭，每个人至少要吃份食物，但是有关系，如每条关系，表示要吃的比多，问最少准备多少份食物可以满足要求 题解 可以通过上述描述进行建图，某条关系就是一条有向边。可以从吃的最少的人开始考虑，也就是说需要反向建图，然后再进行拓扑排序，根据拓扑深度，当深度为时，那这个人所需要的食物就算，在深度为的点时其需要的食物就是。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e4+5; int in[N]; int a[N]; vector<int>E[N]; int topo...

题意 有两个等边三角形其边长为A和B，你可以每次将大的等边三角形的一条边变为任意一个整数，但是要求改变后仍能构成一个三角形。问操作多少次可以将大的等边三角形变为小的等边三角形呢。 题解 正着考虑从A变为B，实际上是不太好处理的。所以我们可以考虑从B变为A，这样的最小次数和从A变为B是一致的。那么从B变为A需要怎么操作呢。我们可以贪心的让每次让最小的边增大的尽量多，有两个限制条件就是不能超过A其次是其他两边之和要大于这条修改后的边。这样我们每次贪心的修改最小的边，然后使得最后所有的边都变为A即可。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using ...

题意 给你一个长度为的序列，问你存在多少个区间使得区间中的元素和能为的任意一个次幂。输出区间数量。 题解 考虑前缀和，某个区间的和可以表示成。我们可以移项得，我们用几个hash来记录的值的数量，然后在遍历过程中的贡献就是其减去后其结果在hash中的数量。我们每次枚举一个的次幂然后遍历一遍前缀和数组，答案每次加上，并在这次将。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N]; long long sum[N]; map<long long ,int>...

题意 给一颗二叉树的括号表示法，求这棵二叉树的中序遍历序列 题解 由于给定的字符串中的整数并不是只有一位的，可以先将字符串处理一下，将数字部分和括号逗号进行区分一下。将处理完的存入一个vector数组。我们建立一个树节点的栈，考虑从左向右扫描，若遇到了左括号，这说明当前节点是一个子树的根节点直接入栈。且标记一下下一个节点为左儿子。当遇到的是数字时，那其肯定是一个儿子节点，若我们标记的左儿子为真则将栈顶的当前子树弹出，其左儿子赋值为当前数字，若左儿子节点为假说明是右儿子，给右儿子节点赋值。当遇到是逗号时这说明下一个节点肯定是右儿子了，那就将左儿子节点标记为假。若遇到右括号表示当前子树已经构造完毕...

题意 给你个，两个相同的数可以相加成新的数。问最后只留下个数，还需要新增多少个。 题解 由于两个相同的数合并成一个新数，所以最后个数肯定是这种。那么我们先考虑一开始的若尽量的合并可以变为多少个数呢，实际上就是二进制下的个数。相当于我们只要将最终的的二进制下的个数小于就可以了(因为，大于的部分可以分裂成两个一样的)。那我们如何去减少原有的的二进制下的个数呢，有一个结论就是在某个数的二进制下的位置上再加上一个，那么这个数二进制总的的个数只会保持不变或减少(多次进位会导致减少)。所以可以基于贪心的策略，每次加上其最低的。最低的可以用来实现。 复杂度 时间复杂度 代码 #include<bits...

题意 给你一个长度为的序列，他想知道序列中有多少组，使得。 题解 首先对于某个数的二进制来说，他二进制中的某个若变成那改变完后的数肯定是大于原来的数的，扩展的话。若该数某一位改为且该后面位的数都变为那这样更改后的数也是大于原数的。有了这个结论我们可以记录一下序列中每个数二进制的最高位的位置。然后我们再去遍历每个数的每一位，若这个数的这一位上为，那么就在答案中加上该为是最高位为的数的数量。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; const int N=1e6+5; int a[N]; int vis[35...

题意 给你一个长度为的各个元素不同的序列，求从这个序列中构造的集合中，有多少个集合符合，集合中的任意两个元素差的绝对值都是2的次幂。两个集合不同即两个集合的长度不同或某一元素属于集合但不属于集合。 题解 首先我们得先明确一下这样的集合大小，最大是多大。假设集合中有三个数。那么他们需要满足。 那么即，若要为整数解，易得且。且三个数为等差数列，公比为。若集合大小为大于等于4，那么同理，就得形成多个形式的等差数列，这明显是不成立的。所以这样的集合大小最大为3。有了这个结论之后，我们可以先预处理一下公比2的次幂，即小于之内的二的次幂。然后对序列进行排序，对于每个数我们检验一下其是不是2的次幂，若是答案...

题意 给你一个序列，问你可以删除其中一个数字并将其插入到序列中的任意一个位置，若选择必须要删除插入，或不选择。问是否可以将该序列分为左右两个子序列使得其左右子序列的和相等。 题解 首先求总的和，若总和为奇数说明不可能划分为两个和相等的子序列。由于所有的数都至少属于其中一个子序列，且两个子序列的和相等的，所有任意一个子序列都应该等于。如果要选择一个数删除再插入的话，这个数可能存在在左子序列中，即在前缀中。令前缀为，且，假设我们是从开始加上每个数的。那么我们就应该从前缀中找到一个数这个数在前缀中出现过(这里可以用map来存这个数)，这个数就为。这样就可以的遍历来找一遍。同样的这个数也可能存在右子序...