清华集训2013 BZOJ3581 扑克牌

GoogleCodeJam乱做

Recursion posted @ 2016年4月02日 19:42 in 题解 with tags GCJ , 558 阅读

膜了waltz神犇的博客后感觉gcj的题目很靠谱的样子...

考虑到今年gcj就要开始了,我还没做过gcj的题,所以决定来学习一个gcj的姿势。

4.10 update:今年的qualification round还是很良心的...至少没有俄罗斯方块那种坑爹题...

4.19 update:早知道jsoi day2就在家打round1A了...

 

2015qualification A:签到题。

2015qualification B:枚举最大值贪心。

2015qualification C:给出的运算表并没有什么卯用...简单的暴力划分成三段就行...

2015qualification D:马隆爆搜题懒得写了...题面给的图片已经剧透了,如果[tex]X>6[/tex],那么总可以搞出一个中间有空隙的omino,直接特判。否则情况就不多了,爆搜+各种剪枝应该就可以过了吧...

2015round1A A:第一问直接算,第二问枚举速度算一下。暴力可以过,不过似乎可以二分。

2015round1A B:二分显然。稍微有点细节,WA了两次T_T。

2015round1A C:把所有点按当前点的极角序排序,显然如果这个点在凸包上一定要有一个180度的范围没有点,[tex]O(n)[/tex]扫过去就行了。

2015round1B A:先贪心搞出[tex]10^k[/tex]。注意到翻转操作只对前一半数位有效,所以每次只会翻转一次。特判末尾是0的情况。

2015round1B B:智商太低想不出来的sb题。如果人数不超过一半答案就是0。否则考虑把人装满后去掉多余的人。于是就可以直接贪心了。

2015round1B C:首先判相交可以直接判断到达终点的时间。第一次会造成1次相遇。之后第[tex]k[/tex]次会造成[tex]k-2[/tex]次相遇。用个堆维护时间点就好了。

2015round1C A:sb贪心。

2015ronud1C B:sb大暴力。kmp可以优化不过这题用不着...

2015round1C C:sb贪心。没仔细想为啥是对的...

2015round2 A:暴力最外面一圈箭头就行了。

2015round2 B:比较无聊的题。搞出每种水能够调节的范围,二分答案即可。

2015round2 C:一道不错的最小割建模。把句子和单词连边,那么句子1和2之间的每条路径必须有一次语言转换。拆点建图即可。

2015round2 D:一道非常有趣的计数题(比起什么玄学大状压不知道高明到哪里去了)。首先利用burnside's lemma枚举置换的长度,然后dp出对应循环节的方案数即可。在纸上画一画可以发现合法方案只能由整行的1和2的4种组合间隔着两整行的3组成,简单的dp就好。

2016qualification A:签到题。

2016qualification B:去掉最后一段+,统计有多少段即可。考虑倒过来做还是挺显然的。

2016qualification C:不会做的sb题,最后还是bx2k教我的。考虑B进制下构造B+1的倍数。显然奇数位和偶数位的贡献分别是1和-1,然后就随便做了...

2016qualification D:按照第一大块里的第二中块里的第三小块...这样的顺序依次询问,可以让每次询问判断出尽可能多的位置是不是gold。

2016round1A A:签到题。

2016round1A B:所有出现奇数次的数。

2016round1A C:简单的dfs一下就好。

 


登录 *


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