WA_TLE

题解

/ 注册

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

华华给月月准备礼物来源牛客小白月赛12

题解：我们要的是找最大的长度，使得所有木棍能截成最少根长度为的木棍。第根木棍最多显然能截成长度为的木棍,为第根木棍的原始长度。因为若，所以能截成的数量是随着木棍长度单调递增而递减的，所以可以采用二分，二分木棍的长度，然后求满足最少根的最大值 #include<bits/stdc++.h>...

2020-04-16

1 612

逆序对来源 Wannafly挑战赛6

题意：给一个计算所有长度为n的01序列的贡献和，每个序列的贡献为对数满足题解：我们来考虑第位为对答案产生的贡献。那么对于特定的序列，若就对答案产生贡献，那么的序列就会有个，而要使就有组，因此第位为对答案产生的贡献为因此答案为代码： #include<bits/stdc++.h> #def...

2020-04-16

1 813

每日一题Xorto

题意：给定两个数组，求多少个不相交区间异或值为0；题解：两个区间异或为0，意思即可变为：两个区间各自异或相等，即若选了区间则满足^^^^那么我们只需要将要选的区间见视为左边选一个区间，右边选一个区间，各自区间内异或值相等即产生贡献，所以我们可以一边枚举左边的区间异或值，同时记录右边区间异或值的个数，...

2020-04-13

1 644

Running Median

对无序数组求中位数，是一个比较经典的问题了。有很多种办法求。这题是边添加边求中位数的。所以每插入一个数就sort一遍复杂度太高显然不行。还有一种利用大根堆小根堆，即平衡树来求，这种可以，这里不说。说另一种复杂度相当的，当常数教小的。利用树状数组来求第K小。建一个权值树状数组。例如有3,4,5,5,6...

2020-04-08

3 771

黑白树

此题解与官方题解大概相差不大，甚至代码都大同小异？？？但也是个人理解，望能帮到你。为了方便描述，我们先来考虑最简单的树，如图，每个节点最多只有一个子节点。对于这个图我们要怎么染色使得最少呢？由于每个节点只能由自己染色或由其子节点染色来影响它变成黑色，故显然叶子节点必然要染色。即给8染上黑色。现在我们...

2020-04-08

2 1168

牛客算法周周练1

A题题解：假定原先序列为则不改变序列的话，值为现在我们将移动到位置，会生什么呢，没受影响的有和,而都后移一位，即此时,而产生的贡献减少了即整体答案会变成,由于原序列非递减，所以有，即越大，答案越大，所以暴力一下每个数往前k个然后计算取最大即可。 #include<bits/stdc++.h&g...

2020-04-07

3 678

牛客OI周赛15-普及组-C-区间加

我觉得超详细了？？？题解：我们先来考虑一下什么情况下，答案会为0。(1),你都比m大了还加个鬼啊(2)，因为包含的区间的起点最多只能包含各一次(3),因为包含的区间结束位置最多只能为各一次。(4),因为包含的区间若有个，必然至少有个区间包含，包含的区间同理--除了以上4种情况外，接下来来解决其他情况...

2020-04-06

1 763

数码

题解：菜鸟讲解版很明显的数论分块。等等，什么是数论分块？？？懂数论分块的直接跳过以下一部分。以下所有分式除法均为整除。----------分割线数论分块，顾名思义，将一段连续的区间分成一块一块相同的区间。简单点，将[1,n]这段区间来分块，分成，,,。k个块。属于同一个块之间的元素满足。好了，我...

2020-04-05

21 1510

牛客OI周赛15-提高组B题

仅对官方题解一个比较（通俗??)的理解题解：当时有解证明：显然，求得序列中中，若给其从小到大排个序，那么前个数必然是相同的,则有那么如果对于给定的有解的话，必然使得有解，其实就是把（）这组合法序列的替换成就是新的合法序列了。那么可以递归下去，都是合法序列。显然 &&时无解，所以递减...

2020-04-05

5 642