题目描述 给你长度为的一个字符串，你可以选择长度为的一段合并成一个字符，并且会得到一个价值。现在通过二进制中大小在后面的行中依次给出，问你这个字符串在最优的合并情况下，可以得到的最大价值是多少。 Solution 通过题目发现，所以最终得到的字符串一定是一个的字符串，如果存在大于情况，一定可以再合并一次获得更大价值。再看的数据范围在很明显在指引着你走向状压的路上。那么我们又从上面发现我们最终可以得到字符串一定是以内的。所以我们使用区间从小到大枚举每一个长度为的区间，如果当前区间长度可以最终被合并成的情况下，我们就去通过枚举每次分割点，分隔成两个小区间的求解最优的情况。我们使用代表从字符串下标到...

Solution 首先我们思考一个简化版的问题，如果不支持修改，我们如何找到搬运完全部石头数的最优解。考虑动态规划解题，对于一堆石子来说，我们可以枚举搬运次数，根据求解的消耗是很容易发现数学规律，我们要让每次搬运的石头尽可能相同的多，就算有不同的不同的两次之间绝对值差值只能小于等于。那么我们考虑代表把第堆石子分次搬完的最小花费是多少。这个花费计算也很简单，直接通过先平分，后面多出来的添加个石头把它分完即可。那么我们找到了分别运送每一份石子的最小花费，接下来就是算合并不同堆的操作了，很明显如果干巴巴的转移会发现很难实现，因为合并前个石堆，你并不能记录到你最小的花费之前搬运了几次，如果需要加上的话...

题目描述 给出一个有个节点的一棵树，每个节点都有需要完成的任务数量，某个节点的任务完成数量等于全部子节点中完成数量的和，如果子节点完成数量的和依旧不够当前节点的任务，我们对于当前节点可以花费每个任务的金币进行补交任务，当然这个补交存在也可以在子节点中进行。问你，完成这个节点全部的任务最小的花费是多少。 Solution 对于叶子节点，他没有孩子节点，所以如果叶子节点需要完成任务一定需要购买。那么叶子节点的父亲，他已经完成的任务数即可直接求合得到，并且如果叶子节点父亲还不足，那么它的选择就有从孩子中选择或者自己本身。我们可以使用一个树形进行维护，回溯的维护节点以及下方孩子节点的最小值。最终判断累...

A、小L的作文 给出字符串，求解字符的出现次数。签到题，遍历计数即可。 const int N = 1e5 + 7; ll n, m; char s[5005]; void solve() { char ch = getchar(); getchar(); scanf("%s", s); int ans = 0; for (int i = 0; s[i]; ++i) if (s[i] == ch) ++ans; printf("%d\n", ans); } B、小L的多项式 因为，所以支持的解法，那么每次输入，直接带入求解即可，...

中文题意 给出头牛，并且告诉你最高的牛在位置，以及它的身高是，还有对可以互相看见的牛，两头牛之间可以互相看见，当且仅当他们它们身高相同并且中间全部的牛都比它的身高更低，并且给出的对关系可能重复，输出每头牛可能的最高身高。 Solution 考虑朴素算法，我们保证每头牛最大的情况下，就把身高初始化成，并且每次给出没出现过的关系，把关系中间中间的全部数都减掉一个，这样即可保证结果正确，但是这样复杂度最差可以来到，显然不行。考虑优化掉每次循环把数减掉这个操作，显然可以使用一个差分数组的形式进行优化，对于数组，每次关系只需要减掉，加上。再对差分数组求一次前缀和就可以找到答案了。 #include &l...

中文题意 给你长度为的一串数字序列，并且里面每个数。你要从中间选出最短的非公共子序列。也就是你构造的子序列原序列找不到。 Solution 首先我们来看几个特别的例子，如果一组样例是： 4 3 1 1 2 1 那么显然答案是1，你可以构造一个子序列它的值是3个数中没出现的哪个。再看一组样例 7 4 1 1 2 3 4 2 1 那么显然，对于前面5个数有着从[1,2,3,4]全部的数，无论你选那一个出来当子序列一定可以找到 但是，后面剩下的一段只有[1,2]说明你可以选择没出现过的两个数。那么估计也看出答案来了把，直接根据出现次数分组，我们假设首先只需要一个数字就可以得到非公共子序列，如果出...

