Hackerrank HourRank 13
十一之前，Codeforces上面自己的rating是1876，一看十一期间有四场比赛，想着怎么也可以上1900了吧，结果呵呵呵了，暴爽的十一三连跪(剩下一个8号的感觉还是跪)，直接掉到了1800，又一次感觉自己真是大菜鸡啊。
下午的时候有很多想在blog里夹带私货总结的，但刚刚写了两个小时的日记。。。忽然发现把什么话都说完了。
我好想在今年变成紫名啊。。。加油。。。吭哧咔哧吭哧咔哧
很喜欢Hackerrank上面的HourRank，原因就是时间短，题目也没有那么难。和别人的差距没有那么大(反正就一个小时，大牛写不完的就写不完了，我这样干瞪眼的也不用难受太久)。像Week of Code那种真是惨绝人寰，到后期还是有人把难题做出来，看着比赛的倒计时一点一点流失，Rank一点一点掉啊，自己还是无能为力的感觉太痛苦。但我还是要打Week of Code啊，好有趣啊啊啊
LeetCode的题落下了好多，明天补一补吧。。。
Sum vs XOR
题意给定一个数$n(n\leq10^{15})$，找到满足这样要求的$x$ :
1.$x(0\leq x \leq n)$
2.$x + n =x \oplus n$
求有多少个$x$满足上面要求。
发现n用二进制表示的话，如果该位为1，那么x在该位上只能是0，否则就进位。如果该位是0，那么x在该位上可以1可以0。所以计算n有多少个0，再2的幂。
Coprime Conundrum
题意是求在有多少个互质对，其乘积小于等于$k(0\leq k \leq 10^9)$。
和HDU1695是一个题，都是容斥原理，找小于等于up里面，与x不互质的个数。
然而我是从1到n枚举了，最后结果还除以一个2，我是沙茶么。。。
直接枚举到$\sqrt k$啊，之后就深搜减去比自己小的，剩下的就没算重复了。
Longest Palindromic Subsequence
题意是给出一个长度为$n(1\leq n \leq 3000)$的字符串，现在要你在任意位置往里面添加一个字符，使得这个字符串的最大回文序列(不是串)至少增加k个。
可知添加一个字符的话，最大回文序列最多多2个，k如果大于2直接就GG。
之后就是枚举添加的位置了，添加的字符可能是作为中间字符，那么最大的回文序列就是两边(其中一边逆过来)的最长公共子序列*2+1；如果是作为两边字符的话，那么就是中间算最长回文子序列的长度，两边算最长公共子序列的长度，dp记录这两者的状态。最后判断是否大于等于k。