归档: 2017/10

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每星期即可以生产