Solution 先统计出原序列的逆序对，这部分可以用树状数组/归并排序完成。随后我们只关心逆序对的奇偶性。对于三种操作分别考虑：操作1，交换两个数字，逆序对的奇偶性改变。操作2，翻转序列，设当前的逆序对为 , 翻转后为 ，长度为 ， 考虑到翻转前后序列的逆序对满足 ，如果 是偶数，必为两奇或两偶，翻转不改变。如果 是奇数，奇偶性必改变。于是问题转化成计算 的奇偶性即可。操作3,4本质是一样的。只考虑左移序列，设当前序列为一个排列（可以看做把原序列离散化）首数字为 ，长度为 ，显然后面可以构成逆序为 个，那么左移后他变成了序列最后一个元素，对于前面的元素与他产生的逆序为 ，总的变化为 ...

A. 平行四边形 Solution 平行四边形判定法则：有一组边平行且长度相等，注意要先检测有没有三点共线的存在。三点共线可以用三点组成的三角形面积来计算，如果面积是 说明三点共线。剩下的就是枚举 点了，我用了一个全排列暴力枚举。 Code https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47945777 B. 子序列 Solution 最优的方案是把 放在最前面或者把 放在最后面，对这两种情况进行检验即可。如何求出 的子序列数字呢？其实每找到一个 都可以在前面所有 中 任取两个 ，所有只需要一直...

A. dd爱科学1.0 Solution 要求最少花费，只需要找到最长不降子序列，该子序列不做修改，将剩下的修改至符合条件即可。令最长不降子序列长度为 ， 答案为 Code https://ac.nowcoder.com/acm/contest/view-submission?submissionId=47881508 B. dd爱探险 Solution 状压 , 注意到 ， 构造一个长度为 的二进制串，第 位为 代表去过地区 ，否则代表没去过。必须使用两种魔法，显然有也可以二进制枚举，一共用四种情况：00,01,10,11不妨以01代表使用了双倍魔法，10代表使用了双倍魔法，11代表...

链接 Description 给定一棵树， 个查询，每次查询给出 ，查询 子树里深度为 的节点个数。 Solution 题目特征：1.可离线。2.无修改。显然思路：把查询离线，思考能否把问题转化成找在树上遍历找每个节点下面所有深度的点并统计。显然可以用树上启发式合并 实现以上任务，那么只要看我们所查询的深度有多少个节点，加入到答案就可以了。注意树上启发式合并的思想：1.暴力找轻链，统计答案，消除贡献。2.暴力找重链，统计答案，不消除贡献。3.暴力找轻链，统计答案，不消除贡献，并与重链合并。如此重链只会计算一次，而树上只有 条轻链，复杂度 得证。 Code #include <b...

Description 简单的说就是定义一个回文串为 阶回文需要满足把他切成两半（, ，奇数长度中间的字符不用管）然后这两半都是 阶的，定义回文串都可以是 阶。 Solution 不会双模数哈希，抄的题解，单模数一直被卡。按照定义，显然是可以类似于 的思想去做的，定义所有朴素的回文串都为 阶，那么先找出所有的回文串，显然当前回文串 的阶数为左边的阶数，因此直接 统计所有答案即可。由于有结论：本质不同回文串的数量级别为 ，所以通过 可以找到所有本质不同回文串并实现上述的赋值操作。需要用双模数哈希来判断是否本质不同，总体时间复杂度 。 Code #include <bits/s...

L3-1 森森旅游 Solution 对1到 的所有点建图正向跑关于 的最短路反向建图，对 到 1的所有点跑关于 的最短路令正向最短路为 , 反向最短路为 在过程中最短路大小是不会变的，不难推出每个点的贡献是 (向上取整)用一个 维护最小值即可，每次进行查找和删除操作注意并不是所有点都能在此将现金转换并到达终点，所有还需要特判一下，否则只有29分 Code #include <bits/stdc++.h> typedef unsigned long long ll; using namespace std; const int N = 1e5 + 5; const d...

Description FJ给他的牛棚的(2≤N≤50,000)个隔间之间安装了N-1根管道，隔间编号从1到N。所有隔间都被管道连通了。 FJ有(1≤K≤100,000)条运输牛奶的路线，第i条路线从隔间运输到隔间。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。（洛谷翻译） Solution 简单的树上差分，对于树上一条链上所有节点加1的操作，用 表示节点 的第 个祖先， 表示 的最近公共祖先，可以转化成 统计答案的时候只需要 统计子树的值之和即可例如下图：对(1, 3)所在的链进行差分，在 的时候得到的结...

