给定长度为的数组，一共次询问：每次询问给定一个长度的数组的一个子集。   定义：集合的权值为该集合内所有元素的异或值   定义：超集为包含该集合的其他所有长度为的数组的子集   求该子集的所有子集的权值之和 以及 该子集的所有超集的权值之和   例如题目样例：数组为   第次查询为长度为的子集(这是下标)，所以实际为   该集合的所有子集为，，；对应的权值为，，；所以所有子集的权值为   该集合的所有超集为，；对应的权值为，；所以所有超集 的权值为      解决这道题目使用的前缀和的思想   设(其中的二进制表示状态，即构成的集合)表示其包含所有子集的权值之和   设表示其包含所有超集的权值...

维护每个节点 从根节点出发到现在节点的26个字符前缀之和即可 + LCA模板   没太多好说的   总代码：   #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define HelloWorld IOS; con...

将修改为到的数字，求有多少种不递增序列   举一些例子后，发现解决这道题目的核心就是求：现在有连续为的长度为，然后可以填写的数字有个，求有多少种方案   可以填写的数字有个，化简为能填写.       使用隔板法求求方案数：现在需要填写的格子有，可以填写的数字有个。   设表示数字填写的个数，...，表示数字填写的个数。那么有：          方便点，将所有的加上，那么：          所以现在一共格子，有个间隔；一共有个数字，那么需要用隔板来分成个区块分别表示每个数字的使用个数   所以有种方案   因为最大可以达到，那么首先处理出阶乘数组......   总代码：   #...

第一道题目：给你一个长度为的字符串，然后判断个字符串是否是的子序列。https://ac.nowcoder.com/acm/contest/1083/B   以这道题目介绍基本的模板，首先以字符串建立数组，表示：中第个字符；表示：从个字符向后面走最近的字符的位置   函数：   初始化所有的都为无穷大，表示后面没有；   注意的下标从开始，我习惯从开始，所以前面加上空白符号后，需要减去   注意初始化时，下标必须从到完整覆盖   后面的转移方程很好理解，只需要注意是逆序更新的，因为从后向前推就是为了找‘第个字符后面最近的位置。   const int N =&nb...

小超的记忆是个问题，虽然很多东西都写过，但就是忘了。   千锤百炼成钢，不知道要做多少题目才能记住（^_^）      分组背包，现在有个组，第组里面有件商品，每件商品都有它的价值与体积；但是每个组里面的商品最多选择一件，求总容量为时的最大价值。   与背包大差不差，需要注意外层循环为体积，内层循环为商品，这样保证了每一个体积只会被当前件商品中的一件商品更新一次，这样就解决了每个组里面的商品最多选择一件这个问题。      总代码：   #include<bits/stdc++.h> using namespace std; #define endl&...

