基本上就是按照大白学习的，基本上都是计数方法的运用。

这是的大体的对组合数学的学习导图。

指导

UVa 11729

UVa 11292 勇士斗恶龙

排序，贪心

UVa 11300

这个题目很有价值。

一方面通过数学推导得出结论。

编号为i的人初始有$A_i$枚金币。对于1号，给了4号$x_1$枚金币，自己还有$A_1-x_1$枚。然后从2号拿走$x_2$枚金币，现在有$A_1-x_1+x_2$枚金币，另外，设平均金币值为$A_1-x_1+x_2=M$。

由此可类推得到

$A_n-x_n+x_1 \Rightarrow x_n=M-A_n+x_1=x_n-C_n$

我们可以得到类推公式

$$C_i = C_{i-1} + A_i – M $$

证明:

$$x_2 = x_1 – C_1$$

$$x_3 = M-A_2+x_2 =2M-A_1-A_2+x_1=x_1-C_2$$\

以此类推。

可以求得，需要求的结果为:

$$|x_1|+|x_1-C_1|+|x_1-C_2|….|x_1-C_n-1|$$

即求这个式子值最小，即求$C_1, C_2, …C_n$的中位数。

LA 3708

这个题目也是比较有水平

使用了按比例缩小的技巧。其中，按逆时针编号，固定一个点作为原点，建立新坐标。原来的位置呈现在新坐标的位置为$pos = i/n*(n+m)$，如此，求移动距离则是$fabs(pos – floor(pos+0.5))/(n+m)$

UVa 10881

蓝桥杯去年山东省的初赛题目，的确有点意思= =

转换方向可以不必在意，因为最终看到的结果已经不知道最初的蚂蚁是哪一只了，所以不用纠结方向的问题。主要要考虑的是最终的位置，以及最初蚂蚁位置的存储，before，after的对应关系。

本文出自svtter.github.io

整数进制输出

把整数按照十进制，八进制和十六进制输出.

$2^32-n$补码表示法.

字符处理

使用Ctrl+D时, getchar()读到的是-1

假设一个年份为1993/12/12, 那么如何简单获取年月日？

使用sscanf函数.

可以使用fgets(s, MAXN, stdin)来获取简单的输入. 一次读入一行，包括空格，遇到\n结束读入

简单习题

• 分数统计

• 本文出自svtter.github.io

基础第二弹

虽然是很水的题目，但是还是收获了不少。

动态小数位数

整数位数

电灯

蛇型填数

调和级数

题目都很水（不能再水了），但是也算是有所收获。学习了一部分C。

• 本文出自svtter.github.io

Pi的获取

觉得自己的一些ACMer的基本素养不够，重新翻看。

pi = 4.0 * atan(1.0)

math.h中的M_PI并不是ANSI C标准。验证可以使用gcc -ansi

scanf输入格式实验

之前阅读了scanf函数的相关部分（百科），但是依然没有很好的掌握。

现在依然没有= =。

有时间需要重新学习一下。

判断整数和浮点数大小

floor(m + 0.5) == m

通过+0.5来判断m的整数值。

floor/ceil是数学库里提供的函数，默认gcc不会自动链接math库, 方法是(-l + 库)

gcc -Wall myround.c -lm -o myround

使用clock()计时

• 包含头文件time.h
• printf("Time used = %.2lf\n", (double)clock() / CLOCKS_PER_SEC);

会从程序开始的时候计时（不管输入输出），所以最佳方法是echo 数据 | ./a.out

多次使用clock()来计时的吧。。。

重定向和fopen读取文件输入测试数据

添加编译选项：-DLOCAL， 使得中间部分生效.

fopen在linux不支持，所以不写了。

---

• 本文出自<svtter.github.io>

利用排列找规律。

首先利用next_permutation函数进行求排列

代码如上。

可以观察出规律，然后即可AC。

详细代码下次再写= =

AC代码

规律在代码中，很明确。

• 本文出自<svtter.github.io>

写在之前

maker关于线性筛素数的论文。

做到欧拉线性筛法再做补充。(当时还写了个这？)

关于线性筛素数

• 之前一直没有正视线性筛素数的问题。今天特意来写一个伪证明。如果当前的i不是素数，那么必然被之前的某个素数筛掉了。i × prime[j]。

  一个合数必然可以写成几个素数的乘积，再或者就是p×i这种形式。如果能被i×p1筛掉之后则不需要i×p2继续筛了，i×p2可以写成p1×(i×p2)

例如12可以被6×2筛掉，之前4×3这种筛除就可以去掉。

• 这种方法会不会存在没有筛掉的合数？

不可能：i会一直到n，也就是整个范围都会包含在内。

代码：

之前的错误在于筛素数的时候没有筛去2的倍数，所以出现后面的值错误。

这个题目的总结就是不作不会死- -好端端的暴力我非要用个bfs。

看见自己wrong了还以为是哈希的问题- =

题意

• p1+p2+p3 = n，$p1 <= p2 <= p3$
• 输出符合条件的组数

输入输出

• 给100组n，输出组数

分析

• 只有3个数，暴力解就可以，注意循环终止条件。

[阅读全文]

最近都是用gcc+vim写代码，昨天突然写个代码算法出个逻辑bug，因为用了大量递归调用，DEB半天出不来也是醉了，于是 学习一下gdb——之前也是勉强使用过，但是明显感觉不爽阿。。所以这次好好学习，记录一下。 目前我能用到的几个命令： 选择调试文件 <shell>: gdb <file> 或者进入gdb以后，使用 断点 显示断点 (gdb): info break 添加静态断点 (gdb): b[reak] + 行数/函数名 (可以用tab补全) 添加条件断点 条件为真，则在断点处停止 – (gdb): b addr if condition 删除断点 删除编号为1的断点, 如果不加参数，会删除所有断点 – (gdb): delete breakpoint 1 启用/禁用断点 (gdb): disable breakpoint 1 (gdb): enable breakpoint 1 运行 开始运行 (gdb):r 继续 (gdb):c 单步调试 不进入单步执行 – (gdb):n 进入的单步 – (gdb):s[tep 显示变量 以变量为var为例 输出var的值 (gdb):p var 输出上一个求得值 (gdb):p 输出历史记录中值 (gdb):p $[num] 输出变量的类型 (gdb):whatis p 调用函数 (gdb):p add(a, b) 数组 输出a后面的十个元素 [阅读全文]

题意

找出子序列和，因为数字过大，mod 1 000 000 007

[阅读全文]