标签归档:bfs

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

待补。。写不动了啊。。

Yandex Algorithm 2018 Qualification Round 做题记录

比赛的时候做了三个题就去睡觉了(反正签到就能晋级下一轮了)。
A.Lottery
签到。

B.Permutation Recovery
题意:对于一个n*n的permutation,n<=100,可以看作一个n*n的方阵。现将每一行看作一个长度为n的数列,每一列同理,打乱顺序输入n行和n列放在一起。让你找出一组可能的permutation。保证输入有解。 首先我们每个数字只会被包含两次,我们需要判断出哪一行是第一行,然后按图索骥放进去东西即可。所以其实就是个模拟,但是我写了四十分钟。。。太垃圾了。。

C.Beautiful Tables 给你一个n,不超过1000,让你在n*n的方阵中填1-n的数字,使得每一行的元素和 and 每一列的元素和都能被n整除。问你有多少种填的方案,答案mod 1e9+7。 比赛的时候是打表出来了n=4,然后利用oeis找到公式为\(n^{(n-1)*(n-1)}\)。 然后赛后才明白是怎么来的:我们可以在\((n-1)^{2}\)的左上角方阵任意填进去1-n种数字,可以证明一定有唯一解。 为什么?因为最右下角的格子只有一种填法。假设已知一种合法的填法,那么一定有:\(\sum_{i=1}^{n}\sum_{j=1}^{n-1} a[i][j]=0 (mod n)\)。\(\sum_{i=1}^{n-1}\sum_{j=1}^{n} a[i][j]=0 (mod n)\)。然后可以证明出来\(\sum_{i=1}^{n-1} a[n][i]=\sum_{i=1}^{n} a[i][n] (mod p)\)。而此时a[n][n]只有唯一一种选择了。所以得证公式。

D.Triangle Construction 题意:给你n (n <= 3e5) 个长度不超过1e18的木棍。有q (q <= 3e5) 组询问,每组询问形如(l, r), 1 <= l <= r <= n。让你找出[l, r]中三个下标不同的木棍,使得这三个木根可以构成一个三角形。如果找不到输出-1。 考虑最长的情况下的无解情况,一定是一个类似斐波那契的数列:1,1,2,3....这样的。而在最坏情况下,不超过100项就会超过1e18。所以我们每次只需要从这段区间中选出100项,然后排序依次check一下相邻的三根木棍即可(相邻是最有可能有解的)。

E.Good Snippets 题意:给你两个string的序列A[1-n], B[1-k],1 <= n, k <= 1e5,每个字符串长度都不超过10,B中的字符串没有重复。问有多少个(l, r),1 <= l <= r <= n满足B中的每一个元素都在A[l-r]中出现过,即set{A[l-r]} 包含 set{B[1-k]}。 这居然是一个双指针的简单问题,居然可以放到E? 用set维护b序列,然后双指针乱搞即可,因为随着长度的增加合法的可能性也越大,开了几个map维护一下信息(因为会有删除的存在)。

F.Network Topology 题意:给你一颗大小不超过2e5的树,让你在树上选两个不同的点a和b。树上两点间的距离定义为两点间最短路径上的边数,树上一点的不稳定性定义为这个点到a或b距离的最小值,整棵树的不稳定性定义为,树上任意一点不稳定性的最大值。让你选出a,b使得树的不稳定性最小。 和cleary大爷讨论一下,发现这就是14牡丹江的B原题。。。 我们二分一个距离x,那么从最深的点开始上找x步就一定是我们要设置的点了,而且只有设置在这里才可以尽可能的多覆盖点。然后从这个点去bfs一下删除能覆盖到的点。然后再从未覆盖的中找最深的点,从而确定另一个点设置在哪里。 这样的复杂度\(O(nlogn)\)。而且这个做法可以推广到任意k个节点。 这个题还可以\(O(n)\)(我能说鄙队当时练过这套题我写了个\(O(n)\),但是现在全忘了还是靠cleary才想起来)。就是找到数的中心然后拆开两部分,从而在新的两棵树上分别找到中心就是答案。本质上还是基于对于一棵树选一个点的话一定是中心。 但是貌似不能推广。。。

2017-2018 ACM-ICPC Southeast Regional Contest (Div. 1)H – Security Badges

题目链接
训练时候没什么想法,赛后看了看别人的代码,才发现居然是如此暴力的做法。
我们可以发现最后的答案,只可能是题目中给出的区间的端点组成的一些交。所以我们把每一条边的左右端点抓出来排序后暴力bfscheck,这里需要注意的是我们把区间的左端点减去1.如果当前值x可以,那么从上一个点到x之间的答案都是合法的。画一画就知道为什么了。。好巧妙~