Descripiton SOlution 不难发现 的长度最多为 。对于一段不包含 的串， 需要满足条件 至少长度为 需要满足条件 至多长度为 即长度为 的串都可能为答案的贡献，对此我们可以暴力找出到底这一段有多长，因为这一段的长度不超过 。至于前导零，我们可以记录当前位置的前导零有多少个，记为 ，那么贡献为 。 Code #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 5; string l, r, s; string cal(int...

Description 有一棵点数为 的树，树边有边权。给你一个在 之内的正整数 ，你要在这棵树中选择 个点，将其染成黑色，并将其他的 个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的收益。问收益最大值是多少。 Solution , 考虑二维树形 令 表示以 为根，选取个作为黑色节点的收益考虑每天边权的贡献，类似于树上两点的距离，对于一条边，它连接两端的相同颜色节点都会产生贡献假设边的左边有 个黑节点， 个白节点，右边有 个黑节点， 个白节点，边权为 那么贡献为 但是显然没有用到 的条件考虑在 的时候记录子树大小 枚举到根节点 和子节点 ...

Description 一堆数字，必须从左到右且全部取出，从下往上放，满足下层 上层, 求所能得到的最高层。如下图为两层：样例解释： 3 1 2 3第一层(最下面)放1 2，第二层放3，答案为2 Solution 瞎贪心肯定是不可取的，但是需要知道一个事实：在构造的过程中，在相同高度下，最底层的数字和越小，结果最优。理性的感受一下就是：最底层的数字和越小，越能够将剩余的放到上面，从而使得最终高度越高。给出一组数据 5 5 4 3 2 100可能在分析的的时候出现 100 无处可放的情况， 不妨从后往前(即从上往下放)，需要满足递增即变成 5 100 2 3 4 5令 表示到了第 个数字...

Description 给出 个数字，每个数字范围是 的自然数，有 个限制注意: Solution 从数据范围得知要从 入手若没有限制条件，则每一个位置都能放 答案为 可见每一个位置的地位都是相同的，限制条件只是改变某一个位置的值但是实际上最多只能改变 个位置，剩下的 个位置直接用快速幂算就好了于是记录这 个限制范围分别在哪一个数字上，由于位置的地位是相同的，不妨离散化一下注意需要去重，直接用一个set存就好了时间复杂度 Code #include<bits/stdc++.h> typedef long long ll; using namespace std;...

Description 一句话题意：给出一个数字序列 ，找出最长的序列 满足： Solution 这里给出一个 的做法,由于 , 可以通过本题。对于 先排序，这样可以满足 的要求。随后从小到大做质因数分解，不妨令 为当前质因子 所能构造的最长序列，那么当遍历到每个数字 时，都能使得它的质因子 成为 , 其中 为 的质因子。直观的感受就是从前面取结尾具有某个相同质因子的最长的一段添上当前的数字。实际上可以先筛出 里面的质因子，进一步优化复杂度，但是对于本题没必要。 Code #include<bits/stdc++.h> typedef long...

Description 一句话题意：每个网格点可以选择上下里面选一个方向，左右里面选一个方向，相邻的位于所选方向上的网格有 的贡献。 Solution 比赛时一眼就看出是 , 但是没有仔细思考细节。今天重新思考后发现其实不难。对于网格点，其实行列的贡献是相互独立的，即行与列的答案hubuy并且每一行，每一列的答案不相互影响。如果我们对行和列分开考虑的话，状态转移方程就很显然了。令 表示到第 行的时候选择了方向为上的最优贡献 表示到第 行的时候选择了方向为下的最优贡献 那么在遍历的时候其实考虑贡献只有来自上面的单位，即 行，于是 列的 也同理，所以对于每一列，每一行找...

Description Solution 前置知识: 差分不懂差分的同学可以百度先进行学习。学会差分能够 实现题目中的 相邻 个石子堆数目加 ，有助于我们进一步处理。首先思考，对于每一个石子数量，如果当前的数量不是 堆石头里面最大值 ，那么它一定要进行差分操作，差分到变成 但是考虑到这样后面的石头可能也会因此增加，所以 会不断改变，需要我们去维护。此外，考虑以下数据 一开始我们不会操作 , 但是由于后面 的改变，第一个 现在已经不是 ， 所以在从左到右做完一遍后，还需要在 里继续检查是否需要差分。至于什么时候输出 ? 如果 此时无法操作，肯定输出 了。此外，最后从头到尾检...