题意 小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的，当且仅当T中包含了所有的小写字母。小N希望知道所有的合法的S的子串中，长度最短是多少。 。 分析 对每个 ，我们要求最大的 ，使得 包含了所有小写字母。显然， 是单调递增的。于是我们开个桶记录一下每个字母出现了多少次，从左到右扫一遍即可。时间复杂度是 代码如下 #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; char s[N]; int cnt[255]; int main(){ i...

题意 有 个二元组 ，二元组可以翻转。现在要将这些二元组接成一个环。连接部分的漂亮度是 （ 时漂亮度为 ）。环的漂亮度为连接部分的最小漂亮度，现在要最大化漂亮度，并输出连接顺序。（第 个二元组的编号为 和 ）其中 。 分析 先考虑答案大于等于 时的性质：也就是任意一个连接处， 是 的倍数。因此答案具有单调性。考虑怎么检验答案。 和 能作为连接处，意味着 在模 意义下相同，也就是 。那么，能否连成一个环，其实等价于是否存在欧拉回路（这个可能需要思考一下）。判断欧拉回路存不存在很好判断。然后找到答案之后再求一边欧拉回路就可以了。复杂度 。 代码如下 #include <bi...

题意 有一个数组 ，每次你可以选择一个元素放到最后面或者最前面，求将 排成不递减序列的最少次数。 可能有重复元素。 。 分析 由于这些数只和大小关系有关，我们先离散化一波，将值域变为 。观察发现，每个数如果要移动，最多只会移动一次。那么，次数 = n - 不移动的数字个数。我们考虑最大化不用移动的数字个数。不用移动，意味着这些数在原数组中是有序的，而且值域上是连续的，而且每个数大于等于前一个数。那我们把原数组按双关键字排序，先按值域，再按下标。那么考虑我们选取的值域为 。那么 中的所有数都是必选的。 和 中的数可以部分选，最优情况肯定是选 的前缀和 的后缀，如图。其中，选的数必须...

前前言 很久之前学的了，但一直没有机会用到，就写个 防止忘记吧。 题意 求 。其中，， 不一定为质数。模板题在这里！ 前言 定理 和 定理一点关系都没有。。。。所以根本不需要你会 定理，不过你得会中国剩余定理QAQ好了下面进入正题！！ 主要思路 先将 分解质因数，变为 分别求出 用中国剩余定理合并 分析 现在的主要问题就是求 。但是 实在是太太太大了，让这一切非常难顶。为了让下面存在逆元，我们要把所有的 提出来。令 ，其中 ，也就是把所有 的次数都提出来。于是原式可以写成这种形式： 现在的问题就变成： 求出 求出 ，然后求波逆元就完事儿了 第一个问题很好求嘛，令 ...

题意 终于Alice走出了大魔王的陷阱，可是现在傻傻的她忘了带武器了，这可如何是好???这个时候，一个神秘老人走到她面前答应无偿给她武器，但老人有个条件，需要将所选武器分别放在天平的两端，若天平平衡则可以将天平上的所有武器拿走，还好这个天平锈迹斑斑，只要两端重量相差小于等于m就会保持平衡，Alice傻傻的认为越重的武器越好，求Alice最多能拿走的武器总重量。（不限操作次数）其中， 。 分析 这题还是比较简单滴。首先，容易发现，称多次和称一次没有区别，也就是称一次就可以得到最终的答案。假如你称两次，第一次为 ，第二次为 ，其中 ，那么我们完全可以变成称一次 ，使得最终答案不变。所以称多次最后都...

题意 有 个数，每个数取值范围为 。现在要在两两数之间插入 和 两种运算符，使得运算结果最大化，求最大化的结果。其中，。 分析 这里提供一种非主流做法。最终的形式肯定是一块块乘积相加的形式，于是我们考虑 。令 表示来到 时的最大值。那么 。其中， 指的是 这段区间每个数的乘积。由于 的取值只有 三种情况，我们分情况考虑： 乘积为 ，也就是这段区间中包含了至少 个 ，那这段区间一定包含了离 最近的 ，不妨记这个位置为 ，那么 乘积不为 ，那么决策点一定是在 中进行选择。如果 ，那么最优的方式肯定是从 转移过来，即 。如果 ，那么可以有两种转移方式：第一种是 。也就是直...

题意 组数据，有 种货币，每种货币有无限量，求最少的货币种类，使得所有种类的货币可以被表示。 。 分析 先将货币数值排序，如果 可以被前面的表示，那么 显然没用了。如果没被表示，就显然必须加入货币系统。怎么看能不能被表示呢？这不就是个背包吗=。=复杂度 代码如下 #include <bits/stdc++.h> #define N 105 using namespace std; typedef long long LL; LL z = 1; int read(){ int x, f = 1; char ch; while(ch = getchar...

