题目一：https://codeforces.com/problemset/problem/577/B   普通的背包时间复杂度为超时，可用优化至   存储的余数是否可达  这部分代码的意思是直接异或以及异或它的余数  bitset<20050> now_bit = bit; now_bit <<= a[i]; bit |= now_bit; bit |= (now_bit >> m);      总代码：   #include<bits/st...

树上合并，将除根节点的其余个点都合并，一共合并次，这样整棵树合并为一个点。合并的同时更新代价   具体的证明过程其他题解有   #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 I...

首先，如果选择个粒子，那么这个粒子都需要满足，即   如果选取商店里的粒子，假设一共选择了个粒子，那么需要满足，其余了个粒子都需要满足，那么此时能量的最大值为   定义表示原始粒子中所有满足的前大粒子的能量和     如果的粒子数小于，那么就是这全部粒子的能量和   如果的粒子数大于等于，那么取前大粒子的能量和    如何求：   将从到按照从大到小的顺序遍历，这样满足已经放入的粒子仍然满足，现在需要维护前大的粒子能量和最大值，所以用优先队列模拟   使用小根堆，这样先进去，如果堆里面的元素数量多了，再取出堆顶最小的几个元素     总代码： #include<bits/stdc++.h...

二叉树的递归不熟      前序遍历是：根-左-右，所以前序遍历的第一个节点一定是该子树的根节点   那么根据题意，首先先找到根节点，然后将后面的区间分成左子树与右子树两个区间（拆分的依据是根据键值与根节点键值的大小关系），例如左子树的全部键值都小于根节点键值，右子树的全部键值都大于等于根节点键值；同时有可能是二叉搜索树的“镜像”，那么就是左子树的全部键值都大于等于根节点键值，右子树的全部键值都小于根节点键值；      分类处理普通的搜索二叉树与其“镜像”   首先找出，即将拆分成，，，对应根左右的区间；循环找到，后续判断是否满足都大于等于或者都小于   if(l >&nbs...

在上上上篇题解中有两个重要结论：   任意一个排列一定可以唯一的分解成若干个互不相交的置换环并集   假设长度为的排列有个置换环，那么交换任意两个元素使得排列升序的最少操作次数为次    现在补充两个排列与逆序对的结论：     一个排列中，交换任意两个元素，逆序对数的奇偶性一定改变   排列的逆序对数与的奇偶性相同       证明第一个结论：     如果交换的位置相邻，那么逆序对数加或者减，那么奇偶性改变   如果交换的位置不相邻，设交换的两个位置之间有个元素，那么两个位置相当于与中间个元素都进行了一次交换，所以是次交换，再加上两个位置的交换，所以是次交换，所以奇偶性改变    证明第二...

大小为的数码问题，两个局面可达，结论：     当为奇数时，当且仅当两个局面下网格中的数依次写成行个元素的序列后（不考虑空格），逆序对个数的奇偶性相同   当为偶数时，当且仅当两个局面下网格中的数依次写成行个元素的序列后（不考虑空格），“逆序对数之差”和“两个局面下空格所在行数之差”奇偶性相同    所以就是归并排序求逆序对         总代码： #include<bits/stdc++.h> using namespace std; #define endl '\n' #define int long lo...

前提知识：     P1031 [NOIP 2002 提高组] 均分纸牌：https://www.luogu.com.cn/problem/P1031    P10452 货仓选址，https://www.luogu.com.cn/problem/P10452        题目的意思是有一个个摊位，然后给出喜欢的个摊位的左边，每次操作可以在某一行或某一列里面选取相邻的两个摊位（每一行或每一列的第一个位置和最后一个位置也算作相邻）然后交换这两个摊位，目的是使得每一行的摊位个数相同，每一列的摊位个数相同并且输出最小操作次数，具体输出，如果不是，则还需要输出最小的操作次数      分析题目可知一...

任意一个长度为的排列，如果可以交换任意两个元素，最终使其排列递增即的次数为   置换环是描述排列错位关系的核心结构，在至的排列里，一群互相占据对方位置的数，顺着本该去的位置追踪，最终会形成一个闭环，这个闭环就是置换环   任意一个排列一定可以唯一的分解成若干个互不相交的置换环的并集，这是置换群伦中的一个基本定理   一个长度为的置换环中，环中的所有元素，没有一个在正确位置，且元素之间是循环错位的，那么操作一次可将一个长度为的置换环拆成一个长度为的置换环以及一个长度为的置换环.....由数学归纳法可得到操作次数是   假设长度为的排列中有个置换环，减去每个置换环少的一个次数，所以就是次     ...

没做过类似的题目，将括号想象成节点，然后转化为二分图的形式      就是将每一对括号想象成一个节点：   根据条件一：一对括号的染色情况必须相同，每一对匹配的括号，是一个颜色绑定的整体。可以直接把一对括号抽象成一个节点，节点的颜色就是这对括号的颜色，不用再单独考虑每个括号   根据条件二：相邻位置的括号字符相同，其颜色必须不同，假设相邻的两个相同字符，分别属于节点 u 和节点 v。因为这两个括号的颜色必须不同，而它们的颜色就是所属节点的颜色，所以节点 u 和节点 v 的颜色必须不同      那么问题转化为一个无向图二染色问题：   现在这里有若干个节点（对应每一对匹配的括号）   两个节点...

洛谷蓝题在牛客也只能有1245分   题目很有意思：就是一开始给定10个数，；然后一共有次操作，每次操作交换两个位置的数。然后一共次查询，每次查询重新从第次操作执行到第次操作后的最终序列为什么。   题目的例子：   第次操作：   第次操作：    第次操作：    第次操作：    第次操作：   第次操作：   第三次查询为，结果为   本来因当是从开始执行操作，但是每次查询都这样肯定会超时   其实就可以当作从第次执行，然后惊奇的发现位置其实已经对应好了   第次操作为 ；把不同的位置对应为   那么就是，，，....，   然后只需要对应到第次...

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

维护每个节点 从根节点出发到现在节点的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...