题意 给我们3个操作，分别是新增一个区间，删除一个已有区间，以及查询目前有多少个区间包含点x+k∗tx+k*tx+k∗t，对于操作3，我最开始没有读懂，wa了几发，操作3的意思就是，t取任意整数，我以为其是定值。 题解 我们首先考虑k为0的情况怎么做，也就是查有多少个区间包含了点x，我们考虑什么样的区间不会对答案产生贡献，也就是右端点小于点x的区间和左端点大于点x的区间，那么我们离散化之后，利用树状数组维护差分前缀和即可，对于操作1，add(L, 1),add(R+1,-1),操作二add(L,-1),add(R+1,1),操作3，query(x)即可 我们考虑k不为0的情况，我们需要查询所有...

这场的难度梯度有点大，题面比较长，然后就可能大家花了很多时间读题，但其实cf的样例解释很详细，看不懂题面的话看看样例解释就懂了 A.Ancient Civilization 就是给我们n个数，给出一个上限l，要我们求一个数x使得∑1n\sum_{1}^{n}∑1n​|aia_{i}ai​ - x|最小，并且x ≤2l−1\leq 2^{l} - 1≤2l−1, 那么做法就很显然嘛，对于这n个数，遍历所有的二进制位，如果对于第i位，n个数中1的数量多于0的数量，x中这一位为1，就是这样，至于上界，是肯定不会超过的 B.Elementary Particles 就是给我们n个数字，要求我们找出两个...

Nhk R1 A」Initiale Dorimu 首先我们从a xor b xor c = 0入手，如果我们令a xor b = c,那么就会很容易的得到a xor b xor c = 0, 那么我们要如何满足a or b or c = d呢？也就是说d中为1的二进制位，a,b,c中都要有奇数个，那么我们就只需要将d拆开，让a中包含一部分为1的二进制位，b中包含另一部分为1的进制位，就是说b中每个为1的二进制位a,b中都会有一个恰好为1，那么就会满足a or b = d,那么怎么拆呢，用lowbit去掉最低一位1就行了 也就是a = n & -n, b = n - a, c = a ...

