Chiaoliyu

题解

dp专题(1) 数据结构(1) 算法(2)

/ 注册

全部文章 / 题解（共9篇）

题解 | 2021秋季算法入门班第十一章习题：线段树、树状数组践踏

题意给我们3个操作，分别是新增一个区间，删除一个已有区间，以及查询目前有多少个区间包含点x+k∗tx+k*tx+k∗t，对于操作3，我最开始没有读懂，wa了几发，操作3的意思就是，t取任意整数，我以为其是定值。题解我们首先考虑k为0的情况怎么做，也就是查有多少个区间包含了点x，我们考虑什么样的...

树状数组线段树前缀和差分

2022-04-28

3 492

Codeforces Round #765 (Div. 2)

这场的难度梯度有点大，题面比较长，然后就可能大家花了很多时间读题，但其实cf的样例解释很详细，看不懂题面的话看看样例解释就懂了 A.Ancient Civilization 就是给我们n个数，给出一个上限l，要我们求一个数x使得∑1n\sum_{1}^{n}∑1n|aia_{i}ai - x|最...

二进制贪心 dp trie 抽屉原理 dfs序树状数组括号匹配

2022-01-14

1 851

牛客练习赛94

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中都要有奇数个，...

C++ bfs 贪心

2022-01-13

1 461

Codeforces Round #764 (Div. 3)

A.Plus One on the Subset 每次选择任意个数字，将其值+1，那么最少需要多少次可以让所有数字相等，显然我们不需要动最大的那个数，答案就是maxai−minaimaxa_{i} - mina_{i}maxai−minai B.Make AP 给出三个正整数a,b,c,我们能否...

C++ 哈希最小or生成树 dp 贪心

2022-01-12

1 646

牛客挑战赛55

牛客挑战赛55题解 A.铁三角这题playf哥哥在妄想集合这一题种讲过这个结论，就是斐波那契数列 B.DoubleSum 这一题一看肯定是要使用O(nlogn)的解法，那么我开始想歪了，事实上我们只需要对每个数枚举logn次，对于每一次枚举，统计在mod ckc^{k}ck意义下有多少个相同数即可...

C++ 贪心脑筋急转弯悬线法斐波那契数列

2021-12-23

0 687

牛客小白月赛42题解

牛客小白月赛42题解 A题冰狱寒岚仔细观察一下，会发现当x≤1023x\leq1023x≤1023时，直接输出这个数；当x>1023x\gt1023x>1023时，输出−1024+(n−1)-1024+\left(n-1\right)−1024+(n−1)%2048 我们解释一下...

C++ 数学广度优先搜索贪心二分查找思维

2021-12-21

0 535

题解 | 牛客练习赛91

A.神奇天平题意：给我们一个能同时确定x（x <= m)个物体中哪个最重，哪个物品最终或者同样重，那么给我们n个物品，问至少需要多少次能够确定最重的物品是哪个？题意：比赛的时候推了推没过，emmmmm,就很离谱，赛后几分钟想清楚了就A了，我好菜了根据样例我们可以得到将n个物品分成（m+...

C++ 可反悔贪心树状数组前缀和思维

2021-11-30

0 474

牛客练习赛92题解

A.D与数列题意：给定三个数N,A，B,让我们构造一个序列满足该序列的中位数是A,平均数是B,序列中的数可以重复题解：那么既然数是可以重复的，那么我们就可以输出先n-1个A 如果假设第n个数A,A<B,就给第n个数加上abs(n * (A - B))，如果A < B就给第n个数减去a...

C++ 拓扑排序贪心数学组合数学脑筋急转弯构造

2021-11-29

0 444

题解 | #魔法学院2hard#

想了很久，主席树，差分什么的，感觉根本行不通，这题其实感觉来源于洛谷P4145花神游历各国，我好惭愧，想到做法时已经写不完了。很容易想到的就是，我们把所有修改用结构体存起来，并按照字符从大到小排序，那么一个点如果最多只需要被最大的那个字符修改一次，我们可以，也就是说对于一次修改，我们只需要修改区间...

C++ 贪心

2021-11-12

3 504