分类:: C++

0

「LCA」最近公共祖先模版

前些日子学了LCA,觉得RMQ写法很玄学,而我喜欢玄学的东西,所以在我还没有完全写明白RMQ的LCA时,就先补充一下RMQ解决LCA的思路,但是不用RMQ那么玄学的维护方式,以POJ 1330举例子: Nearest Common Ancestors Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 31596

0

「RMQ」区间最值问题详解

区间最值问题是用来解决问一个固定区间内多次询问某个子区间最值的快速算法。 那么我们先来说一下RMQ问题的比较快的算法—— ST(Sparse Table)算法是一个非常有名的在线处理RMQ问题的算法,它可以在O(nlogn)时间内进行预处理,然后在O(1)时间内回答每个查询。 首先是预处理,用动态规划(DP)解决。设A[i]是要求区间最值的数列,F[i, j]表示从第i个数起连续2^j个数中的最大

0

「二叉树」二叉树详解

引入——动态链表链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接 一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。 链表最基本的结构是在每个节点保存数据和到下一个节点的

0

「置顶文章」代码仓库 Codes Repo

code’s RepoLuogu 2661 code: #include <iostream> using namespace std; int a[200005],ru[200005],tmp,n,ans=99999999; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d

0

「置顶文章」联赛前的日记

Pre Info题库联赛题:(看下面总结) Easy Mid Hard 无线网络发射器选址AC 花匠(背包) 借教室AC 生活大爆炸AC 摆花(背包)AC 关押罪犯 表达式求值AC 信息传递(暴力)AC mayan游戏 比例简化AC 联合权值(暴力)AC 斗地主 文化之旅(最短路)AC 子串 推销员 运输计划 难题:UVa1635(数论) AC Hanks

0

「最短路」Dijkstra算法模版

Dijkstra算法配合不同的存图方式时间复杂度从O(N²) ~ O(NE),加上优先级队列(堆)的优化能降到O((m+n)logn),那么这篇我列举出一些模版代码,仅供参考。但是我还是更喜欢用SPFA… Dijkstra & 邻接矩阵存图模版: #include <iostream> #include <cstdlib> #include <cstring> using

0

「搜索 & 精度」Luogu 1378 油滴拓展

前言写这篇博客,我真的很荣幸!看了看时间,现在是2017年11月7日 BJS 22:32,为什么这么说呢,我从今天下午19:40时和机房小伙伴们语音聊天,准备做一下传说中的萌新到大佬的巨大门槛(伪)——油滴拓展,传说中的调试9 hours也不是闹着玩的。有幸的是,这道题思路上没什么门槛,就是全排列,然而需要在精度上格外注意。其实double就可以了,还有很多流传的π=3.14就会WA(果然WA 3

0

「读入优化」关于读入的几个测试

测试环境: 操作系统: macOS High Sierra 10.13.1 编译器: g++ 4.2.1 CPU: 2.7 GHz Intel Core i5-5250U //g++版本说明 ➜ Desktop g++ -v Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-

0

「搜索」RQNOJ 73 24点

RQNOJ 73 题目链接 题目描述superwyh是一个非常疯狂的24点爱好者,空闲时总是自己拿出扑克来算24点,24点的规则很简单,就是给你4张扑克(从1至13,用A代替1,J代替11,Q代替12,K代替13)通过加减乘除来求得24,各位oier帮了superwyh好多忙,为了报答大家superwyh就和大家做个24点的游戏,superwyh给大家4张牌大家告诉superwyh能不能凑成24就

0

「动态规划 & LIS」BZOJ 1207 打鼹鼠

Description鼹鼠是一种很喜欢挖洞的动物,但每过一定的时间,它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏:在一个n*n的网格中,在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠,如果i时刻鼹鼠在某个网格中出现,而机器人也处于同一网格的话,那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当

0

「二分答案 & 贪心」BZOJ-1816 扑克牌

CQOI-2010 扑克牌Description你有n种牌,第i种牌的数目为ci。另外有一种特殊的牌:joker,它的数目是m。你可以用每种牌各一张来组成一套牌,也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如,当n=3时,一共有4种合法的套牌:{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci,你的任务是组成尽量多的套牌。每张牌最多只

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 的材料。为了能节省体力来完成他的礼物,小阎想找聪明的你帮他算一算他所要花费的最小体力。 输入输出格式输入格式: