分类 ACM/ICPC 中的文章

ACM – 快速生成测试数据

比赛的时候出现了100 * 100组数据的情况,但是当时使用freopen忘记了具体的步骤,特意重新写一下,也是属于基础的内容。 生成一百行数据,每行100个数据,每个数据为100。 运行过后生成的数据(本来应该输出在屏幕上,此时不会输出到屏幕,而是输出到文件)会保存到output文件中。如果需要使用直接更改output的文件名,再使用一次freopen('r')即可。……

阅读全文

大白刷题录

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的对应关系。……

阅读全文

ACM-白皮书3

本文出自svtter.com 整数进制输出 把整数按照十进制,八进制和十六进制输出. $2^32-n$补码表示法. 字符处理 使用Ctrl+D时, getchar()读到的是-1 假设一个年份为1993/12/12, 那么如何简单获取年月日? 使用sscanf函数. 可以使用fgets(s, MAXN, stdin)来获取简单的输入. 一次读入一行,包括空格,遇到\n结束读入 简单习题 分数统计 ……

阅读全文

ACM-白皮书-练习

本文出自svtter.com 基础第二弹 虽然是很水的题目,但是还是收获了不少。 动态小数位数 整数位数 电灯 蛇型填数 调和级数 题目都很水(不能再水了),但是也算是有所收获。学习了一部分C。……

阅读全文

ACM-白皮书

本文出自svtter.com 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不支持,所以不写了。……

阅读全文

ACM-zoj3789-排列利用

本文出自<svtter.com> 利用排列找规律。 首先利用next_permutation函数进行求排列 代码如上。 可以观察出规律,然后即可AC。 详细代码下次再写= = AC代码 规律在代码中,很明确。……

阅读全文

筛素数更正

本文出自<svtter.com> 写在之前 maker关于线性筛素数的论文。 做到欧拉线性筛法再做补充。(当时还写了个这?) 关于线性筛素数 之前一直没有正视线性筛素数的问题。今天特意来写一个伪证明。如果当前的i不是素数,那么必然被之前的某个素数筛掉了。i × prime[j]。 一个合数必然可以写成几个素数的乘积,再或者就是p×i这种形式。如果能被i×p1筛掉之后则不需要i×p2继续筛了,i×p2可以写成p1×(i×p2) 例如12可以被6×2筛掉,之前4×3这种筛除就可以去掉。 这种方法会不会存在没有筛掉的合数? 不可能:i会一直到n,也就是整个范围都会包含在内。 代码: 之前的错误在于筛素数的时候没有筛去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为例……

阅读全文