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

点击跳转

题目大意:

给定一个长度为 n\leq 500000 的序列 a_1, a_2, \cdots, a_n ,要求对于每一个 1 \leq r \leq n ,找到最小的非负整数 f_{r} 满足

\forall l\in\left[1,n\right]:a_l \leq a_r + f_{r} - \sqrt{|r-l|}

解法

考虑l<r,r>l的将序列翻转后再来一次就可以了

f_r= \max(a_l+\sqrt{r-l})-a_r(l\in[1,r])

可以证明f_r的最优决策点是递增的

可以打表

分治解法

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

点击跳转

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

点击跳转

直接建立20棵线段树统计1,2,4,8,...,2^20就可以了

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
查看原题

点击跳转

dp

(其实记忆化搜索也可以啦)

只要假设组成n的数是递增或递减,就不会重复了

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

点击跳转

一个点在某个高度有水满足左边和右边在同一高度要么是水要么是石头

预处理出L_iR_i表示一个点左边和右边的限制

L_i = \max (\min(L_{i-1},s_i),p_i)

R_i同理

ans = \sum_{i=1}^n \min(L_i,R_i) - p_i

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

点击跳转

先把连续的块缩成一个点

f[i][j]表示[i,j]全部涂成一种颜色最少要多少次

f[i][j] = \min(f[i+1][j],f[i][j-1])+1

c[i]==c[j],f[i][j]=f[i+1][j-1]+1

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

点击跳转

我们可以看成n对石子堆的博弈论

那么我们把n对石子堆的SG值异或一下就可以了

那怎么求每对石子堆的SG值呢?

SG(x,y) = mex({SG(x',y')})(x'+y' = x 或 x'+y' = y)

打表之后可以发现:

每一对(i,j),直接求(i-1)\mid(j-1)二进制的最低的0所在的二进制位

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

点击跳转

f_i表示前i个拆分后最大战斗力和

f_i=\max_{j=1}^{i-1}(f_j+a(s_i-s_j)^2+b(s_i-s_j)+c)

这个很明显是斜率优化式子

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

f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\ge f_k+a(s_i-s_k)^2+b(s_i-s_k)+c \\ 2as_i\le\frac{(f_k+a{s_k}^2-bs_k)-(f_j+a{s_j}^2-bs_j)}{s_k-s_j}

维护个下凸壳就完事了

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

点击跳转

连续和相当于区间和,题目的意思是求所有S_i-S_j的异或和

一般位运算的题我们都拆成二进制下32位来解决

考虑每一位

枚举k

如何统计有多少个((S_i-S_j)>>k)\&1呢?

可以开两个权值树状数组来统计01的数量

如果当前S_i的第k位为1,如果S_j\&(1<<k) = 0S_i+S_j在二进制下进位不会影响到第k位的都符合条件

也就是S_j\&((1<<k)-1) \not = (S_i\&((1<<k)-1))

\&((1<<k)-1)也就是取前k

41/73
Search
search