跳至正文

技术

USACO 3.2.6 Sweet Butter 香甜的黄油 解题报告

这题一开始我用的那个O(n^3)的算法，叫什么名字我忘了，肯定是超时了咯，因为图是稀疏图，这样是肯定超时的，后来就看标称，看了好久，真没想到标称竟然如此精妙，里面设计了一个能够以O(1)的速度查找元素的功能，整个程序是执行了至多n次Dijkstra算法，然后我在里面增加了一些优化（几乎和时间无关的优[……]

继续阅读

奖学金 解题报告

这是个水题，我直接使用了库函数qsort进行了排序，然后输出前五个就可以了，唯一想要说的就是明天或后天把Glibc中的qsort代码看下，学习一下是怎么对超级巨大的数据量进行快速排序的，一个个交换肯定不是，这些都明天再说吧。

#include <stdio.h>
#include &lt[......]
继续阅读

2^k进制数 解题报告

这题困扰了我好几天，详细看了别人的题解，自己反复琢磨，终于琢磨透了。
把我的思路讲一下，f[i][j] 表示第i位(从右向左数, 如12中的1是第二位)，则很容易得到一个DP：
f[i][j] = f[i – 1][j + 1] + f[i – 1][j + 2] + f[i – 1][j + 3][……]

继续阅读

Glibc 的 strcmp

  • 技术

Glibc的设计确实巧妙的让人想不到，如下strcmp的代码就十分巧妙：

C语言: Codee#12462

int
strcmp (p1, p2)
 const char p1;
 const char p2;
{
 register const unsigned char s1 = (const[......]
继续阅读

快速成法

  • 技术

　　当x乘以n的时候，一般人使用的是mul指令（即直接相乘），而我会使用位运算来优化这些速度，比如乘以3，就等于((x << 1) + x)，相当于2x+x 就是3x了，然而这后者的速度比前者的速度快很多。
　　乘以3只是一个情况，乘以n的话，就要把n拆分成2的次方相加，更一般地，就是把n[……]

继续阅读

快速置零 xor %eax, %eax

  • 技术

　　在<<Linux 内核完全注释>>里面看到了几次xor ax, ax，很想不通，为什么不直接用mov ax, 0呢？今日到网上一搜才知道，我的天啊，xor ax, ax 只需要计算机2条指令，而mov ax, 0会消耗计算机5指令，什么意思？就是近三倍的速度差别。

[……]

继续阅读

USACO 3.1 Shaping Regions 形成的区域 解题报告

这题二话不说, 用map[i][j]表示坐标为i, j的点是什么颜色的.. 很快就写出来了, 但是内存超过了,, 内存最多16MB.
没办法, 只好另辟思路, 但是在数据压缩方面我又很弱, 就看标程也花了两三天的时间, 今天终于是看懂了..
用rect记录所有矩形的坐标以及相应的颜色.
程序具体的步[……]

继续阅读

USACO 3.1 Humble Numbers 丑数 解题报告

从这一题开始,, 以后题目我就不贴上来了… 自己去看吧..

这一题开始肯本看不懂,, 后来是反反复复看标程看懂了..

首先要理解这么一个式子吧(算是式子吧“)

已经求出了j-1个丑数,, 现在求第j个丑数

对于每一个素数p乘以一个最小的丑数, 能使积大于第j-1个丑数

在这些乘积中寻[……]

继续阅读