标签归档:ACM

最小(大)表示法

今天做了个leetcode的小比赛,最后一题是个最大表示法的裸题。。。发现这个东西我居然之前一直没学过,就找学弟要了个板子过了。然后自己看了看周源03年wc的ppt,感觉和kmp差不多,而且比kmp更简单理解。。。

原理看ppt就行了。。。。

leetcode这个题让求的是字符串的所有子串中的最大表示,而传统的最小表示法求的是字符串的循环同构中的最小或者最大的字符串。但是从原理来看,是先倍长原串,这样其实就可以套用了,我们只需要截断到字符串末尾就行了。

其实就是优化暴力嘛,时间复杂度O(n)。贴个leetcode代码当做板子好了。。

 

计蒜之道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。。。
哦对了这个函数貌似叫做除数函数,表示约数的次幂和。