//输入3个整数，输出它们的平均值，保留3位小数。 //输入华式温度f，输出对应的摄氏温度c，保留3位小数。提示：c=5(f-32)/9 //输入正整数n，输出1+2+……+n的值。提示：目标是解决问题，而不是练习编程 //输入正整数n(n<360),输出n度的正弦、余弦函数值。提示：使用数学函数 //sqrt是求开根方的函数，pow是求一个数的平方 //输入一个整数，判断它是否为偶数。如果是，则输出“yes”，否则输出“no”。 //一件衣服95元，若消费满300元，可打八五折。输入购买衣服件数，输出需要支付的金额（单位：元），保留两位小数 //输入一个浮点数，输出它的绝对值，保留两位小数 //输入三角形三边长度值（均为正整数），判断它是否能为直角三角形的三个边长。 //如果可以，则输出“yes”，如果不能，则输出“no”。如果根本无法构成三角形,则输出“not a triangle” //输入年份，判断是否为闰年。如果是，则输出“yes”,否则输出“no”。

本文是我对第五章12道例题的练习总结，建议配合紫书——《算法竞赛入门经典（第2版）》阅读本文。
另外为了方便做题，我在VOJ上开了一个contest，欢迎一起在上面做：
如果想直接看某道题，请点开目录后点开相应的题目！！！

这个题比较基础，排序用sort，查找用lower_bound，都是STL的标准函数。注意lower_bound函数的返回值是不小于查找数的第一个位置对应的指针，找不到则返回a+n（也就是函数的第二个参数）。

---

由于此题中木块堆的长度一直在变化，并需要频繁的添加和删除元素操作，用vector是最合适的。
另外，这个题的四种操作中具体操作有一定的重复，合理拆分操作能够使代码模块化更好。

---

此题中涉及的知识点有：
1、set的用法（注意set中没有重复的值）

---

我的代码用了两个map，不如书中的例程代码用了一个map和一个vector。

---

这个题主要使用的数据结构是stack，但最重要的知识点却不是stack！
本题有一种用映射简化数据结构的思想：将另一种相对复杂的数据结构用map映射成int型id，不仅能够大大降低存储空间，而且也可以大大提高查找效率。
因此这是第五章最重要的一道题，没有之一！！！
后续习题或例题中有好几道用到了这种思想，后面会讲到。

---

队列的特点是先入先出，通常排队系统的题会用到队列。
本题用两个队列解决：每个团体有一个队列（元素为团体成员ID），团队整体又形成一个队列（元素为团体ID）。

---

 

 思路
此题在uva上一度submit error，后来可以了。
此题没有必要一定用long long，因为所求结果（第1500个丑数）并不超过int表示范围。但我结果*5却会超过，所以我的程序中用了long long。
代码
 
 

---

 

 思路
注意这个题要求的是按列优先方式输出，这与程序正常输出的方向不同。因此需要改变循环层次，具体见程序。
另外只要有字符后面就要补全M或M+2个字符，如果没有字符则不用。
代码
 
 

---

 

 思路
四重循环枚举肯定会超时，实际上存在大量无用的比较。实际上只需要枚举c1和c2，然后从上到下扫描各行。每次碰到一个新的行r，把c1,c2两列的内容作为一个二元组存到一个map中。如果map的键值中已经存在这个二元组，该二元组映射到的就是所要求的r1，而当前行就是r2。
还有一个细节问题：如何表示由c1,c2两列组成的二元组？一种方法是直接用两个字符串拼成一个长字符串，速度更快的则是进行预处理——给所有字符串分配一个编号，则整个数据库中每个单元格都变成了整数，上述二元组就变成了两个整数。这是例子5-5中介绍的技巧。
另外在做的时候有一个小插曲，第一次提交TLE了，查了一下程序发现每组数据计算时忘记重新对map进行初始化。
代码
 
 

---

 

 思路
该题尚未尝试，先占个位置。
代码
 
 

---

 

 思路
该题尚未尝试，先占个位置。
代码
 
 

---

 

 思路
该题尚未尝试，先占个位置。
代码
 
 

---