背包问题中输出最大价值的任意一种方案      表示：容量为的背包能够装到的最大价值   表示：当考虑完前个物品后，当背包容量为时所装的最大价值，第个物品是否必须使用      这里是小于符号，而不是小于等于符号。小于符号表示这有更优的方案转移而来，而如果等于，那么可能可以从另外一种等价的方案转移而来，那么会导致记录成为不必须，造成混乱。   if(dp[j] < dp[j - v[i]] + w[i]){     dp[j] = dp[j - v[...

虽然贪心算法是入门算法，也是接触最早的一个算法：是一种在每一步选择中采取当前状态下最优局部决策的算法。但难的贪心算法题目经常会让人无从下手或者朝着看似正确的方法去做。      直接按照人数上限从大到小排序，然后用小根堆存入目前所有选择士兵的战斗力，那么堆顶就是所有士兵中最菜的一个   排完序后，从第个士兵依次遍历到第个士兵，因为我们是按照人数上限从大到小排序，所以决定目前所选士兵总人数的是目前考虑到第个士兵的   那么会发生下面两种情况：     如果，这表示我们所选择的士兵人还没有等于或者超过第个士兵的人数限制，那么我们可以直接将这个士兵选择进来   如果，那么我们就需要根据小根堆一直删除...

方程的建立：：     表示的状态，即从出发，已经走了所有的点用二进制存储，这个二进制数就是。例如如果，的二进制为，那么从出发经过的所有点有.   表示起点   包括。因为题目说有重力加速与反重力加速，那么可以有四种：从出发，即没有使用重力加速也没有使用反重力加速，此时为；使用重力加速但没有使用反重力加速，此时为；没有使用重力加速但使用反重力加速，此时为；既没有使用重力加速也没有使用反重力加速，此时为；    初始化：   很显然我们得把都给初始化无穷大，因为我们求的是最短距离。但是对于起点，其距离得初始化为   memset(dp, 0x3f3f3f3f, sizeof(...

基环树：将个点和条边的连通无向图，即在个节点的树上添加一条边恰好包含一个环的图，称为基环树   图的直径：在一个图中，任意两个节点的距离的最大值   个节点构成的所有基环树中，最小的直径是多少？     当时，就是一个最简单的环，此时直径为   当时，可以构造这样的结构：，这样任意两个节点的距离的最大值为    总代码： #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define&nbsp...

这道题目和上一道题目类似，但是第个工作是需要在或之前做，需要的时间来做   同样的，需要的是按照截至时间从小到大排序，那么是按照从小到大排序   不多详解   总代码：   #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long long #define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define...

这是我第一次做到反悔贪心的题目   第座建筑有两个参数：需要秒维修以及需要在秒之前完成维修，否则报废   无论是按照从小到大排序或者从小到大排序都会有个问题，就是可以一开始就选择了很不好的选择，例如我按照从小到大排序，我的想法是物品维修时间小的先修，维修时间大的后修。   反例：   10 30   20 20   如果我先维修第一个，那么就不能维修第二个了；但是如果我先维修第二个，那么也可以继续维修第一个。      如何确定那个先修，那个后修呢？这与它们的紧张度。   在这道题目里面，由决定，所以我们需要按照从小到大排序。但是也会出现上面反例的情况，这时候就需要做出反悔了，我将之前一个耗时...

从到的任意简单路径（不重复经过顶点）顶点的权值序列为，需要满足，即不单调递减，那么得分就是中不同值的个数。   求到中所有简单路径中最大的得分是多少      因为权值需要满足不递减的关系，所以即使能到达，但如果，那么不能走到   所以我们需要将每个点的权值从小到大排序，但是不需要排序，因为是起点。这就是运用到拓扑排序的思想，只有前面权值小的点更新了，那么我才会更新权值大的点，因为如果我直接更新权值大的点，那么会造成遗漏情况。   虽然现在确定了遍历的顺序，例如现在点，所有能够到达的点：     如果，那么   如果，那么    那么可以写出下面的代码：   #include<bits/...

给你个点和条双向边，然后又给你条从到的双向计划道路。这一共边构成的图中：设从到每一个点的最短距离为，现在最多可以删除多少条计划道路，使得删除后的图中从到每一个点的最短距离仍然为。   例如一条双向计划道路为，表示到的双向计划道路的权值为，如何判断这一条计划道路能否可以删除呢？     如果，那么这条计划道路就可以删除，因为在图中到最短距离小于直接到的最短距离，那么这条边肯定可以删除   如果，那么到最短距离虽然等于直接到的距离，但是有可能是，其他从到路径的长度构成了最短距离。那么如果存在到的路径满足，那么这条计划道路就是可以删除的    做法是先用求出边构成的图中从到每个点的距离，然后判断即可...

给定一个无向连通有权图，其中是顶点集，是边集，边权为   生成树的概念：是的一个子图，满足：     包含的所有个顶点   有且仅有条边   子图是连通的，且无环    最小生成树的概念：在所有的生成树中，边权值和最小的生成树      判断能否构成一棵最小生成树以及求出最小生成树的边权值之和有两种方法：  算法，时间复杂度为   算法基于贪心的思想，每次找已选点集合与未选点集合之间权值最小的边连接   详细解释这一段代码：   表示的是这个还没选进入最小生成树的点与已经选进入最小生成树的点之间构成边的最小边权值   所以如果，说明有最小的一条边可以选择，这样最小生成树的边总权值可以最小！  ...