标签归档:dp

计蒜之道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. 阿里巴巴的手机代理商(困难)

待补。。写不动了啊。。

Leetcode 790. Domino and Tromino Tiling(dp)

题目链接
题意:给出一个2*n的棋盘用2*1的矩形骨牌和L型骨牌覆盖,求方案数。
这是今天中午的leetcode最后一题,窝记错时间了只剩半个小时才开始,最后rush了一波这个题,结果死于模数写错。
因为这两种骨牌可能构成两种形态,所以可以考虑设计成两维dp。dp[i][0]表示完全覆盖第i列,dp[i][1]表示剩一个格子。那么就可以转移了。
据说有个递推式:A(n)=A(n-1)*2+A(n-3)。

Codeforces Round #462 做题记录

934A. A Compatible Pair
简单的想法就是要么删除最小的元素要么删除最大的元素(因为要考虑元素的正负性质),那么枚举一下这两种情况下的选择即可。

B. A Prosperous Lot
最多也就18个8,那么就是36个面积。优先选择8,剩余一个的话随便放4即可。

A. A Twisty Movement
题意:一个均由1或者2组成序列,现在要求你翻转一段区间使得翻转过后的序列的最长非降子序列最长。
一开始想了个做两遍LIS(正着一遍反着一遍)然后枚举断点,本质上就是一个贪心的过程。
后来被学弟教育了:因为我们最后要找的序列一定1*2*1*2*这样的,那么我们可以把这个序列分成4部分,然后dp。实在是没想到。。。这样的话复杂度就是O(n)惹。。

B. A Determined Cleanup
题意有点难描述还是看题面吧。
这道题不会,看了题解才知道该往哪方面想。我们尝试通过ai来表示p发现可以得到这样一个式子:p=a0+(-k)*a1+a2*(-k)^2….。
要求ai均为正整数,那么这相当于用-k进制表示p,进制转化一下即可,注意要把系数调整为正。

C. A Colourful Prospect
题意:给出3个圆问把平面分成了几部分。
考虑欧拉公式:V-E+F-C=1。其中V为点数,E为边数,F为面数,C是整个平面上有几个联通的块。那么只需要一个求圆的交点的板子即可。