题意 有 个任务，每个任务有个完成时间 和截止时间 。问最多能完成多少任务。 分析 这道题还是挺难的QAQ。首先看到这题，我们可以先将问题转化一下：假设最终做的任务序列为 ，那么对任意 需满足 ，也就是： ... 我们现在要让这个序列尽量长。然后有一个基础的想法：对于每个 ，我们要求满足上式的最长序列。然后对于同一个长度 ，肯定在合法的条件下，让 越小越好，因为这样能多出更多时间。然后考虑暴力，我们可以对维护一个 的 ，每个 储存合法的长度和最小的前缀和。每次枚举到一个 ，更新所有合法的长度及其对应的最小前缀和（从 更新到 ）。这样复杂度是 的。要继续往下做，我们要发现： 和...

题意 小AA找到了一个数列，她想要知道这个数列中所有长度为偶数的区间异或和之和 。后来她发现这个问题太简单了，于是她加了一个限制，要求区间长度在[L,R]之间，然后她就不会了。。。请你告诉她问题的答案。其中，。 分析 和位运算有关的题统统按位考虑=。=，于是我们枚举二进制的每一位。问题转化为：有 个数，每个数为 或 ，求偶数长度且长度在 且区间和为奇数的区间数量。（真tm绕）如果区间和为奇数，意味着 。于是我们只关心前缀和的奇偶性。这样子问题又转化另一个问题：求 中与 不同的数的个数。这个可以用一个前缀和快速求出。然后由于区间长度为偶数，我们要对奇偶分别开一个数组记录前缀和。。细节还...

题意 给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。其中，。 后言 看了别人的写法才知道我的写法有多s,b。大家就当看个乐吧TAT 后后言 我靠！原来题目中的数组是 的排列！！！！以下做法适用于任何数组！！！ 可以不止有一个！ 分析 直接求中位数是 的区间有多少不好求，我们考虑求中位数大于等于 的区间数 - 中位数大于等于 的区间数，类似一个差分的思想。（当然也可以用中位数小于等于 的区间数 - 中位数小于等于 的区间数）这样子，我们就把问题转化成一个比较套路的题了，即是求中位数大于等于 的奇数长区间...

题意 小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题： 无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍历整个图。其中, 分析 首先假设这个图是个连通图。那么如果这个图有一个奇数大小的环，这个图的所有点一定可以被访问到。（因为可以在环上进行调整）如果这个图不是连通图，那我们要先加边使它连通，那么原来如果有一个连通块满足全部点可以访问到，整个图一定都可以访问到。所以我们现在就把问题转化为：求图上是否有一...

题意 有一颗 个节点的树，以 为根节点，每个点有一个颜色 。设子树 中颜色出现次数最多的颜色集合为 ，记 。现在要求 。其中，。 分析 这种题叫做 ，也就是树上启发式合并。让我们先考虑暴力做法。就是以每个节点，对子树进行 ，然后开一个桶记录颜色出现次数，最后把颜色出现次数最多的颜色加起来。这样子做复杂度是 的。这复杂度显然是不可接受的嘛！暴力差就差在，它计算了很多重复的东西！如果我们能让重复的东西尽量减少计算，复杂度就能够得到提升了！ 看到这道题，有的同学可能一下子想的是树上莫队。确实，莫队算法就是用来优化这些有重复计算的东西的。不过，更优秀的算法是用启发式合并，复杂度可以做到 。...

题意 有一颗 个节点的树，每个点有权值 ， 这条边的权值为 。有 次操作： 将节点 的值改为 询问 到 的路径上有多少条边边权不超过 其中，，。 分析 首先看到这题时限 ，果断上 O(1)gcd + 暴力，复杂度 ，结果没卡过去。。。不过为什么其他人的 做法都能过啊，我的就不能过QAQ下面的解法学习自 CYJian大佬的博客。Orz先以 为根节点，进行树链剖分。（如果你不会树剖，可以先去看看 这道模板题然后每次修改节点 的值，先只对重链上的边进行修改。这样子就保证了重链上的边都是正确值。然后在跳链时，再更新重链之间的连接边（轻链）的边权即可。修改边权 + 查询不超过...

题意 阿狸喜欢收藏各种稀奇古怪的东西，最近他淘到一台老式的打字机。打字机上只有28个按键，分别印有26个小写英文字母和'B'、'P'两个字母。 经阿狸研究发现，这个打字机是这样工作的： 输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。 按一下印有'B'的按键，打字机凹槽中最后一个字母会消失。 按一下印有'P'的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。 例如，阿狸输入aPaPBbP，纸上被打印的字符如下： a aa ab 我们把纸上打印出来的字符串从1开始顺序编号，一直到n。打字机有一个非常有趣的功能，在打字机中暗藏一个带...