月度归档:2018年03月

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

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

Codeforces Round #470 做题记录

最近尽力补补cf。。
A. Protect Sheep
暴力检验一下S上下左右有没有W就好了。。

A. Primal Sport
发现只需要迭达两次,我们要判断出来X1的可能范围。因为X2一定是一个合数,我们可以预处理出来1e6以内每个合数的最大质因子。因为X1一定是在[x2-p+1,x2],要想让这个区间尽可能的大,也就是p要最大,所以我们要处理出来最大质因子。然后在把这个区间内的可能值for一遍,维护最小值即可。

B. Producing Snow
用一个堆把已经加入的雪堆存起来,用一个标记表示累计的每天消耗的雪量,然后每天把消耗完的雪堆扔出堆外,最后剩下来的雪堆数目就是在这一天消耗完整的t[i]的堆数。感觉是个套路题吧。。。注意爆int。

C. Perfect Security
挺简单的吧,用一个trie存下来p[i],相当于对于每个a[i]找寻可以让其异或起来最小的p[i],就是经典的模型了。

Leetcode 685. Redundant Connection II(并查集)

不粘题面了。。。就是煞笔题写了半天,写出来各种细节错误。。
就是并查集判环,但因为是有向树只能固定方向了,不能按秩合并。而且删哪条边也需要考虑是否有一个点有两个父亲。然后就没了,讨论出细节即可。
这种状态准备面试还是csp都是gg的啊。。。