归档: 2017/8

0

「离散化」简单好用的一种数学模型处理思想

简介什么是离散? 我们好比在看地图时,放大或缩小时候的一种放缩感,换句话说,就是把一个巨大的空间中的数据映射到唯一一个小的编号中(哈希Hash),离散主要提高了空间利用率,降低时间,可谓一举两得,写起来也很方便,但是不是所有数据都能或者说都值得离散化的。我们看一下POJ-2502 Subway这道题的存图,显然他需要坐标进行计算得到距离,如果离散的话,那么就会导致距离错误。而Vijos 1056就

0

「带权并查集」Vijos-1540 月亮之眼

描述吉儿是一家古董店的老板娘,由于她经营有道,小店开得红红火火。昨天,吉儿无意之中得到了散落民间几百年的珍宝—月亮之眼。吉儿深知“月亮之眼”价值连城:它是由许多珍珠相连而成的,工匠们用金线连接珍珠,每根金线连接两个珍珠;同时又对每根金线染上两种颜色,一半染成银白色,一半染成黛黑色。由于吉儿自小熟读古籍,所以还晓得“月亮之眼”的神秘传说:“月亮之眼”原是一个古代寺庙的宝物,原本是挂在佛堂的一根顶梁柱

0

「带权并查集」洛谷-P1196 银河英雄传说

题目描述公元五八零一年,地球居民迁至金牛座α第二行星,在那里发表银河联邦创立宣言,同年改元为宇宙历元年,并开始向银河系深处拓展。 宇宙历七九九年,银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征,气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。 杨威利擅长排兵布阵,巧妙运用各种战术屡次以少胜多,难免恣生骄气。在这次决战中,他将巴米利恩星域战场划分成

0

「最短路」POJ-2502 Subway-SPFA和建图

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10980 Accepted: 3589 DescriptionYou have just moved from a quiet Waterloo neighbourhood to a big, noisy city. Instead of getting to

0

「动态规划」01背包问题详解

引入什么是背包问题,按照顺序,我们先从装箱介绍: 装箱问题 有个一箱子的容量额为V(0<=V<=20000),同时有n个物品 (0<n<=30),每个物品的体积值为正整数。 要求从n个物品中,选取若干个装入箱内,使箱子的剩余空间最小。 输入2行整数,第1个数表示箱子的容量V,第2个数表示有n个物品,下一行n个数据表示n 个物品各自的体积。 输出背包剩余体积。 分析贪心?或

0

隆重推出Ex10si0n的Coding实验室 2.0

新2.0版本!大家久等了!经过几个小时的赶制,新版本的Coding实验室隆重推出 为了能够让大家对本站更加喜欢,我准备在9月1日开学前更新本站,在此之前访问本站不受影响,初步预计时间:8月15日前正如我疯掉了一般,终于在8月6日晚,新版本与大家见面了,大家可以品尝到新版本的新的UI设计和风格(当然如果喜欢之前的和风可以建议我回滚哦)本人认为上一个版本有很大缺陷,以及风格的设定看起来有一些简陋(不可

0

「图论」SPFA单源最短路径算法

最短路径算法首先感谢GGN的博客带来精彩的最短路讲解,让我受益匪浅! 目前的最短路算法有几种: Floyed-Warshall $O(n^3)$ Dijkstra $O(n^2)$ SPFA $O(KE) K<=2$ 那么这几种最短路的求法在GGN博客也已经有所讲解,今天我就来讲解一下SPFA算法,我们用SPFA如何来求单源最短路径(就是一个源点求到每个点的最短距离) SPFA

0

「图论」SPFA优化算法

误删,尴尬昨天搞到很晚的SPFA优化一不小心被今天的POJ1860覆盖了,我只好再码一遍,昨天转了某位大神的博客,很好的解释了SPFA,凭我的记忆,还有NOCOW上的码起来的链接:NOCOW,以及超棒的注释代码: /* * 单源最短路算法SPFA,时间复杂度O(kE),k在一般情况下不大于2,对于每个顶点使用可以在O(VE)的时间内算出每对节点之间的最短路 * 使用了队列,对于任意在队列中的点

0

「转载」Markdown语言用法说明

NOTE: This is Simplelified Chinese Edition Document of Markdown Syntax. If you are seeking for English Edition Document. Please refer to Markdown: Syntax. 声明: 这份文档派生(fork)于繁体中文版,在此基础上进行了繁体转简体工作,并进行了适当

0

「位运算」N皇后问题

位运算可以很大程度上提高运算效率,而且还会有神奇的效果,下面我们用位运算来解决n皇后问题: 我们先声明一些变量 int n; //不解释了 —— n皇后中的 n int upperlim=(1<<n)-1; //终止状态 int row,ld,rd; 在这里强调一下:upperlim=(1<<n)-1对于n=4时,它的二进制值为1111(n个1),现在我们把状

0

「并查集」HDU 1232 畅通工程

「并查集」HDU 1232 畅通工程Problem Description某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路? Input测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N (