150127测试总结（一）

第一题：niven【P373】R   （T：最多为O(n²)；R：O(n)）
1.核心思想：任意进制转换为十进制。
2.易错点：忽略掉【十进制】不需要转换，只需要提取数字即可。

第二题：sub最长子串【p374】W  （T:O(n²)；R：O(n)）
*错因：1、没弄清楚string所占字节。开了3000000个，超过了内存。
       2、处理不同字符的方法不对，O(n³)的复杂度并没有因为提前找到子串跳出循环而减少。【详见代码子函数】

1.核心思想：用0,1判断此位置字母与前面D（字串长度的一半）的字母是否相同，由累加结果比较看是否子串成立。
           另外，有add[j]=add[j-1]+mk[j+i-1]-mk[j-1];来递推计算出i位置后所有起点的不同字符数。减少了一层循环。
2.易错点：+1或者-1要弄清楚
3.技巧：1）枚举一半字符长度，直接回避判断长度是否为偶数
       2）用string比用char简单，可用s.substr(起点，字串长度)函数，来直接得到子串内容。比参考代码上再用一个循环来找要方便一些。

第三题：传递消息news【p375】R  （T:O(n³)；R：O(n²)）
1.核心思想：Floyd得到最短路，筛选同一起点最短路中的最大值。再找所有起点对应最大值中的最小值。
2.易错点：有向图。

第四题：选数问题arrange【p376】W  （T：O(n*log₂n) ；R：O(n)）
*错因：1、分析题目时出错。直接用了O(n³)的方法。
1.核心思想：二分答案。
2.易错点：最后输出L或R要分析一下，此题最后应该输出L。
3.技巧：1）不想计算L或者R的时候，直接用ANS存储。
        2）枚举答案从1~1000000000用“>>1”位运算符，比/2要快。【等效】