基本上就是按照大白学习的，基本上都是计数方法的运用。
这是的大体的对组合数学的学习导图。
大白刷题录
UVa 11729
#include <cstdio> #include <cmath> #include <iostream> #include <algorithm> using namespace std; struct Ant { int id; int p; int d; bool operator < (const Ant& a) const { return p < a.p; } }; const int MAXN = 10010; const char dirName[][10] = {"L", "Turning", "R"}; Ant before[MAXN], after[MAXN]; int order[MAXN]; int main(int argc, const char *argv[]) { freopen("input", "r", stdin); int t; int L, T, n; int p, d; char c; scanf("%d", &t); for(int kase = 1; kase <= t; kase++) { printf("Case #%d:\n", kase); scanf("%d%d%d", &L, &T, &n); for(int i = ; i < n; i++) { scanf("%d %c", &p, &c); d = c == 'L' ? -1 : 1; before[i] = (Ant) {i, p, d}; after[i] = (Ant) {, p+T*d, d}; } sort(before, before+n); for(int i = ;i < n;i ++) order[before[i].id] = i; sort(after, after+n); for(int i = ; i < n; i++) if(after[i].p == after[i+1].p) after[i].d = after[i+1].d = ; for(int i = ; i <n; i++) { int a = order[i]; if(after[a].p < || after[a].p > L) puts("Fell off"); else printf("%d %s\n", after[a].p, dirName[after[a].d+1]); } printf("\n"); } return ; } #include <cstdio> #include <cmath> #include <iostream> #include <algorithm> using namespace std; struct Ant { int id; int p; int d; bool operator < (const Ant& a) const { return p < a.p; } }; const int MAXN = 10010; const char dirName[][10] = {"L", "Turning", "R"}; Ant before[MAXN], after[MAXN]; int order[MAXN]; int main(int argc, const char *argv[]) { freopen("input", "r", stdin); int t; int L, T, n; int p, d; char c; scanf("%d", &t); for(int kase = 1; kase <= t; kase++) { printf("Case #%d:\n", kase); scanf("%d%d%d", &L, &T, &n); for(int i = ; i < n; i++) { scanf("%d %c", &p, &c); d = c == 'L' ? -1 : 1; before[i] = (Ant) {i, p, d}; after[i] = (Ant) {, p+T*d, d}; } sort(before, before+n); for(int i = ;i < n;i ++) order[before[i].id] = i; sort(after, after+n); for(int i = ; i < n; i++) if(after[i].p == after[i+1].p) after[i].d = after[i+1].d = ; for(int i = ; i <n; i++) { int a = order[i]; if(after[a].p < || after[a].p > L) puts("Fell off"); else printf("%d %s\n", after[a].p, dirName[after[a].d+1]); } printf("\n"); } return ; }
UVa 11292 勇士斗恶龙
排序，贪心
#include <stdio.h> #include <algorithm> using namespace std; int main() { // freopen("input", "r", stdin); const int MAXN = 20010; int dra[MAXN]; int sol[MAXN]; int m, n; while(scanf("%d%d", &n, &m)) { if(n == m && n == ) break; for(int i = ; i < n; i++) scanf("%d", &dra[i]); for(int i = ; i < m; i++) scanf("%d", &sol[i]); sort(dra, dra+n); sort(sol, sol+m); int i, j, cost; i = j = cost = ; for(;;) { if(i == n || j == m) break; if(dra[i] > sol[j]) j++; else { cost += sol[j]; i++; j++; } } if(i == n) printf("%d\n", cost); else puts("Loowater is doomed!"); } return ; }
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$的中位数。
#include <stdio.h> #include <algorithm> #include <math.h> #define lln long long using namespace std; const int MAXN = 1000000 + 10; lln gold[MAXN], C[MAXN]; int main() { // freopen("input", "r", stdin); lln n, sum, per, cnt; while(~scanf("%lld", &n)) { sum = ; for(int i = ; i < n; i++) { scanf("%lld", &gold[i]); sum += gold[i]; } per = sum / n; C[] = ; for(int i = ; i < n; i++) C[i] = C[i-1] + gold[i] - per; sort(C, C+n); cnt = ; lln x1 = C[n/2]; for(int i = ; i < n; i++) cnt += abs(x1 - C[i]); printf("%lld\n", cnt); } return ; }
LA 3708
这个题目也是比较有水平
使用了按比例缩小的技巧。其中，按逆时针编号，固定一个点作为原点，建立新坐标。原来的位置呈现在新坐标的位置为$pos = i/n*(n+m)$，如此，求移动距离则是$fabs(pos – floor(pos+0.5))/(n+m)$
[阅读全文]ACM-白皮书3
本文出自svtter.github.io
整数进制输出
printf("%d %o %x\n", a);
把整数按照十进制，八进制和十六进制输出.
$2^32-n$补码表示法.
字符处理
使用Ctrl+D时, getchar()读到的是-1
#include <stdio.h> #include <string.h> int main(int argc, const char *argv[]) { char c = getchar(); printf("%d%c\n", c, c); return ; }
假设一个年份为1993/12/12, 那么如何简单获取年月日？
使用sscanf函数.
#include <stdio.h> #include <string.h> int main(int argc, const char *argv[]) { int year, month, day; char s[] = "1993/12/12"; sscanf(s, "%d/%d/%d", &year, &month, &day); printf("%d/%d/%d\n", year, month, day); return ; }
可以使用fgets(s, MAXN, stdin)来获取简单的输入. 一次读入一行，包括空格，遇到\n结束读入
简单习题
- 分数统计
ACM-白皮书-练习
- 本文出自svtter.github.io
基础第二弹
虽然是很水的题目，但是还是收获了不少。
动态小数位数
#include <stdio.h> #include <math.h> int main() { int a, b, c; while(~scanf("%d %d %d", &a, &b, &c)) { printf("%.*lf", c, a/(double)b); } return ; }
整数位数
// 整数位数
int cal(int a)
{
if(a == 0) return 0;
return (int) log10( (double) a)+1;
}
电灯
#include <stdio.h> #include <string.h> #define bool int //C语言没有bool bool light[1010]; //C也没有引用 void trans(bool *a) { if(*a) *a = ; else *a = 1; } int main() { int i, j; int n, k; while(~scanf("%d %d", &n, &k)) { memset(light, , sizeof(light)); for(i = 1; i <= k; i++) { j = i; while(j <= n) { trans(&light[j]); j += i; } } for(i = 1; i <= n; i++) { if(light[i]) printf("%d ", i); } printf("\n"); } return ; }
蛇型填数
#include <stdio.h> #include <string.h> #define bool int //C语言没有bool bool light[1010]; //C也没有引用 void trans(bool *a) { if(*a) *a = ; else *a = 1; } int main() { int i, j; int n, k; while(~scanf("%d %d", &n, &k)) { memset(light, , sizeof(light)); for(i = 1; i <= k; i++) { j = i; while(j <= n) { trans(&light[j]); j += i; } } for(i = 1; i <= n; i++) { if(light[i]) printf("%d ", i); } printf("\n"); } return ; }
调和级数
#include <stdio.h> #include <math.h> double calharmony(int a) { double sum = ; int i; for(i = 1; i <= a; i++) { sum += 1/(double)i; } return sum; } int main() { int a; while(~scanf("%d", &a)) { printf("%.3lf\n", calharmony(a)); } return ; }
题目都很水（不能再水了），但是也算是有所收获。学习了一部分C。
ACM-白皮书
- 本文出自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读取文件输入测试数据
int main() { #ifdef LOCAL freopen("data.in", "r", stdin); freopen("data.out", "w", stdout); #endif }
添加编译选项：-DLOCAL， 使得中间部分生效.
fopen在linux不支持，所以不写了。
ACM-zoj3789-排列利用
- 本文出自<svtter.github.io>
利用排列找规律。
首先利用next_permutation函数进行求排列
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define INF 0x3f3f3f3f int a[30]; int cal(int n) { int sum = ; int i; for (i = 1; i <= n; i++) { /* code */ sum = abs(sum - a[i]); } return sum; } void parray(int a[], int len) { int i; for (i = 1; i <= len; i++) { cout << a[i] << " "; } cout << endl; } void cp(int a[], int b[], int n) { int i; for (i = ; i <= n; i++) { a[i] = b[i]; } } int main(int argc, const char *argv[]) { int i; for (i = 1; i <= 30; i++) { a[i] = i; } int n; int maxa[30], mina[30]; while (~scanf("%d", &n)) { int max = -INF; int min = INF; if (n == 1) { cout << "1 1" << endl; cout << "1" << endl << "1" << endl; continue; } while (next_permutation(a+1, a+n+1)) { /* code */ int temp = cal(n); if (temp >= max) { max = temp; cp(maxa, a, n); } if (temp <= min) { min = temp; cp(mina, a, n); } } cout << min << " " << max << endl; for (i = 1; i <= n; i++) { cout << mina[i] << " "; } cout << endl; for (i = 1; i <= n; i++) { cout << maxa[i] << " "; } cout << endl; } return ; }
代码如上。
可以观察出规律，然后即可AC。
详细代码下次再写= =
AC代码
#include <stdio.h> #include <string.h> #include <cmath> using namespace std; int main() { int i, n; int max, min; while(~scanf("%d", &n)) { max = min = ; for(i = n; i >= 1; i--) min = abs(min - i); for(i = n-1; i >= 1; i--) max = abs(max - i); max = abs(max - n); printf("%d %d\n", min, max); for(i = n; i >1 ; i--) printf("%d ", i); puts("1"); for(i = n-1; i >= 1; i--) printf("%d ", i); printf("%d\n", n); } return ; }
规律在代码中，很明确。
筛素数更正
- 本文出自<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，也就是整个范围都会包含在内。
代码：
memset(Prime, , sizeof(Prime)); memset(IsPrime, 1, sizeof(IsPrime)); for(i = 2 ; i <= n; i++) { if(IsPrime[i]) Prime[num++] = i; for(j = ; j < num && i * Prime[j] <= n; j++) { IsPrime[i * Prime[j]] = ; if(i % Prime[j] == ) break; } }
之前的错误在于筛素数的时候没有筛去2的倍数，所以出现后面的值错误。
ACM – hdu5104-water
这个题目的总结就是不作不会死- -好端端的暴力我非要用个bfs。
看见自己wrong了还以为是哈希的问题- =
题意
- p1+p2+p3 = n，$p1 <= p2 <= p3$
- 输出符合条件的组数
输入输出
- 给100组n，输出组数
分析
- 只有3个数，暴力解就可以，注意循环终止条件。
使用gdb调试
最近都是用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后面的十个元素
[阅读全文]