面试算法题*2

题目描述

背景 $k$ 聚类,可能和实际题目有出入。。。

T1

二维平面上有一个中心点 $p_{0}$ ,你可以在上面添加一些点,但对于任意添加的两点 $p_{i},p_{j}$,需满足 $dis(p_{i},p_{0}) < dis(p_{i},p_{j})$ 且 $dis(p_{j},p_{0}) < dis(p_{i},p_{j})$

T2

二维平面上有 $n+m$ 个两两不同的点,其中 $n$ 个点我们称其为待分类点,其余的 $m$ 个点称为中心点(分类的中心点),将一个待分类点分给中心点的代价为两点的距离。

现在给定这 $n+m$ 个点,并且第 $i$ 个分类只能容纳 $[l_{i},r_{i}]$ 个点,请你设计一种算法求出最小总代价最小。

My solution for T1

猜了一个等分圆,列个柿子:$\frac{2\pir}{n} > r$ 解出 $n$ 最多 $6$。

My solution for T2

答了个上下界费用流,建图类似二分图带权匹配。

2020杭电多校

打星为 upsolve

Round 1

rank 524 (1/12)

棒子,我x你仙人.jpg

阅读更多

2020牛客多校

打星为 upsolve

Round 1

好多论文题。。自闭

rank 99 (3/10)

阅读更多

回滚莫队

介绍

在一些用莫队处理的问题中,扩展区间容易但收缩区间不好处理,这时可以考虑使用回滚莫队的技巧,以达到区间只增不减的效果。

阅读更多

2020校队预选赛A-字符矩阵-题解

关于本次比赛

首先道个歉,卡掉了时空复杂度为 $n^3$ 的 $dp$ 做法确实是不应该,零基础的话能自学到掌握基本 $dp$ 的程度应该是很优秀的水平了。

而本次组题问题也很多,包括没有一个总的命题人来把握整体难度 和 “祖安” 一题出现意料外的解法(正则表达式)等。再次对我们命题工作的不当导致大家不好的比赛体验道个歉。

但每个题所涉及的知识点多为算法竞赛中实用的算法或技巧,数据也经过多次验证,欢迎大家赛后补题。

阅读更多

kruskal重构树

Kruskal重构树

资料

Kruskal重构树入门 自为风月马前卒

模板

构建方法:初始时有 $n$ 个叶子节点,运行 $kruskal$ 最小生成树算法,对于用边权为 $w$ 连接两个节点 $(u,v)$, 新建一个权值为 $w$ 的节点 $x$,并连边 $(x,root(u))$ 和 $(x,root(v))$, 并将 $x$ 置为这颗树的根节点。

这样建出来的其实是一个大根堆,可以用来求从点 $x$ 出发只走边权 $<=w$ 的边能到达的点的极大集合

做法就是从 $x$ 倍增往上面跳直到点权 $>w$,设跳到的点为 $u$,那么 $u$ 的所有叶子就是所求的极大集合

还有一个性质是:任意两个点路径上边权的最大值为它们的LCA的点权

阅读更多