知识点积累（二）
做题感悟：这题是在比赛时做的，开始没做这题，看见有三个人 AC 而且没超时现象，所以……
解题思路：用线性筛法（在本题与一般筛法时间一样）把素数筛出来，然后判断是否为美素数，可以把美素数存起来或者选择二分（内存少）。
做题感悟：开始写完代码时差点要提交但是又测试了几组数据不可以，又改了一下才可以，幸好没交，所以以后提交一定要淡定，多试几组测试数据，代码有点乱。
解题思路：这题属于练习代码的题，俗称模拟题，1A。
做题感悟：这道题是简单数学题，开始想到方法了，但是求出的 X 值不是最小的，这一点没考虑到。
解题思路：化成平方差的形式，( y - x ) * ( y + x ) = n , y - x = a , y + x = b , 解得：x = ( b - a ) / 2 ,要想 x 最小，b 与 a 应该尽量接近，应该从 sqrt ( n ) 开始到 1 遍历。
做题感悟：开始做这题时在调用函数时就犯一个致命的错误，传递的是 double 类型的，但是形参我用的是 int 类型的导致超时，之后跟别人讨论了一下才出来。感觉这种题应该多思考一下，这样可以提升做题的能力，毕竟以后单挑的形式多。
解题思路：把给的公式两边分别加起来你就会发现，其实体重增长是一个等比数列，注意开始如果就大于 k 时输出 0 天。
五、STL之Vector
vector 我很早时就听说了，只是迟迟没学习它。vector和C++ 的string 类形式一样，string 相当于数组存字符串。vector相当于数组(可以用数组的形式也可以不用)，只是添加元素时开辟空间。
头文件：#include<vector> + using namespace std ;
基本运算：
v.empty( ) 判断是否为空
v.size( ) 返回容器中数据个数
v.clear( ) 清除元素中所有数据
v.erase( pos ) 删除 pos 位置的数据
v.erase( beg,end ) 删除 [ beg , end ) 区间的数据
v.front( ) 返回第一个数据
v.insert( pos ,elem ) 在 pos 位置插入一个 elem 拷贝
v.pop_back( ) 删除最后一个数据
v.resize( num ) 重新设置容器大小
v.begin( ) 返回指向第一个数据的迭代
做题感悟：这题属于想法题，开始第一次做时想到了，第二次又去做时居然想了老半天。
解题思路：最多的相同等级的士兵 = 最少数量的扫帚 ，可用 sort 排序，map，字典树。
做题感悟：因为在研究字典树，so 这题一看就是字典树+深搜，另一种比较巧妙的方法真没想到。
解题思路：这题可以用字典树+深搜做，也可以用map解决（将字符串映射成数字）。
八、错排
之前做了好几道关于错排的题，于是总结一下。
错排：你封信放入n个信封里，要求全部放错，求共有几种方法，记n个元素的错排总数为F（n）
假设有n封信，将第一封信可以放在 2~n 的任意一信封里，共有n-1 种放法，如果第一封信放在了第k个信封里，若此时第k封信放在了第一个信封里，则只要将剩下的n-2封信错排，即F（n-2）错排，如果第k封信没有放在第一个信封里，可将第1封信的位置看成“第k个位置”，即将n-1封信错排，即F(n-1)
由上可得公式：F（n）=（n-1）*（F（n-1）+F（n-2）） 。
做题感悟：这题不会钟表时间转化为角度，纠结了很久。
解题思路：先按照角度从小到大排序，如果有相同角度的则时间早的在时间晚的前面。
转化公式： angle =fabs（ h * 30 - 5.5 * m ）(如果h >12 , h - = 12 这点很重要）
已知三角形三遍 a ,b , c 求 c 边所对应的角度 angle = acos ( ( a*a + b*b - c*c ) / ( 2.0*a*b ) ) * 180.0 / 3.1415926 ;
做题感悟：这题很简单，为什么要写进博客呢 ？我的代码虽然AC了，但是太麻烦！改过之后纪念一下。
解题思路：BFS+优先队列。
十一、HDU 2072 单词数
做题感悟：这题其实是一个字典树模版题，但是在输入上恶心了好久具体见代码。
解题思路：字典树，map都可以。
做题感悟：明明快做出来啦，只要稍微动动脑筋就可以的事，为甚忍不住搜题解呢!!!!
解题思路：N=（a+1）+(a+2)+......+(a+n)= n*a+n*(n+1)/2;即求该方程的整数解！ 个数最多为 N = ( x +1 ) * x / 2 , so~ x<=sqrt( 2 * n )
做题感悟：一看这题无非是找规律或者有数学方法。
解题思路：方法一、找规律：当你列出 12 个时你会发现把它分成奇数和偶数的情况时，f [ i ] = i - 2 + f [ i - 2 ] ; 方法二、当在一条直线上变成逆序时需要 n*（n-1）/2 次，但这题是环形所以将环分成尽量相等的两部分，求逆序即可。
十四、HDU 2154 跳舞毯
做题感悟：通过这题可以明显感觉出只想不动手永远做不出题。
解题思路：因为每次跳有两次选择，所以第 i 次跳共有 2^i，但是求第 i 次必须求第 i-1次有多少选择了A，所以次数就等于 2^( i - 1 ) - f [ i - 1 ] .(这题要注意中间值，有可能溢出)。也可以用dp ：动态方程： dp[ i ] = dp[ i - 1 ] + 2 * dp[ i - 2 ] .
做题感悟：这题真是太坑了，也许自己不够灵活，在做不出时应该认真读题，看是否是思路错了。
解题思路：这题其实只要其中一个放水点大于等于司令部就可以把司令部淹没。
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/17550189
- 点赞
- 收藏
- 关注作者
评论（0）