zcmimi's blog
avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

说实话,我觉得我是太傻吊了,一道动动脑筋就可以写的题我能写成麻烦的dp

dalao的代码:(直接扫描一遍就可以过了)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先按左端点排序,每次添加右端点的时候如果堆中个数等于k就统计答案,然后弹出最小的右端点

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

首先将数列按位分解成32个位数列.

枚举区间的左端点,,区间的and值要对答案有贡献必须为1,随着右端点右移,and值为不递增的,而区间的or值要对答案有贡献必须为1,随着右端点右移,or值为不递减的。

可以求出每一段一段的最大长度然后统计

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

\sum_{x=1}^n \sum_{y=1}^n [gcd(x,y)=1][a_{b_x}=b_{a_y}]

可以直接记录v[a_{b_x}]然后统计,用莫比乌斯容斥

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

直接求很难

突然看到二分的标签

那我们二分k的值,判断排名不就可以了

如何判断排名:

如果区间[l,r]满足要求,那么左端点换成[1,l-1]中的任何一个也都满足要求

那我们只要枚举右端点,然后用双指针法就可以了

求众数可以用莫队的思想

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

S_i[1,i]\ge w的数的个数

如果一个区间要满足中位数\ge w,那么\frac {S_r-S_{l-1}}{\frac {r-l+1}2} \ge w

化简一下:2S_r-r > 2S_{l-1}-(l-1)

那么二分w然后用树状数组统计之后判断排名是否\ge k就可以了

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

二分第k大平均数w,统计平均数大于等于它的区间的个数

这样的区间满足\frac {s_r - s_{l-1}}{r-l+1} \ge w

化简一下: s_r - s_{l-1} \ge w(r-(l-1)) \\\\ s_r - wr \ge s_{l-1} - w(l-1) 那么我们只要用树状数组统计一下就可以了(当然你要用权值线段树也可以)

因为平均数可能不是整数,所以我们要离散化一下才能统计

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

官方:

对于一段区间l~r,其中一个数x对答案的贡献为(2x-l-r)次。

因此我们只要求出所有数对答案的贡献并累加起来即可。

将2x-l-r分为两部分,一部分为求2x的和,即为x左边与x右边相同的数的对数。

另一部分为l+r,将其拆开来,并记录前缀和,对于一个数a[i],我们需要维护的是Σk,Σs[i-1],Σs[i-1]*i,以及a[i]出现的次数就可以了。

这里我们可以在枚举的同时,记录这些信息,并更新答案,就可以了。

复杂度为线性O(n)。

更加详细:

https://www.cnblogs.com/zkGaia/p/6108204.html

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

集合hash

  1. 两个点不认识

    两个点是相似关系说明他们的所有朋友都相同,可以把一个点的朋友当成集合hash一下,然后就可以统计了

  2. 两个点认识

    两个点是相似关系说明他们的所有朋友加上对方都相同,可以把一个点的朋友加上它自己当成集合hash一下,然后就可以统计了

42/74
Search
search