TKK-ICPC Round#8 题解

竞赛链接:http://xujcoj.org/Home/Contest/cs/cid/696/ctype/1

1、形单影只

  位运算题目,由于每次操作只能在原来数字的基础上加 2,所以在不考虑这个数字二进制最低位的情况下,每次把 n 加上 lowbit(n),直到 count_one(n) = 1 或 n = 0,前者直接满足要求,后者则是数据溢出。在 n 进行自加的同时,使用变量 ans 记录每次加上的数字之和,如果最后溢出则多加 2,答案为 ans / 2。


2、成群结队

  计算字符串 S 的 Next 数组,假设串长为 m,则 m – Next[m] 为每增加一次需要的长度,所以最后答案为:(m – Next[m]) * (n – 1) + m,注意结果可能会超过 int。


3、进制转换

  提示:四位二进制 = 一位十六进制


4、寻找数字和

  计算前 n – 1 个质数的和加1后乘以 k 的结果即可,需要用到前缀和预处理,注意答案取模。


5、String Game

  使用双指针标记,由于操作次数很大,故不能完全模拟,考虑到游戏最后一定是涂涂和罗少反复在操作同一位置上的数字,故当两个指针重合时判断剩余操作次数的奇偶性即可。


6、Kingdom Rush

组合数公式

  快速幂,注意特判 n = 1 的情况。

2 条评论

发表评论

*

  • 为啥说是前n个质数的和乘以k啊。。。。样例中n = 2, k = 2时, 前2个质数2,3的和是5,5 * 2 = 10;n = 3, k = 5时,前三个质数2,3,5的和是10,10 * 5 = 50?要得到样例给出的答案,怎么还得多乘上一个3 / 5呢。。。。。

    • 这里要把1也算上,因为1与任何数的最大公因数都为1(题解已更新)