zcmimi's blog

categories/刷题记录/共653篇文章

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

点击跳转

直接树剖即可

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

点击跳转

解法1:

贪心

把深度大于2的都加到堆中

每次取出深度最大的点

从根结点往它父亲连边

然后把周围的节点标记为已经覆盖

解法2:

树形dp

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

点击跳转

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

点击跳转

记忆化搜索

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

点击跳转

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

点击跳转

我们定义第x个数中从右往左数第i位的贡献:有多少个在x之前的数j满足a_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_x的第i位是1.

f[x][i]表示第x个数第i位的贡献,a[x][i]表示第x个数第i位是多少。

a[x][i]=0,取j=x不会产生贡献。若j < x,aj \bigoplus a_{j+1} \bigoplus ... \bigoplus a_x=a_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_{x-1}。所以f[x][i]=f[x-1][i].

a[x][i]=1,取j=x产生1的贡献。若j小于x,aj \bigoplus a_{j+1} \bigoplus ... \bigoplus a_xa_j \bigoplus a_{j+1} \bigoplus ... \bigoplus a_{x-1}相反。所以f[x][i]=(x-1-f[x-1][i])(j小于x的贡献)+1(j=x的贡献)=x-f[x-1][i].

f[x]=f[x][0]×1+f[x][1]×2+f[x][2]×4+...+f[x][31]×2^{31}.

则答案就是f[1]+f[2]+...+f[n].

可以用滚动数组

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

点击跳转

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

点击跳转

两点之间距离为MAX(|x-x'|,|y-y'|)

这种距离好像叫做切比雪夫距离

套路:

将一个点 \color{Blue}{(x,y)(x,y)} 的坐标变为 \color{Blue}{(x+y,x-y)(x+y,x−y)}后,原坐标系中的曼哈顿距离 = 新坐标系中的切比雪夫距离

那么: 将一个点 \color{Blue}{(x,y)(x,y)} 的坐标变为 \color{Blue}{(\frac{x+y}{2},\frac{x-y}{2})}后,原坐标系中的切比雪夫距离 = 新坐标系中的曼哈顿距离!

假设当前所有松鼠来x

\Delta X(a,b) = |a_x - b_x| , \Delta Y(a,b) = |a_y-b_y|

$$ ans =\sum{i=1}^n d(i,x) \\ = \sum{i=1}^n\Delta X(i,x) + \sum_{i=1}^n \Delta Y(i,x)

$$

假定x,和y都是有序的。

那是不是可以用前缀和呢?

lowerbound一下,前后反过来就可以了

最后:记得加 \color{red}{long\ long} !

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

点击跳转

GCD-Extreme top: 0

g(n) = \sum_{i=1}^{n-1} \gcd(i,n)

$$

\sum{i=1}^{n-1} \sum{j=i+1}^n \gcd(i,j)

\\

= \sum_{i=1}^n g(i)

$$

$$

g(n) = \sum_{i=1}^{n-1} \gcd(i,n)

\\

= \sum{d|n}d \sum{i=1}^{n-1}[gcd(i,n)=d]

\\

= \sum{d|n}d \sum{i=1}^{\frac nd - 1}[gcd(i,n)=1]

\\

= \sum_{d|n}d \times \varphi(\frac nd);

$$

求出g的前缀和

可以用筛的方式求g

O(n \sqrt n + T);

不能用之前的套路,否则会tle

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

点击跳转

f_i表示前i块土地

f_i=\min_{j=1}^{i-1}(f_j+maxw[j-1][i]\times maxh[j-1][i])

这样的话怎么想都没有办法优化

我们发现,如果一块土地被另一块土地所包含(即长和宽都比另一块土地小),

那么只需购买那另一块土地即可,于是我们可以据此筛掉其他的土地,

只剩下一些长度递减,宽度递增的土地

那么:

f_i=\min_{j=1}^{i-1}(f_j+l[j+1]\times w[i])

设任意0\le j<k<i,若从j转移比从k转移优,那么

f_j+l[j+1]\times w[i]\le f_k+l[k+1]\times w[i] \\ w[i](l[j+1]-l[k+1])\le f_k-f_j \\ w[i]\le \frac{f_k-f_j}{l[j+1]-l[k+1]}

维护一个下凸壳就完事了

47/66
Search
search