ray58750034-CSDN博客

原创攻城狮都应当知道的——编译器的工作过程

源码要运行，必须先转成二进制的机器码。这是编译器的任务。比如，下面这段源码（假定文件名叫做test.c）。#include int main(void){ fputs("Hello, world!\n", stdout); return 0;}要先用编译器处理一下，才能运行。$ gcc test.c$ ./a.outHello, world!对于复杂的项目，编译

2015-01-02 23:36:23 546

原创蜜蜂的问题

蜜蜂的问题作者: Ray 日期: 2006年11月3日，星期五 99年ACM/ICPC 的final有一道蜜蜂的坐标的问题，非常有意思，和队友们讨论了许久都没能解决。记得那天做练习是我和肖筹划着用计算几何的方法估算出结果，虽然做法很独特，但毕竟是估算的，最后没有能过。后来我找了份解题报告，看到了解这类问题的神奇地使用笛卡儿坐标，着实让人兴奋啊。所以准备了一份模板、数道

2006-11-04 10:26:00 3072 1

原创 10/22日上大程序设计联赛裁判日记

10月22日晴，昨天下过雨，所以今天还是比较凉爽，是个编程比赛的好天气。这是第一次做裁判，满有趣的，虽然比赛中出过小叉子（tomcat被关掉了），但总归还是挽救了回来。题目是Larva三个赶着写出来的-_-0。Ray和Leaderz还是比较勤恳的，花了一个整天分别出了4道和3道。 Leen就有点~~比赛前一天晚上赶到2点多才赶了两道。Problem A: PageReplacement Algo

2006-11-02 19:58:00 1402 1

原创关于“逆序数”

昨天我们做了清华的预选赛，沈大、梁老大、肖叉各搞定一道题，险些跌出60名。我做了B和F，其中F是关于逆序数的题目，复杂度是 nlog2n+mn 最差的复杂度可能降为O(n^2)。但我提交的结果不是TLE，而是MLE和RE。真不知道是清华判题系统有问题还是我的程序有问题。总之，我心有不服啊，所以决定今天花点时间归纳一下“逆序对”的题目，给大家写份报告，提供点资料。首先，逆序对（inversion

2006-10-08 14:49:00 14462 3

原创 PKU 2893 M × N Puzzle 的优化

M*N PUZZLE类似与八数码问题，其实这个问题满热门的，而且有着很多的扩展。题目中说道N 与 M中有一个为奇数，那么自然就想到了用逆序对数可以解决这个问题，其简单的证明在以前写过个八数码报告里就有：（注：将空格去除，只考虑有数字的格子） 1 对于左右移动是不影响整个序列的逆序的。 2 对于奇数列的PUZZLE，做上下移动无异与左右移动偶数个位置，至少不会

2006-09-05 00:49:00 2704

对于约瑟夫问题，今天看到了一篇好帖子，是用数学方法处理的，感觉还不错的无论是用链表实现还是用数组实现都有一个共同点：要模拟整个游戏过程，不仅程序写起来比较烦，而且时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。我们注意到原问题仅仅是要求出最后的胜利者的序号，而不是要读者模拟整个过程。因此如果要追求效率，就要打破常规，实施一点数学策略。为了讨论

2006-08-24 02:16:00 3887 4

原创 Southwestern Europe 2005 ——解题报告

Southwestern Europe 2005 ——解题报告序：复旦的教练给了我们一次听ACM讲课的机会，课的进度太快，也没听懂多少，所以问牛人们敲了一套题来做做，就是本文的标题SWERC05的题目。题目难度中等略上吧，不过题目数量很多，有10道（吓）。后面的几道题目满有搞头的。 A The mysterious X network：求最短路径的简单题，因

2006-08-17 11:12:00 2159

原创《炮兵阵地》解题报告

《炮兵阵地》解题报告Description司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用"H" 表示），也可能是平原（用"P"表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色

2006-07-21 07:51:00 4723 4