解题思路 整个题面一看就有着溢出屏幕的线段树的味道。那么任何使用线段树维护区间，我们使用线段树又要维护什么呢？显然对于我们每次的修改，都是存在一定规律的，既公差的等差数列，并且每次求解的都是一段区间的和，那么我们就用标记推迟往下赋值的时间，并且使用记录区间的和，因为给出了首项，项数可以通过的距离求解，这样就可以通过求合公式求出来。每次把标记打上首项的值，这样在递归到下面层次的时候就可以直接求解到左右两边的对应权值。即可实现求解和更新答案。 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_...

中文题意 给你个数，问你从中挑选非空的子序列并且保证子序列的子序列数量有多少个。 。 Solution 正向不太好做，那么就反向思考，我们可以选择的总的子序列个数是个。减去选择一个素数这些子序列个数，再加上选择两个不同素数乘积这些的子序列数量，再减去选择三个素数的，依次容斥就是答案了。注意我们还需要跳过例如这样的子序列，因为我们只能选择个不同的素数相乘计算贡献。那么对于每次选择的的贡献，也就是有几个统计中有几个可以被整除，求一下这些数的子序列贡献即可。 #include <bits/stdc++.h> using namespace std; #define js ios::syn...

A、小G的sum 对于每个数，最小的约数是1，最大的约数是它本身。那么使用等差数列求合即可。 void solve() { n = read(); ll ans = n + (1 + n) * n / 2; print(ans); } B、小G的GCD 对于单个，很容易发现可以被整除的数量有个数。并且发现这些数都是等差数列，公差。那么循环遍历全部的即可找到全部的答案。 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0);...

中文题意 给你一个存在个节点，并且有条边的无向图，这个节点中存在个特殊节点。询问你从起点去终点，如果可以从，那么输出最小的最大特殊节点间隔。也就是规定你从起点出发距离为之内一定要有新的特殊节点，并且每次走在特殊节点的时候把距离清零重新计算。输出最小的。如果无法去到，那么输出一个。 Solution 看到最小的最大值我们就可以猜测二分答案，但是我们还有另外一种解法，使用优先队列去找答案。队列中存放的节点我们定义为当前需要的最大距离，终点。这样我们依次遍历节点，使用一个代表节点需要的最大距离，那么在遍历边的时候，我们要保证去到的节点比当前节点需要的距离加还跟远，不然就没有更新的必要了，这样就可以优...

中文题意 给出个数，你需要操作的次数是，现在你有3个盘子，假设编号是0,1,2，初始我们编号1中有一个小球，每次操作可以在0,2中选择一个盘子和1做一次交换，并且重新做编号。问做次操作之后，小球还留在1号盘子的概率是多少，输出最简分数的形式。 。 Solution 我们首先使用动态规划进行递推最终答案，我们假设代表第步留在0,1,2号盘子的概率。那么我们得到转移方程是。 对于每个位置都可能从旁边转移过来以及之前就保留在这个位置，并且这次选择要选择正确的移动。那么观察我们不难发现0号和2号盘子是对称的。所以我们可以得到把它带入中。再次化简你会得到：再把看成带入中，你会得到: 同理再做一次代换可以...

A、回文括号序列计数 既要是回文又要是括号序列，我们知道回文具有对称性，但是我们写一个回文串就会发现。类似这种回文串不可能是括号序列，所以只有在的时候存在一个空串，特殊判断即可。 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<int,...

请问有没有大佬知道下面代码为什么使用连接一次边连通块数量减1就只能通过70分。重新写个循环就可以AC。在印象中是可以这样判断有没有最小生成树把，而且同样的最小生成树H题这样写法都可以通过。 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define p...

F、我的心是冰冰的 根据树的特性，一定可以使用黑白染色把它分开，注意特判只有一个节点的情况即可。 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define pai pair<int, int> #define ms(__x__,__val__) memset...