GoogleCodeJam乱做

膜了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一下就好。