zcmimi's blog

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

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

点击跳转

斜率优化入门题

f_i表示前i件玩具的制作费用

f_i=\min_{j=1}^{i-1}(f[j]+(i-j-1+s_i-s_j-L)^2)

显然\Theta(n^2)不能满足要求

a_i=s_i+i,b[i]=s_i+i+L+1

(都只与i有关)

那么 f_i=\min_{j=1}^{i-1}(f_j+(a_i-b_j)^2) \\\text{展开得}\\ f_i=f_j+{a_i}^2-2a_ib_j+{b_j}^2 \\\text{移项得}\\ 2a_ib_j+f_i-{a_i}^2=f_j+{b_j}^2

x=b_j,y=f_j+{b_j}^2 y=2a_ix+(f_i-{a_i}^2)

可以看成一条斜率为2a_i的直线

f_i含义转化为当上述直线经过点(x,y)(b_j,f_j+{b_j}^2)时,直线在y轴的截距上加上{a_i}^2

题目就是要找这个最小的截距

我们可以将这条直线从下往上平移,直到经过第一个点

这样的话我们可以维护一个下凸壳

求的过程大概是这样:

https://www.desmos.com/calculator/mqsdvzuaee

那么如何维护这样一个下凸壳呢?

可以发现凸壳中的相邻两点的斜率是递增的

我们可以用单调队列维护

那么查询呢?

我们可以发现:

如果当前直线经过的点左边的斜率<当前斜率<右边的斜率,

那么这个点就是最优的。

我们可以按照下面的方案实现:

设队头为h,队尾为t,队列数组为q,s(i,j)为直线ij的斜率

  1. while(s(q_h,q_{h+1})<2a_i)++h;
  2. 当前队头的点最优,用这个点计算出f_i
  3. while(s(q_{t-1},q_t)>s(q_{t-1},i))--t;
  4. 队尾插入点i

对于3操作的解释:

假设当前插入的是红点,那么绿点明显在凸包内,要删除掉

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

点击跳转

玄学的最短路优化

一看数据范围这么大,一定不能直接做

当你删掉某条边(u,u+1)时,最短路路线为:1->x(<=u)->y(>u)->n,并且x->y一定不会属于原最短路

就是最短路->其他边->最短路

ban:(禁用)

先把所有堵车的边ban掉,然后跑最短路

接着依次加边,跑最短路,就不用清空dis了

d(x,y)xy的最短距离

每个点的答案就是d(1,x)+d(x,n)

所以开一个堆,

枚举被ban的边

把答案和没被ban的边的编号扔进去就可以了

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

点击跳转

[l,r]之间最小值位置为p,原数组为a

那么左端点在[l,p],右端点在[p,r]的区间的最小值都是a[p]

那么这部分的贡献为a[p] \times (p-l+1) \times (r-p+1)

接下来还有[l,p-1],[p+1,r]没有处理

pre_ii前第一个比a[i]小的数的位置(用单调栈筛出)

存在x,满足pre_x=p

f[l][r]表示以r为右端点,左端点在[l,r]的区间的答案

那么f[l][r]=f[l][pre_r]+a_r\times(r-pre_r)

因为f的变化只与r有关,所以可以删掉一维

那么f_r= a_r \times (r-pre_r) +f_{pre_r}

所以[p+1,r]的答案就是f_r-f_{p-1}

[l,p-1]求法类似

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

点击跳转

前置定理:

d(ij) = \sum_{x|i} \sum_{y|j}[gcd(x,y) = 1]

所以:

n<m

\sum_{i=1}^n \sum_{j=1}^m d(ij) \\ =\sum_{i=1}^n \sum_{j=1}^m \sum_{x|i} \sum_{y|j}[gcd(x,y) = 1] \\ =\sum\limits_{x=1}^n\sum\limits_{y=1}^m \left\lfloor\frac{n}{x}\right\rfloor \left\lfloor\frac{m}{y}\right\rfloor [\gcd(x,y)=1]

x、y换成i、j

\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)=1] \\ =\sum\limits_{i=1}^n\sum\limits_{j=1}^m \left\lfloor\frac{n}{i}\right\rfloor \left\lfloor\frac{m}{j}\right\rfloor \sum_{k|gcd(i,j)}\mu(k)

g(i)=\sum_{i=1}^n \left \lfloor \frac ni \right \rfloor

ans=\sum_{k=1}^n\mu(k) g(\left \lfloor \frac nk \right \rfloor) g(\left \lfloor \frac mk \right \rfloor) \\

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

点击跳转

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

点击跳转

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

点击跳转

https://www.luogu.org/blog/CSGO/solution-p3413

直接肝不行,我们反着来

找不包含回文串的个数

一个数任何一位都与前两位不相同时,它就不包含回文串

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

点击跳转

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

点击跳转

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

点击跳转

设选区间[l,r],要穿x号的人数为f(x)

必须满足 \sum_{i=l}^{r}f(i) \le (r-l+1+d) \times k

\sum_{i=l}^{r}(f(i)-k) \le kd

那么用线段树维护全局最大子段和就可以了

46/65
Search
search