第15届湖南大学ACM校赛题解

A题： Oshino Shinobu loves Mr.Donut

题意：每一回合有几种甜甜圈分配方式可以选择，求最后在拿的甜甜圈数量不大于忍野忍的情况下最多可以拿多少甜甜圈。

题解：dp(i,j)代表第i回合和忍野忍差距为j的时候最多可以拿多少甜甜圈，然后n^2递推。

B题：Kuangyeye's Resistance

题目大意：计算图中n级网络的等效电阻
图片说明
解题思路：

C题： One Piece

题目大意：给出一个32位的整数n，求该整数二进制数表达式中1的个数。
解题思路：

假设二进制表示n=01000100，则n-1 = 01000011
我们可以发现n&(n-1) = 01000000

所以，每次进行 n&(n-1) 的操作实质就是抹掉n最右边的1

或者可以将n转化为无符号整数后，直接调用C/C++自带的函数__builtin_popcount()得出

D题：Kth hright

题意:两个队伍，每个队伍有n个人，每个队伍都按身高升序.有m次操作，每次操作讲某个队伍的某个人替换，且替换后该队伍依然是升序的，求每次替换后两个队伍中第k高的人，输出身高。

题解:
本问题等价于求两个有序序列第k大，一般很容易想到的做法是遍历O(n)但本题有m次询问故会超时。注意本题的k是小于等于n的，那么结果必定在1号数组1~~n和2号数组1~~n之间。
设当前A数组有效范围从l1(初始为1)到r1(初始为k),B数组有效范围从l2（初始为1）到r2(初始为k),要取这两个范围内的第k大的值，
可以采取以下方法: **
**①:当k为1时，取两个A[l1]和B[l2]较小的结果范围答案，否则进行②操作
②:比较A[l1–k/2 + 1]和B[l2–k/2+1]的大小，删除较小部分的前k/2个元素，同时更新k，跳回操作①
m次操作，每次操作至多log2(n)次，故时间复杂度为mlog(n)

E题：Just calculat

图片说明

F题：Cards With Numbers

题意：
起始有一个空的序列，有两种操作：
0 x表示向序列中插入数字x
1 x表示查询序列中是否有数据x

对于每个查询输出yes或者no分别表示有和没有
操作数规模1e6，x范围0~1e9，时限1s，空间256M

解题思路：
(1) 1e6的输入规模，需要读入优化，这个不会的自行百度“读入挂”即可。
(2) 对于一个数字x，我们只需判断它存在或者不存在，也就是说这是个非0即1的问题。
对于这个非0即1的问题，考虑以下三种思路：

(1)STL里的map(或者手写AVL树)，这个的时间复杂度是O(nlog n)，1s会TLE

(2)用bool数组，O(n)的时间复杂度是可以了，但是O(max{x}）的空间复杂度是不行的。由于x的数据范围是0~1e9，那么bool数组的size就有可能需要达到1e9，也就是需要1G的内存，显然会MLE

(3)对于(2)进行优化，计算机里能够表示0或者1的最小单位不是bool,而应该是bit，1个字节是8个bit，如果可以用bit来表示0或1，则一个字节就可以表示8个数，1e9个bit占用空间也就是1e9/8字节，也就是大约125M。时间复杂度也是O(n)的，O(1)的插入，O(1)的查询。虽然这是最初设想的正解，但是呢，实际上这题用哈希也能AC。。。
图片说明

G题：Longest Palindrome Substring

题意：判断给定字符串的最长回文子串的长度是否大于1

做法1:用manacher算法在O(n)的时间内求出所给字符串的最长回文子串，看长度是否大于1

做法2:观察易知，长的回文串中间必然包含短的回文串。
例如回文串abccba中间包含回文串bccb和cc，回文串abcba中间包含长度大于一的回文串bcb。
所以字符串的最长回文子串长度是1等价于不存在长度为2和为3的回文子串（如果长度>=2，那么必然包含为2 的或者为3的）。
不存在长度为2的回文子串→s[i]!=s[i+1]
不存在长度为3的回文子串→s[i]!=s[i+2]
循环所有的合法的i，都满足上述两条则最长回文子串长度为1，否则大于1.