【10月末总结】

总结

1.计划总结

白书的训练指导第一部分训练也告一段落了。收获用巨大形容也不为过。

2.简单比赛总结

I.10月份的几场新生赛也算排在前列，比较稳了，比起一开始的一两场不熟悉的比赛进步了不少。比赛内容停留在BC一题难度。估计11月的校赛过后就要升级难度了。所以要有准备。

II.BestCoder感觉应该可以稳定搞定两题了，毕竟之前的几场测试卡在第二题边缘，上一次BC成功突破了，希望明天的BestCoder能做出两题来。

3.算法总结 (开学->现在)

{

(1)异或运算

1、一个数异或本身恒等于0，如5^5恒等于0；

2、一个数异或0恒等于本身，如5^0恒等于5。

3 满足交换律

(2)字符串函数

1.strtok

strtok()用来将字符串分割成一个个片段。参数s指向欲分割的字符串，参数delim则为分割字符串中包含的所有字符。当strtok()在参数s的字符串中发现参数delim中包含的分割字符时,则会将该字符改为字符。在第一次调用时，strtok()必需给予参数s字符串，往后的调用则将参数s设置成NULL。每次调用成功则返回指向被分割出片段的指针。

2.atoi,atoll,atof

把字符串转换成整型数。ASCII to integer 的缩写。

其余同理(可忽略字符串前面非数字非符号)

3.strchr() strstr()

分别为查找字符串S1中第一次出现字符c位置，第一次出现字符串S2位置

4.sscanf()

这个不多解释了

(3)特殊字符串数据读入技巧

Josephus 72(3) 126 10 -3 0 47 21(2) -2

对于这样的数据 scanf("%d%c") 可轻易判断读入的数据的后面时候有括号，有的话再这样读一遍；

(4)格式控制

printf("%-10s"）左对齐

printf("%4d"）右对齐

printf("%04d") 不足位用0补

(5)搬家问题—贪心策略

差值排序贪心

(6)分CAKE

图像法->转换成数学问题->证明且得到关键公式p+q-gcd(p,q)

(7)素数筛法一些其余的小运用

可以维护某个值分解后拥有的最大素数（O（n）级别的貌似不可以）或最小素数（O（n）筛素数的最小保存详情见8代码）或者素数个数

貌似也可以维护欧拉函数（因此不用再分解因式）（由8知可以）

可参考：http://blog.csdn.net/dream_ysl/article/details/7934471

(8)欧拉函数

欧拉函数 $varphi(n)$ 是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名

φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn) 其中p1, p2……pn为x的所有质因数

可以在O（n）筛素数中很快忘成！

原理如下：

代码去翻之前的文章：

m%p=0时：phi（n）=phi（m）*p

m%p！=0时：phi（n）=phi（m）*（p-1）

(9)O（n）筛素数

利用最小质因子筛选

证明：

http://blog.csdn.net/zy691357966/article/details/39703937

(10)十分棒的一道删数题（数学+枚举（三段分拆法））

http://blog.csdn.net/zy691357966/article/details/39717451

(11)N^N

科学计数法+取对数

(12)斐波那契数列前几位数（看起来像超级高精度）

变形公式+科学计数法+取对数

或者

黄金比例+科学计数法+取对数