题意：给一个计算所有长度为n的01序列的贡献和，每个序列的贡献为对数满足题解：我们来考虑第位为对答案产生的贡献。那么对于特定的序列，若就对答案产生贡献，那么的序列就会有个，而要使就有组，因此第位为对答案产生的贡献为因此答案为代码： #include<bits/stdc++.h> #define ll long long #define endl '\n' #define rep(i,l,r) for(int i=l;i<=r;i++) #define per(i,r,l) for(int i=r;i>=l;i--) const int MX=750008; const ...

题意：给定两个数组，求多少个不相交区间异或值为0；题解：两个区间异或为0，意思即可变为：两个区间各自异或相等，即若选了区间则满足^^^^那么我们只需要将要选的区间见视为左边选一个区间，右边选一个区间，各自区间内异或值相等即产生贡献，所以我们可以一边枚举左边的区间异或值，同时记录右边区间异或值的个数，然后看右边区间与枚举的异或值相等的有多少个区间，将他加到贡献中即可。具体看代码注释。时间复杂度 #include<bits/stdc++.h> #define ll long long #define endl '\n' #define rep(i,l,r) for(int i=l;i&...

对无序数组求中位数，是一个比较经典的问题了。有很多种办法求。这题是边添加边求中位数的。所以每插入一个数就sort一遍复杂度太高显然不行。还有一种利用大根堆小根堆，即平衡树来求，这种可以，这里不说。说另一种复杂度相当的，当常数教小的。利用树状数组来求第K小。建一个权值树状数组。例如有3,4,5,5,6四个数，那么即树状数组中存的是某个区间的权值出现的次数。由于这是一个32位无符号整型，范围过大必然使内存爆炸，所以需要离散化一下，先给原先的数组排一下序，就可以记录每个是是排在第几位，用这个排位来代替原值求，然后最后再转换回去。所以就可以边插入边求得第，显然前个数的中位数就更新到第个数时的第大了，因...

此题解与官方题解大概相差不大，甚至代码都大同小异？？？但也是个人理解，望能帮到你。为了方便描述，我们先来考虑最简单的树，如图，每个节点最多只有一个子节点。对于这个图我们要怎么染色使得最少呢？由于每个节点只能由自己染色或由其子节点染色来影响它变成黑色，故显然叶子节点必然要染色。即给8染上黑色。现在我们从下往上考虑，设表示从底下往上考虑到第i点时的最少染色数（且保证同染色数最优），最优即越往上影响越多即越优。现在，，且对8进行染色。这时候都黑了。现在，到了节点 ,查看一下，已经被染了，所以此时,且都黑了现在，到了节点,查看一下，没有被染，此时就必须多染一个点，（也许你想调整一下前面的染色？？但别忘...

A题题解：假定原先序列为则不改变序列的话，值为现在我们将移动到位置，会生什么呢，没受影响的有和,而都后移一位，即此时,而产生的贡献减少了即整体答案会变成,由于原序列非递减，所以有，即越大，答案越大，所以暴力一下每个数往前k个然后计算取最大即可。 #include<bits/stdc++.h> #define ll long long #define endl '\n' #define rep(i,l,r) for(int i=l;i<=r;i++) #define per(i,r,l) for(int i=r;i>=l;i--) const int MX=5e5+7; ...

我觉得超详细了？？？题解：我们先来考虑一下什么情况下，答案会为0。(1),你都比m大了还加个鬼啊(2)，因为包含的区间的起点最多只能包含各一次(3),因为包含的区间结束位置最多只能为各一次。(4),因为包含的区间若有个，必然至少有个区间包含，包含的区间同理--除了以上4种情况外，接下来来解决其他情况。直接上。 表示前个数加到的方案数，但这里需要修改一下区间加的合法性，把原先的对于任意两次区间加的起始，结束位置各不相同修改为对于任意区间的起始位置各不相同，除了以i结尾外，结束位置各不相同换句话说，就是允许多个以结尾的区间。显然遍历到时，以结尾的区间有个,如果我们先判断一下若则原题的答案变为0了，...

题解： 菜鸟讲解版 很明显的数论分块。等等，什么是数论分块？？？懂数论分块的直接跳过以下一部分。以下所有分式除法均为整除。----------分割线数论分块，顾名思义，将一段连续的区间分成一块一块相同的区间。简单点，将[1,n]这段区间来分块，分成，,,。k个块。属于同一个块之间的元素满足。好了，我们已经知道数论分块分成什么块了。接下来是怎么分？显然，如果则有。所以块中元素依然连续，相当于在原先的数轴[1,n]剪成k个块。那么想要怎么分就等价于怎么确定一个块的两个端点了。显然第一个块的左端点是,因为我们只考虑区间,那么如果确定了左端点（设为)后，右端点(设为)怎么确定呢？答案是,令证明：,即又...

仅对官方题解一个比较（通俗??)的理解题解：当时有解证明：显然，求得序列中中，若给其从小到大排个序，那么前个数必然是相同的,则有那么如果对于给定的有解的话，必然使得 有解，其实就是把（）这组合法序列的替换成就是新的合法序列了。那么可以递归下去，都是合法序列。显然 &&时无解，所以递减到最后只能是;即有 解得,即得证。构造办法,从上述可知，，那么构造办法就可以为第一个为,接下来x个0，接下来x-1个为1，x-1个为2...代码 #include<bits/stdc++.h> #define ll long long #define endl '\n' #define ...