转载动态网络页面和AJAX技术

动态网络页面和AJAX技术文 / 李涛　　传统的网络页面是一个个的HTML文件，其内容在不刷新整个页面的情况下将不会改变。可能有读者会问，网络页面能否做得像桌面程序一样，具有丰富、适时的人机交互功能呢？如果读者用过Google Map、Google Suggest或GMail，可能就会意识到我们离这个时代已经不远了。现在炒得很热的Web 2.0概念，其实说白了就是使桌面运用网络

2006-06-13 23:48:00 1735

原创 TopCoder SRM305 DIV1 Report

TopCoder SRM305 DIV1 Report match date：Wednesday, May 31, 2006 report date：Sunday, June 4, 2006 Preface: 看题不仔细，算法不扎实，总之仍需再虚心学习学习再学习。 Contents Preface: Contents: Proble

2006-06-04 19:39:00 1242

原创 TOJ 2006 Weekly Contest 1 报告

TOJ 2006 Weekly Contest 1 报告Preface: 嘿嘿、感觉好爽呀，做了5道题目，拿了个第7（算是银牌？呵呵）。先是我去拉人一起来做，结果没一个人理我-_-0 ，后来我自己搞，搞了3道，肖叉进来陪我一起做，把最后两道解决了。整体上难度不高，没有特别神奇的算法和技巧出现。训练一下满好的。A. Magic Sticks Again 第四个过的，原

2006-05-21 00:17:00 1523

原创 TopCoder SRM301 DIV1 Report

TopCoder SRM301 DIV1 Report match date：Tuesday, May 9, 2006 report date：Thursday, May 11, 2006 Preface: 好久没做TOPCODER了，主要是因为SRM的时间都不好，大都在我有课或有事的时候，这次有机会做一次感觉满提神的，特别是这次有幸和Petr在一组！总共

2006-05-16 18:03:00 2606 1

转载三篇关于“Chomsky normal form”的文章

Chomsky normal formFrom Wikipedia, the free encyclopediaJump to: navigation, searchIn computer science, a formal grammar is in Chomsky normal form iff all production rules are of the form: A → BC o

2006-05-15 22:47:00 1610

原创读《图算法，Robert Sedgewick》笔记 —— 最短路径

读《图算法，Robert Sedgewick》笔记 —— 最短路径最短路径（Shortest Path）是在实际应用中非常有用的工具，将该问题细分，可以分为点到点最短路径（source-sink），单源点的最短路径（single-source），所有点到所有点（all-pairs）以及带负边情况下的最短路径。为了简化我们的问题，设置以下几个限制：

2006-05-09 22:26:00 6304

原创读《图算法，Robert Sedgewick》笔记 —— DFS特性

读《图算法，Robert Sedgewick》笔记 —— DFS特性 DFS（Depth-First Search）就是我们常说的深度优先搜索（深搜）。他的基本搜索方式这里暂不讨论，就《图算法》中对于DFS的特性分析做一下笔记，表达一些个人的观点。无向图：首先是DFS所用到的一些表示：我们用两个数组分别记录访问结点的序列和每个结点在搜索树中的父结点，以ord 和 st表示

2006-04-22 19:43:00 3809 1

原创再谈jGraph

再谈jGraph组概念在图的表示中，有时我们需要描述一组有相关特性的点或线，这时，引入组的概念。组由一组Cell组成的，而组本身也是一个Cell。也就是说jGraph用了父与子的树型结构描述了组和组中的成员的关系。这样，对于组的操作就可以像对一般的单元（点、线、port）一样了，即拖动、放大/缩小等等。 jGraph提供了一组丰富的API来建立组和成员的关系，包括对某GraphC

2006-04-18 16:42:00 2068

原创 TopCoder SRM296 DIV1 Report

