首页 > 代码库 > acm 经验
acm 经验
1. 求夹角时候的tan值可以用x/y， 这样比较哪个更大，则夹角距x正向的距离更小.
2. 全局变量放在主函数外面可以减小运行时间。
3. qsort中的size如果是结构体的话最好用结构体第一个单元，如sizeof(num[0])。
4. 有大量比较时候尽量用sort、qsort不稳定，sort返回值是0和1.
5. 使用排列组合算C(n,m)时可以由小到大算
__int64 C(int n, int m)
{
_int64 all =1;
for(int i=n, j=1;j<=m; j++, i--)
all = all* i/ j; //注意这里不能写成all *= i / j;
return all;
}
6. 错排公式：D[0] = 0; D[1] = 0; D[2] = 1; D[n]= (n-1)*( D[n-1] + D[n-2] );
7. if ( ( year%4==0&& year % 100 != 0 ) || ( year % 400 == 0 ) ) 闰年判断
8. int day[] = {31, 28, 31, 30,31, 30, 31, 31, 30, 31, 30, 31};
9. __int64 lcm(__int64 a,__int64b) // 最小公倍数
{
__int64 c =b%a;
if(a > b) return lcm(b, a);
if(c==0)return b;
returnlcm(c,a)/c*b;
}
__int64 gcd(__int64 x, __int64 y) //最大公约数
{
__int64 m;
if(x<y)
returngcd(y,x);
if(x%y!=0)
returngcd(y,x%y);
else return y;
}
10. 如果是长宽同时为n的矩形，在dfs时可以用k（为n*n次）表示x， y
x = k /n, y=k%n;
11. strcat, 在字符串末尾加字符。
12. struct data {int i, int j }; 在{}内使用data () { i = 0, j = 0} 可以赋初始值。
13. 通项n*(n+1) 的前n项和为 n*(n+1)*(n+2)/3,
通项n*(n+1)*(n+2) 的前n项和为n*(n+1)*(n+2)*(n+3) / 4。
通项是 n-2，前n项和就是 n(n+1)(2n+1)/ 6
通项是 (2n-1)2，前n项和就是 2n(2n+1)(2n-1)/ 6 = n(4n2-1)/ 3
通项是 n3，前n项和就是 (n(n+1)/2)2
通项是 (2n-1)3，前n项和就是 n2 * (2n2-1)
14. reverse字符串反转函数，头文件<algorithm> strrev字符串反转函数，头文件<string.h>
15. 背包：( f总价值，价值是w[i]， 费用是c[i]，v容量)
（1）01背包：f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i])
（2）完全背包：f[i][v]=max([i-1][v-k*c[i]]+k*w[i])（0<=k*c[i]<=v）
（3）多重背包：f[i][v]=max(f[i-1][v-k*c[i]]+k*w[i]) (0<=k*c[i]<= n[i])
与01背包有点类似循环求f[i]时，从最大开始.
16. 函数assign()常用在给string类变量赋值.
直接用另一个字符串赋值 : str2.assign(str1); 即用str1给str2赋值.
用另一个字符串的一个子串赋值 : str3.assign(str1, 2(开始的下标), 3(复制的个数) );
用一个字符串的前一段子串赋值 : str4.assign("World(复制的字符)", 5(复制总个数);
用几个相同的字符,赋值: str5.assign(10(复制次数), ‘c‘(复制字符));
17. 充分利用计算机的^运算，x^x = 0， x^x^y=y，这样可以用来区别运算的数据是否成对。
如: zoj 3432
18. 可以定义string类的数组，但是要注意的是在VS中查看需要用类名加下标。
如string str[10], 在watch中查看时用str[i]看。
19. 从字符串str1中查找是否有字符串str2，如果有，从str1中的str2位置起，返回str1中str2起始位置的指针地址，如果没有，返回null。
20. 有些字符串题目不能同时出现两次相同的符号，可以在一个循环内加上两个相同的判断当第二次出现该符号时则退出。
21. n!结尾有多少个0：（取决于n又多少个5的因子）
当0 < n < 5时，f(n!) = 0;
当n >= 5时，f(n!) = k +f(k!), 其中 k = n / 5（取整）。
【http://15838341661-139-com.iteye.com/blog/1883889】
22. fabs 和 abs 慎用。
23. 欧拉函数是小于或等于n的正整数中与n互质的数的数目。
24. stripTrailingZeros是java移除尾部所有的0.
25. substring返回一个新的字符串，它是此字符串的一个子字符串。该子字符串始于指定索引处的字符，一直到此字符串末尾。exp："unhappy".substring(2)returns "happy".
26. 用java的BigDecimal时候别忘了String tem= result.toPlainString();来消除BigDecimal用科学计数形式来表示结果.
27. if((year%4==0&&year%100!=0)||(year%400==0))
acm 经验