特色文章

BZOJ上的USACO 第一弹

听说刷BZOJ上的USACO题目比较涨rank,于是我也开始了开心的划水生活~在这里贴一些题目的代码和思路,如果感觉比较好的题目用★标注出来,也会单独写写。

现在做了几题:

50/50

终于填完了,写题写的好慢啊QAQ。再弄个第二弹。

继续阅读

特色文章

Codeforces题目泛做计划

找了一些比较水的cf上的题目,然而又不想整套整套的的写了,于是一些散的cf上的题目就放在这里了。

现在做了几题:

30

好弱啊、、

继续阅读

计蒜之道2018初赛做题记录

最近又开始了计蒜之道,目前进行到了前两场,两场都打了:第一场是自己打,第二场帮考试中的队友打的。第一场题目不算太坑一个小时做完前三个不想写hard就可以晋级了。。。第二场题目有些坑点实在难以注意到结果半个小时写完前两个easy就晋级了。。。写了一整场的medium。。。想到博客已经n年没有更新了,最近考试周也过去了,就把题目补补(如果会的话),写到这里算了,毕竟月底蓝桥杯还是要咸鱼冲锋一下的。。剩下的几场因为没有号了,可能就随便打打了。。。

第一场

A. 百度无人车

二分答案没啥好说的。。

B. 百度科学家(简单)

这道题我比赛的时候写了两个版本简单和中等,困难当时也看出来要写可持久化线段树优化建图,但是老年人写不动就算了。
简单版本直接枚举的起点然后bfs的。。。不贴代码了。

C. 百度科学家(中等)

发现加的总边数不会超过1e5就很好办了。先Tarjan缩点成dag后重新建图,然后因为权值非负贪心选择出度为0的点中价值最小的即可。

D. 百度科学家(困难)

待补。

第二场

A. 淘宝的推荐系统

直接dp[i]表示到当前元素为止价值为i的合法序列长度,然后就是O(nd)的dp了。。。

B. 阿里巴巴的手机代理商(简单)

没有update不贴代码了。。

C. 阿里巴巴的手机代理商(中等)

这个题细节贼鸡儿多。。。就说一个地方吧,因为我是错在这里了,就是你update需要先删除然后断掉子树,然后插入在连接。具体看代码吧,至于为什么,考虑你把一个老的单词换成一个新的单词且老的是新的前缀的情况,所以这个顺序不能乱。

D. 阿里巴巴的手机代理商(困难)

待补。。写不动了啊。。

Project Euler 211 Divisor Square Sum(约数平方和)

For a positive integer n, let σ2(n) be the sum of the squares of its divisors. For example,

σ2(10) = 1 + 4 + 25 + 100 = 130.
Find the sum of all n, 0 < n < 64,000,000 such that σ2(n) is a perfect square.

简单写写了,早上问了一下大爷们约数平方和有什么好的性质么?答:积性函数啊!哦,那我只要线性筛一遍一个个验证答案好了。。。
然后发现自己原来没怎么学过线性筛啊。。。


如果x=p1^a1*p2^a2*….pk^ak,


那么约数平方和为(1+p1^2+p1^4+…+p1^(2*a1))(1+p2^2+p2^4+…p2^(2*a2))*…*(1+pk^2+pk^4+…+pk^(2*ak))。
那么为了保证线性筛的复杂度,我们需要存一个每个数的最小素因子(也就是p1)的括号里的东西就可以做了。。。
直接看代码好了~
注意爆int。。。
哦对了这个函数貌似叫做除数函数,表示约数的次幂和。

51nod 1461 稳定桌 & codeforces 577C. Arthur and Table(贪心+权值线段树)

题面自己看吧。。。面试JD的时候居然问了个这个题(你敢信?),但是码力有限差一点就调出来就被面试官小姐姐打断了,被吐槽写得太慢了QAQ。。。吓哭了。。。估计多半是凉了。
就是枚举每个长度作为最大值的情况,那么比他大的全部删除,比他小的中删除最小的k个。前面的可以后缀和一下,前面的权值线段树上二分就行了。
贴个面试代码。。。