TopCoder SRM296 DIV1 Report match date：Monday, April 3, 2006 report date：Monday, April 10, 2006 Preface: 该好好反省了，在DIV1始终还是不能有好的表现。这次靠几个数据Challenge了几个代码，但题目还是没能做出来，看来水平还是不济啊。 Probl

2006-04-17 18:50:00 1120

转载拈及其各種變形遊戲

拈及其各種變形遊戲張鎮華(一)拈 (Nim) 這種遊戲就像物理的不共容原理一樣，數學遊戲的趣味性和其數學理論的完整性，成為互相排斥的兩部份。一種遊戲完全被數學決定以後，玩的人只要曉得其中的理論，無不處於優勢。遊戲本身則成為數學的計算，玩起來必索然無味；但如果將它視為數學問題處理，則蘊藏有甚多美妙的理論在其中。富有挑戰性的遊戲，則沒有固定的規律可尋，必須隨機應變，靠臨場的機智和

2006-03-29 10:43:00 1856

原创 TopCoder SRM294 DIV2 Report

TopCoder SRM294 DIV2 Report match date：Saturday, March 25, 2006 report date：Tuesday, March 28, 2006 Preface: 好可惜呀，这次的比赛是有奖金可拿的，但我没能排上前两名，区居小三。这次我和肖叉一起做的，感觉他很浮躁，不跟我搞配合就算了，还老是影响我。最后他的第

2006-03-28 14:06:00 1137

转载欧拉函数公式

pk的欧拉函数对于给定的一个素数p，我们知道Φ(p) = p-1。假设一个整数n是p的k次幂，也就是 n = pk k∈N+容易证明 Φ(n) = pk - pk-1 证明：已知少于小于pk的正整数个数为pk-1个，其中和pk不互质的正整数有{p×1,p×p2,...,p×(pk-1-1)}共计pk-1-1个所以

2006-03-27 14:02:00 5386

原创初识jGraph

初识jGraph序在为老师写项目的时候我急需一个基于java的图形组件，第一次搜索就搜索到了jGraph。总体感觉还是挺容易上手的，是一套能够应对多种图形用途的工具。虽然我对其中一些编程的风格有些不是很满意。不过能做出来就是好的！而且效果十分出色，感谢jGraph社团带给我们的强大工具。最令我欣赏的是，jGraph在对需要使用jGraph Layout Pro的

2006-03-26 00:50:00 4918

原创 Greater New York 2005 部分解题

Greater New York 2005 match date：Friday, March 3, 2006 report date：Wed

2006-03-22 14:03:00 2357

原创 Solari10（JDS）中使用GDM登录界面

最近新装了solaris10系统，真是不错呀。首先界面是满豪华的，而且反应速度算是快的了（至少比federa要快）。最大的缺点一个是相容软件偏少，就连eclipse都没有x86下的solaris版本，搞了好久才把基本的软件环境配置好。缺点二是不太习惯，SystemV的还是第一次用。总得来说，优点要远远多于缺点，在这就不唠叨了。几天下来，每次开机都是在用默认的

2006-03-12 20:13:00 1679

原创整数匹配问题（DP）

今天是ACM课的小测验（也许称不上小测验），因为上大关心ACM的人实在太少了。一共有四道题目，三道是很简单的题目，最后一道比较经典的，有点曾经做旅行商问题时候的感觉。测试时，我自己并没有写出来，只是觉得是DP的方向，后来在老师的提示下通过了。题目如下：整数匹配Description 有两行正整数，第一行与第二行中相同的

2006-03-02 22:02:00 1146

原创解题报告：Cube Stacking

解题报告：Cube Stacking关键字：ACM/ICPC，解题报告，并查集，路径压缩题目大意有最多30000个标有标号的小方块，输入最多100000次操作，其中每次操作包括以下两种： M x y 将含x的方块堆堆到含y的方块堆上去 C x 计算标号x的方块的下方有多少方块说明：不会有这样的操作， M x y

2006-02-22 18:42:00 2004

原创 TopCoder SRM289 DIV2 Report

