标签归档:Codeforces

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],就是经典的模型了。

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是整个平面上有几个联通的块。那么只需要一个求圆的交点的板子即可。