sukhoeing/aoapc-bac2nd-keys

算法竞赛入门经典第2版-习题选解

aoapc-bac2nd-keys's Issues

习题解答原书勘误

36页向上数第三行代码，C++ 应该没有 readInt

195页例题7-5有一处笔误

第二段：

输入正整数n和L，输出由前L个字符组成的、字典序第k小的困难的串。

应该是字典序第n小的困难的串。

另外，书上的样例输出与题目实际要求的输出出入较大，是不是因为希望读者去读原题所以才这样？

1

《习题与解答》P11 & P12 & P19,20 & P25 疑问

P11
从上往下
vector<string> vec{1,2,3};
应改成
vector<string> vec{"1","2","3"};

P12
在HashFunc中,蒟蒻有些不清楚
return (hash<int>()(o.x) ^ hash<string>()(o.y) << 1) >> 1;
这一句最后的">>1"的作用.
假如值在先前的运算中已经一样的话,右移等于没效果.
假如值不一样,这样反而有极小的概率使得其相同,就Hash冲突了.
好像只会浪费时间诶,应该可以去掉吧.

P15 C[n+1][k]=C[n][k]+x,其中x应该是k在n+1中出现的次数，而不是n

182页 UVa725的讲解中对枚举量的分析有误

紫书182页，UVa725，分析里面说枚举量降低到不到1万，这个不对，应该说枚举量的数量级降低到一万。做一下实验发现，枚举量最大的时候是n=2，示例代码中fghij从1234枚举到50000。

p243 程序结束后多了个一样的main函数

如题

7.2.3插图中位置cur并没有如书中所说那样标了高亮

这一节提到“位置cur用高亮表示”，高亮在哪

紫书的两个小问题

• 紫书例题9-22(UVA12105)的参考程序好像有点小问题？
  对于Udebug给出的数据并不能通过全部样例，在形如12 1593之类的只有0满足条件的数据的时候，程序会输出两个0。（虽然UVA上可以AC）
  (在程序中加入特判多个零出现的情况就好了)

• 紫书习题8-7 书上的翻译和实际问题不符
  书上的问题：用不超过2n^2次操作把它变成升序；
  实际问题：用不超过2n^2次操作把升序变成它

紫书第六章141页UVA 514例题代码有误

代码无法获得正确结果，没能正确处理输入

代码改进

ch4/UVa1589.cc
第118行应修改为：
scanf(" %c%d%d", &type, &(p.x), &(p.y));

原答案未在%c前添加空格，不添加空格时上一次输入的回车存在于缓冲区中，导致type读取为'\n'

P188 7.3.1 在没有假设n=10的前提下说解答树有1024个结点

要么写明假设n=10，或者写解答树有2^n个结点就行了。