分类:: C++

0

「优先级队列」codeVS-6130 布丁

###题目描述 Description FJ建立了一个布丁工厂。在接下来的N(1<=N<=40,000)个星期里,原料牛奶和劳动力的价格会有很大波动。FJ希望能够在满足消费者需求的前提下尽量减小花费。 FJ预计接下来每个星期会需要Ci(1<=Ci<=5,000)元钱来生产一单位布丁,且消费者会需要Pi(0<=Pi<=10,000)单位布丁。 FJ每星期即可以生产

0

「图论」数据结构常用存图方式

数据结构常用的存图方式在我和YHS大佬讨论半天存图方式之后,我更加坚信用我的习惯 vector<int>G[maxn] 的方式存图。(%%% YHS 大佬的 list 表存图) 结构 我们观察这张不完全的图,运用到vector的不定场性质,可以大大缩减了数据规模,但是要注意G中要用到edge(自定)类型。 代码如下: #include <iostream> #include &l

0

「GDB」gdb调试以及其他命令大全

命令大全调用调用gdb编译需要在cc后面加 -g参数再加-o; [root@redhat home]#gdb 调试文件:启动gdb 调试(gdb) l :(字母l)从第一行开始列出源码 (gdb) break n :在第n行处设置断点 (gdb) break func:在函数func()的入口处设置断点 (gdb) info break: 查看断点信息 (gdb) r:运行程序 (gdb) n:单

0

「笔记」联赛前要掌握的算法

今天借着机会总结一下必刷题和算法 二分基础:NOIP 2012 借教室NOIP 2011 聪明的质检员POJ 3258POJ 3122NOIP 2010 prisonPOJ 3579 median POJ 3104POJ 2002POJ 2456POJ 3432 难题:POJ 2282 消防1271 教学评估POJ 2002 median priority queue布丁 难题:积水LA 3135

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

「图论」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

「位运算」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 (

0

「算法」康托展开

在此之前我对此的描述: 生成第n个全排列的X(Sn)函数值的一种运算方式 换句话说,就是保证每一种全排列都有自己固定的值。 以下是GY大神的解释: 好的,那我就这样理解吧! 康托展开对于康托展开的表达式 X(Sn)=an*(n-1)!+an-1*(n-2)!+…+ai*(i-1)!+…+a2*1!+a1*0! 看起来有可能会感觉头疼,但是我们只需要记住这种计算方法即可。 那么我们开始说

0

「算法」归并排序

「算法」归并排序基础算法二路归并排序是归并排序的一个过程,可以用这种思想处理空间要求比较大的题目,以防止超时。以下是归并排序的思想: #include<iostream> #include<cstdio> using namespace std; int a[100]={0,10,20,30,40,50}; int b[100]={0,11,15,22,60}; int c[100];