2
14
2016
2

GCJ 2013

感觉再不认真做题OI水平就没有救了

听说GCJ题目质量蛮高的决定开一个新坑

3.31 其实开学前就想弃坑了,感觉gcj上的题更偏向结(xiang)论(ti)而不是算法。下面还是好好做cf的题吧,以后有时间再到gym里做做这些题。

 

 

15

【QR A】签到题

【QR B】对每一行每一列求最大值,判断每个点等不等于两个最大值中较小的那一个

【QR C】如果一个回文数的平方也是回文数,要求平方的时候乘法没有进位,这也要求各位数字平方和小于$10$。这样情况数就很少了,直接搜即可。

【QR D】有解的充要条件是每种钥匙的数量足够且能获得每种需要的钥匙,只需按位贪心就行了

【R1A A】裸二分

【R1A B】很经典的一道题啦(感觉在哪里见过),尽量取最大的,然后分治处理左右

【R1A C】只要暴力枚举排列算一下那个概率大就行了

【R1B A】按从小到大合并就行了,合并不了就乘二减一

【R1B B】在纸上画一下就出来了

【R1B C】如果一个人没有经过起点,那么他与鹿相遇一次,如果一个人经过一次起点,那么他与鹿不相遇,否则每多经过一次起点,与鹿多相遇一次。所以可以用优先队列保存每个人经过起点的时刻,将相遇次数进行相应的加减。因为减一只有$N$次,且答案最大为$N$,所以时间复杂度为$O(NlogN)$。

【R1C A】扫一遍就行了

【R1C B】只要$\sum_{i=1}^{n}i\geq \left | x \right |+\left | y \right |$,并且奇偶性相同,就必然有解。从大到小枚举,贪心改变绝对值更大的。

【R2 A】 贪心还是蛮明显的吧。

【R2 B】 二分大法。

【R2 C】 可以建出边数为$O(N)$的拓补图。每次取一个最小的,看它最前能放在哪里,然后分治处理左右。

Category: 题解 | Tags: | Read Count: 841

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com