Kick Start 2020 Round A 题解

这次的题挺简单的,可惜了当时没做,错过一次好机会

A.Allocation

有 $N$ 个房子,每个房子单价为 $a_i$ 你共有 $B$ 块钱,求最多可以买多少个房子

分析

贪心

每个房子的收益都是 1,因此如果有两个房子 $A,B$, 一定是买价格低的最好

code

B.Plates

$N$ 堆盘子,每堆有 $K$ 个, 每个盘子的收 …

阅读全文

Kickstart 2019 Round H

kickstart 2019 round H, 2019 年最后一场kickstart,被打回原型了

感觉还是应该莽一发小数据的… 前天已经接到了google的实习申请通知了,得抓紧时间刷题了,近期准备把 2018,2017都刷一遍

A H-index

easy, H,是递增的,因此有很多种解决方案

  1. 维护一个 $citation …

阅读全文

现代多核计算机体系结构简介

这篇博文简单介绍多核计算机体系结构的相关术语(e.g. SIMD,superscalar,hyper-thread…),现代计算机体系结构保罗万象,越来越复杂,这里仅仅是抽象层简介,不涉及具体实现。旨在简单介绍它的一些工作方式概念.(非专业人士,有错误欢迎指正)

希望这篇文章能够帮助理解以下概念:

单核

(**注** 未特别说 …

阅读全文

PageRank 算法简介

这篇文章总结 PageRank 相关内容

PageRank 在搜索引擎中用来对网页做特征评估(为网页重要性打分),Google当年就是靠它,拿到互联网时代的门票,进而成就今天的霸主地位。同时,这也是 技术+商业 变现的例子。这边博文就在这里简要总结PageRank算法,揭开它的神秘面纱。

intuition

pagerank的直观非常简单:

  1. 整 …

阅读全文

Dimension Reduction: PCA and SVD

这篇博文简要总结关于数据降维的另外两种方法,PCA与SVD。之前讲过用JL变换和随机投影的方式做降维,那种方式的出发点是从计算效率出发的,所以计算方式会更快同时也是数据透明(data-oblivious)的,也就是不关心数据的特点,而今天要讲的两种方式都关心数据的特点。同时这里给出了一些PCA的相关直观性解释

PCA

首先我们说降维的目标始终都是用一 …

阅读全文

Kick Start 2019 Round G

人生第一次 AK!

这次的题目似乎比以前要简单一些

A. Book Reading

这题是说,有 $N\le 1e5$ 页书,有 $M$ 页是坏的,有 $Q$ 个人分别从 $q_i\le N$ 开始读,只读 $q_i$ 的倍数,坏的不读, 求共读了多少页

题解

直接暴力就行了,类似埃筛(complexity $O(n\log n)$))注 …

阅读全文

Kick Start 2019 Round F

F round 题解

A.Flattening

这轮,这个A还是有点难,好多选手都挂了…

$O(N^3)$ 版本

  1. 计算 $num[i][j], interval[i,…,j]$ 仅存在一块时需要改变的元素数目
  2. $dp[i][k]$ 使得前 $i$ 块的石头中,$\# A_x \ne A_{x+1}\le k$ 需要 …

阅读全文

找相似元素: LSH 局部敏感性hash

这篇博文简单总结一下局部敏感性hash(locality-sensetive-hash,LSH) 在找相似元素中的应用,这也是最近邻的另外一种解决方案

LSH 的直觉非常简单,设想一下我们判断一个集合 $set$ 中是否存在一个元素 $e$ 的方法,通常是将集合中的所有元素hash到一个一个的桶中,同时将 $e$ hash到桶中,如果存在, …

阅读全文