zcmimi's blog

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

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

点击跳转

可以参考线段树或分块维护区间加和区间减的思路

看一下数据范围,每次操作只能O(1)的复杂度。

点的位置可以离散化一下

记得先乘后加

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

点击跳转

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

点击跳转

p条直线分情况讨论平行线的条数,已知在有r条平行线时有p-r条线与他们相交于p\times(p-r)个交点,再加上对于这p-r个交点的相交组合即可!

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

点击跳转

\sum [lcm(i,j)=i\times j]

相当于求\sum_{i=1}^n \sum_{j=1} ^n[gcd(i,j) = 1]

时间限制:10.00s

1 \le n,m \le 10^9\min(n,m) \le 10^6

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

点击跳转

思路很妙

注意m-n \le 20

也就是说最多只有21条非树边

我们可以先跑一遍kruskal,然后按套路建树,两点之间的距离就是d_x+d_y-2\times lca(x,y)

接着剩下最多21条边(42个节点),再跑最多42次最短路就可以处理出加上非树边的结果了

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

点击跳转

我们可以考虑放n-k个节点然后使深度最大的最小

一开始的时候可以反过来想:树里面长度最大的路径就是树的直径,它的两个端点的度都是1(也就是叶子节点)

我们可以从每个叶子结点开始,向中心包围。可以用队列的方式实现。

(代码很短)

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

点击跳转

枚举哪些行和哪些列要变成回文

处理:

行:点(i,j)对应点(i,m-j+1)

列:点(i,j)对应点(n-i+1,j)

我们可以用并查集合并这些点

然后求每个块中0还是1多

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

点击跳转

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

点击跳转

D-query top: 0

就是莫队的板子题

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的最优决策点是递增的

可以打表

分治解法

38/66
Search
search