A.Plus One on the Subset 每次选择任意个数字，将其值+1，那么最少需要多少次可以让所有数字相等，显然我们不需要动最大的那个数，答案就是maxai−minaimaxa_{i} - mina_{i}maxai​−minai​ B.Make AP 给出三个正整数a,b,c,我们能否在不改变a,b,c的顺序的前通下，将其中某个数乘上一个正整数，使得这三个数构成等差数列？ 那么只需要改变其中一个数，我们分3种情况讨论就行了，假如改变a，那么c - b即为公差，由此得到等差数列中的a‘a^{`}a‘,看a能否得到它就可以了 C.Division by Two and Permuta...

牛客挑战赛55题解 A.铁三角 这题playf哥哥在妄想集合这一题种讲过这个结论，就是斐波那契数列 B.DoubleSum 这一题一看肯定是要使用O(nlogn)的解法，那么我开始想歪了，事实上我们只需要对每个数枚举logn次，对于每一次枚举，统计在mod ckc^{k}ck意义下有多少个相同数即可。 对于一个aia_{i}ai​和aja_{j}aj​，题目要我们求出最大的k使得两个数在mod ckc^{k}ck的意义下同余，我们可以将题意转换成求解在对于k(0≤k且ck≤1e90 \leq k 且 c^{k} \leq 1e90≤k且ck≤1e9)，有多少个k满足ai,aj在modcka_{...

题目链接：https://www.acwing.com/problem/content/841/ map + priority_queue实现可以修改任意插入位置的堆 个人感觉手写堆除了提升一下自己码力，就没有啥用处了 在大多数情况下，我们只需要使用STL中的priority_queue即可，万不得已也可以手写左偏树 那么要修改任意位置，我自己瞎搞了一个优先级队列+map的方法，AC了本题，就是不知道有没有问题 希望各位小佬爷们帮忙康康 //ink代表第k个插入的是谁 //knum代表值为x的数有多少个 1.插入第cnt个数x, 常规操作聪明的你一定能看懂 ink[++cnt] =...

声明：题意就不细说了，我这功底说的也语句不通，尽量写好题解，大家由疑问可以私信我，我会及时回复的，此篇题解是作者在看了网上众多题解之后，自己的一些感受。 A. Alice and Bob 说实话，这题比赛的时候是真的不会，和队友讨论了一下，感觉就情况很多，然后很复杂 思路 题目中给出了一些必败态，那么由此可知，每一个必败态（x,y)，那么由此推出的（x + k, y + s * k), (x + s * k, y + k)就一定是必胜态。 由此我们使用dp[x][y[来表示状态, dp[x][y] = 1, 先手胜，dp[x][y] = 0, 后手胜 那么我们对于每一个后手胜的状态，枚...

AtCoder中的一些dp好题 1. AtCoder Beginner Contest 210 D - National Railway 题意： 有一个n*m的阵列，每个点有一个值a[i][j], 我们需要在这个阵列中找到两个不同的点，连接他们的花费为 a[x1][y1] + a[x2][y2] + （|x1 - x2| + |y1 - y2|) * c, 要求最小的花费是多少？(n <= 1000, m <= 1000) 思路： 暴力的想法就是把任意两个点拿出来匹配，但是显然是会超时的，这题可以对每一个点进行bfs, 每次向 四周扩展，然后貌似没有优化方法，...

A.D与数列 题意：给定三个数N,A，B,让我们构造一个序列满足该序列的中位数是A,平均数是B,序列中的数可以重复 题解：那么既然数是可以重复的，那么我们就可以输出先n-1个A 如果假设第n个数A,A<B,就给第n个数加上abs(n * (A - B))，如果A < B就给第n个数减去abs(n*(A - B)),就可以了 但是我比赛的时候写了一个很***的做法，使得n个数是不一样的，就很浪费时间 B.D与集合 题意：给定一个序列 a 1 . . . a n a_{1}...a_{n} a1​...an​，并给定一个数k,要求要这n个数分成k个集合，使每个集合的和都是非负数...

牛客小白月赛42题解 A题 冰狱寒岚 仔细观察一下，会发现 当x≤1023x\leq1023x≤1023时，直接输出这个数； 当x>1023x\gt1023x>1023时，输出−1024+(n−1)-1024+\left(n-1\right)−1024+(n−1)%2048 我们解释一下第二部分吧，可以发现就是将当数x>=1024x>=1024x>=1024时，从-1024开始计数，那么也就是说将一个数减去1024后映射到-1024~1023，我们考虑将x映射到0到2047，也就是(x-1024)%2047，最后再减去1024就是-1024到1023了 #incl...

A.神奇天平 题意：给我们一个能同时确定x（x <= m)个物体中哪个最重，哪个物品最终或者同样重，那么给我们n个物品，问至少需要多少次能够确定最重的物品是哪个？ 题意： 比赛的时候推了推没过，emmmmm,就很离谱，赛后几分钟想清楚了就A了，我好菜了 根据样例我们可以得到将n个物品分成（m+1)堆比较优（让我自己想，怀疑自己想不到），也就是说将当前的n个物品尽可能平均的分成(m+1)堆,那么就按照每堆(n + m) / (m + 1)个进行分配，就可能会使得最后一堆的没有这么多个，那么没关系，那么此时将m堆数量为(n+m)/(m+1)的放到天平上称量，就可以知道重物在哪一堆中，剩下一堆...

A.D与数列 题意：给定三个数N,A，B,让我们构造一个序列满足该序列的中位数是A,平均数是B,序列中的数可以重复 题解：那么既然数是可以重复的，那么我们就可以输出先n-1个A 如果假设第n个数A,A<B,就给第n个数加上abs(n * (A - B))，如果A < B就给第n个数减去abs(n*(A - B)),就可以了 但是我比赛的时候写了一个很***的做法，使得n个数是不一样的，就很浪费时间 B.D与集合 题意：给定一个序列a1...ana_{1}...a_{n}a1​...an​，并给定一个数k,要求要这n个数分成k个集合，使每个集合的和都是非负数 题解：要求是非负数，如果...

想了很久，主席树，差分什么的，感觉根本行不通，这题其实感觉来源于洛谷P4145花神游历各国，我好惭愧，想到做法时已经写不完了。 很容易想到的就是，我们把所有修改用结构体存起来，并按照字符从大到小排序，那么一个点如果最多只需要被最大的那个字符修改一次，我们可以，也就是说对于一次修改，我们只需要修改区间[l, r]中没有被修改过的点就可以了，我们就可以用并查集来加速找没有被修改过的点这个过程，一个点被修改过，我们直接跳过去就行了 当i这个点没有被修改过时，fa[i] = i， 当i被修改过之后，令fa[i] = i + 1(当前点右边相邻点可能就是下一个需要修改点), 以(i+1)号点为起点，寻找...