TopCoder SRM289 DIV2 Reportmatch date：Tuesday, February 14, 2006 report date：Friday, February 17, 2006Preface: 好也！在DIV2 拿了第一，虽然DIV2难度比较低，但是也算有小突破了。可惜的是因为加分实在太少，所以还是只能以1180分继续在DIV2打拼。 DIV2的

2006-02-22 16:16:00 1083

原创八数码实验报告

八数码实验报告问题简介：所谓八数码问题是指这样一种游戏：将分别标有数字1，2，3，…，8的八块正方形数码牌任意地放在一块3×3的数码盘上。放牌时要求不能重叠。于是，在3×3的数码盘上出现了一个空格。现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则，将任意摆放的数码盘逐步摆成某种特殊的排列。如下图表示了一个具体的八数码问题求解。问题分析：首先，八数码问题包

2006-02-15 22:48:00 11873 4

转载 Two Dimensional Convex Hull

Two Dimensional Convex Hull 二维凸包译 by Felicia Crazy (QQ 125376968 MSN felicia1101@hotmail.com )准备知识几何学数学模型给出平面内的点集，找出面积最小的凸多边形，使得这些点在这个多边形之内（或者在它的边上）。可以看出，多边形的顶点必须是给定点

2006-02-11 21:15:00 1699 1

原创 TopCoder SRM288 DIV1 Report

TopCoder SRM288 DIV1 Reportmatch date：Wednesday, February 8, 2006 report date：Friday, February 10, 2006Preface: 也许是第一次成绩太好了，第二次被分到了div 1 组，才发觉自己的水平真得不济。只能有时间coding两道题目，而第二题因为没把握所以没提交。第一题也没通过s

2006-02-11 12:24:00 1152

原创 TopCoder SRM287 DIV2 Report

TopCoder SRM287 DIV2 Reportmatch date：Saturday, February 4, 2006report date：Thursday, February 09, 2006 Preface: 这是第一次参加TopCoder，手法比较生疏。虽然三题都是赶在结束前提交的，但准确率很低，所以不但给了别人一次challenge，而且System test

2006-02-09 09:28:00 1060

转载 A*算法及其应用 -------98计算机邹飞（98132194）

一．引言图论是计算机科学中的一个重要研究工具，它产生于欧拉（Euler）对图的连通性的研究，但直到本世纪计算机诞生以后才得最迅猛的发展。图论中的最短路径问题在计算机中有着广泛的应用，例如网络通信中最短路由的选择，人工智能中搜索算法的研究等。本文对几种常见最短路径的算法进行介绍，尤其是在1968年发展起来的A*算法。二．常用算法简介为叙述的方便，本

2006-02-05 21:03:00 1975

转载深入A算法 ----浅析A算法在搜索最短路径中的应用

　　在这里我将对A*算法的实际应用进行一定的探讨，并且举一个有关A*算法在最短路径搜索的例子。值得注意的是这里并不对A*的基本的概念作介绍，如果你还对A*算法不清楚的话，请看姊妹篇《初识A*算法》。　　这里所举的例子是参考AMIT主页中的一个源程序，你可以在AMIT的站点上下载也可以在我的站点上下载。你使用这个源程序时，应该遵守一定的公约。 1、A*算法的程序编写原理　　我在《初识A*

2006-02-05 12:24:00 1120

转载初识A*算法

写这篇文章的初衷是应一个网友的要求，当然我也发现现在有关人工智能的中文站点实在太少，我在这里抛砖引玉，希望大家都来热心的参与。　　还是说正题，我先拿A*算法开刀，是因为A*在游戏中有它很典型的用法，是人工智能在游戏中的代表。　　A*算法在人工智能中是一种典型的启发式搜索算法，为了说清楚A*算法，我看还是先说说何谓启发式算法。一、何谓启发式搜索算法　　在说它之前先提提

2006-02-05 12:14:00 928