monkeycpp - 个人主页动态 - 牛客网

发布(24) 评论刷题

2020-06-01 12:02

清华大学算法工程师

[每日一题] [NC15748] 旅游

https://ac.nowcoder.com/acm/problem/15748 题目大意：给定一个树，每天选择一个点访问，每次访问的时候标记其邻居。要求每天不能访问标记过的点。最多可以访问多少天。 题意就是选择一个maximum independent set，对于树来说就比较简单用tree dp即可。就是考虑每个node选／不选的MIS，然后很容易用孩子表示根。最后返回root(s)选择的MIS。 注意会被卡常，也需要开fast IO. #define MAXN 500005 VI children[MAXN]; int visited[MAXN]; int unchosen[MAXN...

0 点赞评论收藏

分享

2020-05-27 12:35

清华大学算法工程师

[每日一题] [NC25043] Protecting the Flower

题目大意：有一些奶牛，每个奶牛有两个属性，一个是Ti，一个是Di。需要选择一个所有奶牛的排列，使得以下的值最小：每个奶牛被选中时，加上Ti和所有尚未被选中的Di的总和。例如T1=D1=D2=2,T2=3时，如果先选择1，该总和为T1D2=4，如果先选择2，该总和为T2D1=6，则12顺序优于21顺序。 https://ac.nowcoder.com/acm/problem/25043 分析相邻两个奶牛，用哪一个顺序更优：cow1: D1, T1cow2: D2, T2按照cow1,cow2的顺序，这两个奶牛的贡献为：2T1(D - D1) + 2T2(D - D1 - D2)= 2(T1+T2...

0 点赞评论收藏

分享

2020-05-26 14:27

清华大学算法工程师

[每日一题] [NC21228] 货币系统

题目大意：给定n个数字[A1,...,An]，用他们的非负倍数线性组合能生成的集合S[A1,...,An]最少可以由多少个数字生成。比如S[2, 4] = S[2]，只需要一个数字。S[3,5]至少需要两个数字。 https://ac.nowcoder.com/acm/problem/21228 首先猜想需要的个数，就是n减去可以被其他数字表示的数字。一方面，去掉这些数字后，这些数字都可以再被表示出来；另一方面，不是很好证明，但是直觉上是正确的。那么就是需要能知道哪些数字可以被表示出来。当作一个无限背包问题即可。 #define MAXA 25005 int dp[MAXA]; int do...

0 点赞评论收藏

分享

2020-05-22 15:48

清华大学算法工程师

[每日一题] [NC14414] 小AA的数列

题目大意：给定一个int数组，求所有长度为偶数的连续区间，且长度在[L,R]区间内，xor的总和。 https://ac.nowcoder.com/acm/problem/14414 很明显，可以不妨只对一个数位进行计算。如果我们知道倒数第五位，xor在这一位为1的符合要求的区间个数为10，那么我们知道倒数第五位xor对于总和的贡献是10*(1<<4)=160，等等。 对于一个数位，问题变成了，给定一个binary array，有多少个长度为偶数，在[L, R]区间内，且有奇数个1的区间个数。显然可以拆分成(0, R]和(0, L-1]的差简化问题。于是问题化为了，给定一个0/1数...

0 点赞评论收藏

分享

2020-05-21 14:05

清华大学算法工程师

[每日一题] NC19913 [CQOI2009]中位数图

题目大意：给定1,2,...,n的排列，和一个pivot number，求多少个长度为奇数的连续自序列的中位数恰好为这个pivot number。 https://ac.nowcoder.com/acm/problem/19913 因为没给数据范围，首先测了一下OJ，发现O(n^3) TLE，O(n^2) WA。所以先思考quadratic solution，并不困难，就是能否用amortized O(1)更新每个区间是否符合要求，那么判断是否中位数为pivot number只需要能维护大于该数、小于该数、等于该数的count。对于每个左端点L，遍历右端点即可，当然要忽略掉长度为偶数的情况。 ...

0 点赞评论收藏

分享

2018-08-19 02:22

清华大学算法工程师

SQL面经汇总

汇总了一下面试中会出现的SQL题，希望对大家针对性准备算法岗／数据分析／BA面试有帮助。 目前的打算是还要写一个假设检验的汇总和机器学习的汇总。 之前写的概率论汇总: https://www.nowcoder.com/discuss/95737 另外欢迎大家讨论这些题和贡献自己遇到的题目。 推荐一个介绍SQL网站吧，是我和我同学找工作时经常看的：http://www.dscademy.com/languages/sql 餐馆菜单输出最贵的五道菜 https://www.nowcoder.com/discuss/94886 学校中有一个年级表，有两个核心字...

投递招商银行·招银网络科技等公司10个岗位 >

0 点赞评论收藏

分享

2018-08-18 21:18

清华大学算法工程师

概率论面经汇总

原帖地址: https://www.nowcoder.com/discuss/94581 之前的帖子说好要持续更新的，但是牛客网上似乎精华帖不太方便修改。我就暂时在这里更新。每个section新加了几道题，然后有一部分题加上了网上有的答案。 论坛里有不少面经，这里想集中总结一下概率论问题的那部分。大家可以集中准备这一块。 我把题目简单分了一下类，相似套路的题目都算作了一道，然后有一些题放了网上能找到的答案。 准备概率论的话分为复习知识点和刷题两个步骤，个人认为都非常重要。如果只掌握课本理论，那么遇到面试题还是非常有可能不会做。...

投递知乎等公司10个岗位 >

0 点赞评论收藏

分享

2018-08-16 03:56

已编辑

清华大学算法工程师

概率论面经汇总(持续更新)

论坛里有不少面经，这里想集中总结一下概率论问题的那部分。大家可以集中准备这一块。 我把题目简单分了一下类，相似套路的题目都算作了一道，然后有一些题放了网上能找到的答案。 准备概率论的话分为复习知识点和刷题两个步骤，个人认为都非常重要。如果只掌握课本理论，那么遇到面试题还是非常有可能不会做。推荐一门教科书https://www.amazon.com/First-Course-Probability-9th/dp/032179477X 刷题的话强烈推荐这个网站的概率论题库，里面的题目非常全，而且概率论的教程和题目会不断更新。http://www.dscademy.com/...

monkeycpp：我是楼主。精华不太方便更新，新开了一个帖子有时间会慢慢更新。https://www.nowcoder.com/discuss/95737。欢迎大家贡献题目。

投递美团等公司10个岗位 >

0 点赞评论收藏

分享

2018-08-15 17:35

已编辑

清华大学算法工程师

多家公司算法工程师面经

毕业季一直是在牛客网上刷题看面经，最终拿到了满意的offer，贡献一下自己的面试经验希望能帮助到大家 本人本硕统计，主投算法岗 百度 电话 线性回归的共线性，如何解决，为什么深度学习不强调 解释word2vec原理 情感分析可以怎么做 CNN padding的原理 N个数找出最大的K个 百度 onsite 检查一个树是BST Logistic回归损失函数的公式和含义 ...

十元里美：求这两道题要怎么做使得|x_1 - x*| + .. + |x_n - x*|最小的x* 最小化|x_1 - x*|^2 + … + |x_n - x*|^2

投递瓜子二手车等公司10个岗位 >

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务