跳至正文

技术

NOIP 过河 解题报告

这题我不怎么说吧，我在网上搜的，到现在为止为什么能这样我还是没想通，只知道这样能过。
就当是个定理吧，记住就是了，这题我不太想解释，看代码吧：

#include <stdio.h>
#define INT_MAX 200000000
int stone[100];
int map[919[......]
继续阅读

Glibc 中的 memset

  • 技术

Glibc的效率真的快！快到让我想不到！！！
这个memset跑的贼快~！不过我还是没想通，为什么不用汇编呢？sep movw，速度可能更快!
对memset的注释如下：

C语言: [Codee#12483](http://fayaa.com/code/view/12483/)

void *mem[......]
继续阅读

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记录所有矩形的坐标以及相应的颜色.
程序具体的步[……]

继续阅读