主页

0

「二分判断」BZOJ-1196 公路修建问题

[HNOI2006]公路修建问题DescriptionOI island是一个非常漂亮的岛屿,自开发以来,到这儿来旅游的人很多。然而,由于该岛屿刚刚开发不久,所以那里的交通情况还是很糟糕。所以,OIER Association组织成立了,旨在建立OI island的交通系统。 OI island有n个旅游景点,不妨将它们从1到n标号。现在,OIER Association需要修公路将这些景点连接起

0

「数论」启发式思路——fac数组存大整数

关于——为什么要写这个我们都用过杨辉三角递推式生成过杨辉三角,可是往往时间效率只能达到n<=5000,在学习完二项式定理之后得知一种新的直接递推第n行的杨辉三角数的公式 数组表达形式:line[n][x]=line[n][x-1]*(n-x+1)/x 终于可以O(n)求组合数了! 但是别高兴的太早,实测在不取模的情况下n=30就会爆int,而我们知道: (a+b)mod n=((a mo

0

「拓扑排序」Topo_Sort 模版

生成拓扑序-模版对于一个DAG,统计入度,入度先从入度为0的结点开始,将其入队,然后删去这个节点的所有出度,并维护整个区间的新的入度in_degree[],循环操作此过程,最后生成的ans[]即为生成的拓扑序。 #include <iostream> #include <queue> #include <cstdio> using namespace std; int edg

0

「拓扑排序」POJ-1094 Sorting It All Out

Sorting It All Out题目传送门 https://vjudge.net/problem/POJ-1094 没改完的code //topologial order //存图记录 入度 出度 //队列维护 #include <iostream> #include <queue> #include <cstdio> #include <cstring> using

0

「二分 & 二分图染色」NOIP 2010提高组 & 洛谷P1525 关押罪犯

题目描述S 城现有两座监狱,一共关押着N 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件。 每年年末,警察局会将本年内监狱中的所有

0

「Floyed & 高精度」NOIP 2002普及组 & 洛谷P1037 产生数

题目描述给出一个整数 n(n<10^30) 和 k 个变换规则(k<=15)。 规则: 一位数可变换成另一个一位数: 规则的右部不能为零。 例如:n=234。有规则(k=2): 2->5 3->6 上面的整数 234 经过变换后可能产生出的整数为(包括原数): 234 534 264 564 共 4 种不同的产生数 问题: 给出一个整数 n 和 k 个规则。 求出: 经过任

0

「区间dp」育才高中部信息学模拟赛 9.25 T3 男神的礼物

题目背景小阎有一个祝福信物,他希望使大家都会得到女神的祝福。所以他准备给每个人送一份祝福礼物。 题目描述为了准备一份礼物,他要加工 n 份材料,并且每一次只能加工相邻的材料。当小阎 加工两个魔法值为 a,b 的材料,他都要消耗 a*b 的体力,同时在这个地方合成出魔法值(a+b)%100 的材料。为了能节省体力来完成他的礼物,小阎想找聪明的你帮他算一算他所要花费的最小体力。 输入输出格式输入格式:

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

「今天不写算法系列」Secret base~君がくれたもの~ 怀着美好的回忆...

童年的友情,人物间微妙的情感,即使成长也无法抹去,但却都偷偷藏到心底,表面成了陌生人。 我们仍未知道那天所看见的花的名字可能是因为催泪TOP10的缘故,补了这个番。 虽说没看完,额就看了第一集,可是这个不是任何作品改编的动漫的确还是很好的。 然后我爱上了ED。 君がくれたもの 真心推荐这个ED,虽说应该好多好多人都知道了。额,懒得加播放器API了,自行链接吧。 网易云链接 歌词 (汉字+假名)君(

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 个物品各自的体积。 输出背包剩余体积。 分析贪心?或