知识点积累（三）
一、输入外挂
非负整数：
-
int read()
-
{
-
int c,res ;
-
while((c = getchar())<'0' || c>'9');
-
res = c-'0';
-
while((c = getchar())>='0' && c<='9')
-
res = res*10 + c-'0';
-
return res ;
-
}
存在负整数：
-
int read()
-
{
-
int f=1,c,res;
-
while(((c = getchar())<'0' || c>'9') && c!='-');
-
c=='-' ? f=res=0 : res=c-'0';
-
while((c = getchar())>='0' && c<='9')
-
res = res*10 + c-'0';
-
return f ? res : -res ;
-
}
二、全排列
在做一个题时，给你一个数字让你重新排列，排列后尽量接近该数字且比它小。可以用全排列函数next_permutation( 数组名,数组名 + 个数 ) ; 数组可以是整数也可以是字符串。
三、数学公式
1、点到直线的距离
假设点（x1，y1）到直线 AX+BY+C=0 ,的距离 d = | Ax1+By1+C | / sqrt( A*A+B*B ) .
2、圆台体积
圆台的体积公式：V = [ S + S' + sqrt( S * S' ) ] * H / 3 = PI * H * ( R^2 + R*r + r^2 ) / 3 ;
r - 下底半径 R - 上底半径 H 高
做题感悟：这题曾经向那个方向想过，但是一直没实现。
解题思路：首先计算任何一个所求的序列一定是一个以 1 为公差的等差数列。先求所求数列中最多有多少个数，等差公式：Sn = n *a1+d*n*(n-1) /2 , 因为 d=1 ,且当a1等于1时有最多数，所以 Sn = n*( n+1 ) /2 . Sn *2 = n*( n+1 ) n<=sqrt( Sn*2 ) .知道最多有多少个数，接着依次遍历，看末尾项是否小于 n .
这里总结一下等差公式：设首项为 a1 末项为an 项数为 n 公差为 d 前 n 项和为 Sn .
Sn=( a1 + an )* n /2 Sn=n*a1 + n*( n-1 )/2 *d Sn = ( 2 *a1 +( n - 1 )*d ) *n/2 Sn=A*n^2 +B*n ( A = d/2 B = a1 - d/2 )
做题感悟：这题开始看时貌似很难，但是等它激怒了我，我就下定决心一定A掉它，就这样不断的wa,,,最后还是让我AC了，做完才发现这题很简单。
解题思路：这题和球最大连续和的思想差不多，只是这个可以形成环。
做题感悟：这题如果没有提示自己想方法真不好想于是记录一下。
解题思路：我们可以将立方体的8个顶点染成红色和蓝色，要求任意两个相邻的顶点颜色补同。若A,B,C,D的粒子数分别是a，b，c，d，A,C同色，我们可以通过运输将C点的粒子都移到A点（先让A,B同时增加c个粒子，然后将B,C同时减少c个粒子，此时A，B，C，D的粒子为，a＋c，b，0，d），这样我们解决这个问题就简单多了。
七、期望、方差
因为方差和期望在比赛时出过，虽然都险过但是想公式想了好久。
期望：即算数平均值 E(X) = ( a1+a2+a3+a4+……an ) / n .
方差：方差是实际值与期望值之差平方的期望值，而标准差是方差算术平方根。在实际计算中，我们用以下公式计算方差。方差是各个数据与平均数之差的平方的和的平均数,即S^2 = 1/n * [ （x1 - x ）^ 2 +( x2 - x )^ 2 +(x3 - x ) ^ 2……+( xn - x )^2 ] , 其中，x_表示样本的平均数，n表示样本的数量，xn表示个体，而s^2就表示方差。
做题感悟：这题只想到一点如果 x y 的最大公约数不是 1 则结果为 Inf ,以为如果 x y 的最大公约数为 z ( z != 1 ) 那么由 x 和 y 组成的数一定是z的倍数。至于那个公式不知道如何推出来，这题应该再忍耐一下说不定就找到规律了。
解题思路：x y 的最大公约数为 1 则为 n*m - n - m 否则 为Inf 。
数学题 : 借这题总结一下抛物线的公式：v = g*t h = v * t - 1/2 * g * t ^ 2 v1^2 - v2^ 2 = 2 * g * h y = a * x^ 2 + b*x + c (顶点坐标：( - b / ( 2 * a ) , ( 4 * a * c - b * b ) / ( 4 * a ) )) .
求抛物线解析式公式： 1 ) 已经知道抛物线上三点( x1 , y1 ) , ( x2 , y2 ) , ( x3 , y3 ) , 设抛物线公式为 y = ax^2 + bx +c ; 带入三点求三元一次方程，解得 a, b , c 的值。
2 ) 知道抛物线与 x 轴的两个交点 ( x1 ,y1 ) , ( x2, y2 ) ,以及另一点( m , n ) ,设抛物线公式为： y = a*( x - x1 ) * ( x - x2 ) 代入( m, n ) 可以得到 a 的值。
3 ) 已知抛物线经过原点且已知顶点( x1, y1 )坐标求解析式： 设抛物线公式为： y = a*( x - x1 ) ^ 2 + y1 ; 代入 ( 0 , 0 ) 求出 a 的值代入即可。
题目给出 h x v 根据公式可得（H 指上升高度并非总高度）： 1 ) H = v *sin( rx ) - 1/2 * g * t^2 ; 2 ) x = v*cos( rx ) * t 由 1 ) 和 2 ) 得 ： H = x * tan( rx ) - 1/2 * g *x^2 *( 1+tan( rx ) ) ( PS : rx 指角度 ) so 最大值为 ： ( 4 * a * c - b * b ) / ( 4 * a ) ;
做题感悟：这题一定要注意精度的处理，开始就推出状态方程但是没处理精度一直wa。
解题思路：dp [ i ] 代表花费 i 元钱最多有多少种方案，初始化也要注意 dp[ 0 ] = 1 ,其它均为 0 。
动态方程：dp [ i ] = dp [ i ] + dp [ i - v ] ; ( V 为相应的钱 )
文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nyist_zxp/article/details/20685369
- 点赞
- 收藏
- 关注作者
评论（0）