- 博客(127)
- 资源 (6)
- 收藏
- 关注
RSS订阅
原创 并查集（入门）
并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。如下图：我们通过反复地合并，可以将其转化为下面的集合：合并所以，并查集的其中一个操纵就是合并，也就是合并两个点所在集合，转换为代码：void merge(int x, int y){fa[get(x)] =...
2019-05-18 16:13:34
428
原创 拓扑排序（入门）
拓补排序是一种图论算法。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序，这种操作得出的顺序就称为拓补序列。那我们应该进行怎样的排序呢？这就是我们这次研究的重点了。这就是拓补排序的操作过程，下面我们来详解一下。1.找到一个入度为0的点2.删掉它的所有的边，将它放进队列3.找到另一个入度为0的点4.删掉它的所有的边，将它放进队列5.重复1和2，直到...
2019-05-03 17:01:48
283
原创 目录
YCOJ：找数字&&洛谷P1036选数等边三角形中国邮递员问题家谱迷宫解的方案数踏青工作分配问题(job)黑熊过河二进制数问题装载问题(load)弹地小球字母统计弹簧板2传娃娃数塔问题城堡之旅01背包完全背包问题混合背包洛谷：采药城堡之旅数字三角形 Number Triangles迷宫八皇后陶陶摘苹果（升级版）三连击小A点菜...
2019-03-01 19:19:43
197
原创 动态规划初步——易懂
目录1.递推2.动态规划入门动态规划的科普动态规划的基本概念：动态规划的优化原理与无后效性。背包1.递推讲到动态规划就不得不提到递归，递推是经常被使用的一种简单算法。递推 是一种用若干步可重复的简单运算来描述复杂问题的方法。递推的特点在于，每一项都和他前面的若干项有一定关联，这种关联一般可以通过 递推关系式 来表示，可以通过其前面若干项得出某项的数据。对于递推问题的求解一般从初始的一个或若干个...
2019-02-17 20:09:15
223
原创 修灯
题目：一行信号灯,有些坏了,要求修好最少的灯,使存在一条连续K个灯没有坏输入第一行给出N,K,B分别代表一共有N个灯，希望有连续K个灯是好的，目前有B个灯是坏的接下来B个数字，代表坏的灯的编号 1≤N≤100,0001≤B,K≤NN个灯,B个坏掉的灯输出输出最少需要修好的灯样例输入 10 6 5210159样例输出 1水题，前缀和记录区间里有多少个坏了的灯泡，然后只需要枚举长度为k的区间，取每个区间的最小值即可。考试时数组开小了就离谱代码：#in
2020-11-04 19:08:15
449
原创 test-2020-10-27 （公交换乘 对称二叉树 photo）
时隔多月，终于准备再水一篇博客了，还有9天就CSP提高了，考完没一等奖就当中考er了，应该就不会怎么动这个博客了。这次考三道题，两道CSP2019-J原题，重温一下那种感觉吧。T1:公交换乘这道题是CSP2019-J的T3，满满的怀旧，当年就挫败在了这道题之下，现在一看，就一道模拟嘛。思路：题目给的很明确:如果可以使用优惠票一定会使用优惠票；如果有多张优惠票满足条件，则优先消耗获得最早的优惠票。我们保证出行记录是按照开始乘车的时间顺序给出的，且不会有两次乘车记录出现在同一分钟。记录既
2020-10-28 21:25:33
203
原创 详解最小生成树——Prim&Kruskal
生成树是指在一个有个点的图中由n-1条边构成的子图并且每一个点都在这个子图中，其中总边权值最小的生成树就被称为最小生成树。如图所示：PrimPrim算法是通过扩展边来求最小生成树，其思路和Dijkstra非常相似，它从一个未被加入最小生成树的点开始，枚举所以从其出发的所有边，选出其中权值最小的一条边，将其加入最小生成树，将其到达的点加入最小生成树并将点标记，直到最小生成树里有n-1条边。如图所示，就是prim构造最小生成树的过程。核心代码如下:void prim(){ memset(dis,
2020-08-03 17:26:50
315
原创 Wormholes——SPFA判负环
题目：描述John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N（从1…N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时
2020-07-31 20:30:58
237
原创 奖金——构造最小拓扑序
题目：描述Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。输入第一行两个整数n,m，表示员工总数和代表数；以下m行，每行2个整数a,b，表示某个代表认为第a号员工奖金应该比第b号员工高。n<=10000，m<=20000
2020-07-31 19:14:15
247
原创 拓扑——判断是否有唯一的拓扑序
题目：描述从前有一个萌萌哒的图，它是一个有向无环图。它想知道自己的拓扑序是否唯一。但因为图不会写代码，所以它把这个任务交给了你。输入第一行两个正整数 n, m 表示图的点数和边数。接下来 m 行，每行两个整数 x, y，表示有一条从 x 到 y 的有向边。1 ≤ n ≤ 100000, 1 ≤ m ≤ 100000输入保证图中无环。输出如果图的拓扑序唯一，输出一行一个字符串 ”YES”。否则输出 “NO“样例输入4 41 22 32 41 3输出NO
2020-07-31 16:55:25
5776
1
原创 Dijkstra算法及其优化——最短路算法
Dijkstra算法（一下简称Dij），是目前主流的求最短路的方法，自从CCF出题人公开表明SPFA它死了，并且在2018年卡了一次毒瘤数据SPFA，SPAF便退下主流最短路之位。Dij实在每次进行扩展时，都去找相邻且离起点最近的点，这样就能达到最短路当前最优，但是并不代表未来最优，但是我们现在不考虑，那是Astar的事。Dij算法如上右图，BFS如左图，可见，BFS不能处理带权的最短路，只是暴力的扩展，而Dij可以。下面我们通过一道例题来理解Dij的代码实现。热浪输入第1行：4个由空格隔开
2020-07-31 09:15:48
507
原创 Revamping Trails 道路升级——多维最短路
题目：描述每天,农夫John需要经过一些道路去检查牛棚N里面的牛. 农场上有M(1<=M<=50,000)条双向泥土道路,编号为1…M.道路i连接牛棚P1_i和P2_i (1 <= P1_i <= N; 1 <= P2_i<= N). John需要T_i (1 <= T_i <= 1,000,000)时间单位用道路i从P1_i走到P2_i或者从P2_i 走到P１_i 他想更新一些路经来减少每天花在路上的时间.具体地说,他想更新K (1 <=
2020-07-30 16:59:08
208
原创 最短路上的统计——Floyd
题目：描述一个无向图上，没有自环，所有边的权值均为1，对于一个点对（a,b）我们要把所有a与b之间所有最短路上的点的总个数输出。输入第一行n,m,表示n个点，m条边接下来m行，每行两个数a,b,表示a,b之间有条边在下来一个数p,表示问题的个数接下来p行，每行两个数a,b,表示询问a,bn<=100，p<=5000输出对于每个询问，输出一个数c,表示a,b之间最短路上点的总个数样例输入5 61 21 32 32 43 54 532 55
2020-07-29 18:57:15
185
原创 Roadblocks——SPFA求次短路
题目：描述贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多
2020-07-29 16:38:45
327
4
原创 Hide and Seek 捉迷藏 USACO 最短路板子题
题目：描述贝茜在和约翰玩一个“捉迷藏”的游戏．她正要找出所有适合她躲藏的安全牛棚．一共有N(2≤N≤20000)个牛棚，被编为1到N号．她知道约翰（捉牛者）从牛棚1出发．所有的牛棚由M(1≤M≤50000)条双向路连接，每条双向路连接两个不同的牛棚．所有的牛棚都是相通的．贝茜认为同牛棚1距离最远的的牛棚是安全的．两个牛棚间的距离是指，从一个牛棚到另一个牛棚最少需要通过的道路数量．请帮贝茜找出所有的安全牛棚．输入第1行输入两个整数N和M，之后M行每行输入两个整数，表示一条路的两个端点．输出
2020-07-28 19:03:44
188
原创 位运算——关于状压DP
位运算就是直接对整数在内存中的二进制位进行操作。简单的说就是二进制计算，我们的状压DP是通过将状态转为二进制的01来表示再转为十进制存到数组中来达到压缩状态，所以要学好状压，一定要学好位运算.& and&，也就是and，“按位与”，也就是两个二进制数每一位与每一位进行计算，如果都为1则返回1。如1011与0101进行&运算则得到0001，如下图| or|，也就是or，“按位或”，就是两个二进制数各个数字一一进行比较，如果两个数其中一个为1则返回1。如1011和0101进行
2020-07-28 14:27:15
187
原创 方格取数——移动类DP
题目：设有N*N的方格图(N<=10)，我们将其中的某些方格中填入正整数，而其他的方格中则放人数字0。如下图所示（见样例 ，黄色和蓝色分别为两次走的路线，其中绿色的格子为黄色和蓝色共同走过的）：某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。输入输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数
2020-07-27 20:42:53
220
原创 数字三角形4——移动类DP
题目：描述一个数字三角宝塔。设数字三角形中的数字为绝对值不超过1000的整数。小K从最顶层走到最底层，每一步可向下或右斜线向下走。每走过一个节点他会把这个节点的数字加在自己计数器中。另外他最多只能向下走k次。现在小K想知道他到达底层后，计数器中可能的最大的值。输入输入数据的第1行是数字三角形的行数n和能够沿左斜线向下走的次数k，1<=n<=1000，0<=k<=100。接下来n行是数字三角形各行中的数字。所有数字都小于1000。输出如题样例输
2020-07-27 20:21:25
221
原创 数字三角形3——移动类DP
题目：描述一个数字三角宝塔。设数字三角形中的数字为绝对值不超过1000的整数。小K从最顶层走到最底层，每一步可沿向下或右斜线向下走。每走过一个节点他会把这个节点的数字加在自己计数器中。另外他有一次机会，将他的计数器的数清零，他可以在任意时刻使用这次机会。现在小K想知道他到达底层后，计数器中可能的最大的值.输入输入数据的第1 行是数字三角形的行数n，1<=n<=1000。接下来n行是数字三角形各行中的数字。所有数字都小于1000。输出程序运行结束时，将计算出的最大
2020-07-27 20:07:23
184
原创 数字三角形2——含绝对值的移动类DP
题目：描述一个数字三角宝塔。设数字三角形中的数字为绝对值不超过1000的整数。现规定从最顶层走到最底层，每一步可沿向下或右斜线向下走。求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和的绝对值最大，输出最大值输入输入数据的第1 行是数字三角形的行数n，1<=n<=1000。接下来n行是数字三角形各行中的数字。所有数字都小于1000。输出程序运行结束时，将计算出的最大值输出。样例输入413 24 10 14 3 2 20输出24
2020-07-27 19:45:32
169
原创 传球游戏之最小总代价——状压DP
题目：描述n个人在做传递物品的游戏,编号为1-n。游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；求当物品经过所有n个人后，整个过程的总代价是多少。输入第一行为n,表示共有n个人（16>=n>=2）；以下为n*n的矩阵，第i+1行、第j列表示物品从编号为i的人传递到编号为j的人所花费的代价，特别的有
2020-07-26 20:28:31
245
原创 旅行者的背包——分组背包类
题目：描述cici去远游，却发现他的背包不同于01背包，他的物品大致可分为k组，每组中的物品相互冲突,每组至多只能选一个，现在，他想知道最大的利用价值是多少。输入两个数m,n，表示一共有n件物品，总重量为m接下来n行，每行3个数ai,bi,ci，表示物品的重量，利用价值，所属组数1<=m<=1000 1<=n<=1000 组数t<=100输出一个数，最大的利用价值样例输入45 310 10 110 5 150 400 2输出10
2020-07-26 17:27:03
329
原创 石子合并2——环状合并DP
题目描述在一个环形跑道上有N堆石子，每次取相邻两堆进行合并最终合并成为一堆。请问将每次合并后的代价进行累加其总和最少为多少输入第一行为石子堆数N,N<=200第二行到第N行，每行一个正整数代表石子数,其小于10000输出一行，表示最小的总得分样例输入44594输出43此题是典型的合并类DP，板子题，它和石子合并1所不同的是这次的跑道是环状的，也就是首尾相连，最后一个可以和最开始一个合并了。所以我们可以将数组开成双倍的，从而达到环的效果。借此机会
2020-07-26 17:00:15
300
原创 vbs进阶——常用函数之inputbox篇（末尾有彩蛋）
上一期，我给大家讲了msgbox，这一期我们来研究获取输入的inputbox相比于msgbox，inputbox要简单很多。下面是基本格式：inputbox 1,2,31和msgbox一样,inputbox的第一个参数是将要询问的问题或者说输入值的意义，也就是一个字符串。代码示例Dim xx=inputbox ("Are you reading my blog?Yes or No"...
2020-02-27 20:40:45
3097
8
原创 vbs进阶——实用函数之msgbox篇
两个月没写博客了，最近重新来找一下感觉吧。因为疫情严重，闲着也是闲着，就来写写vbs的博客吧。在vbs入门里我曾经提到过msgbox这个函数，可以弹出一个对话框，下面我来具体描述一下这个函数完整的格式msgboxmsgbox 1,2,3,4,51这里可以是一个字符串或者一个变量,如果你想要变量+字符串，可以用 & 来连接它们示例：dim xx="world"msgbox ...
2020-02-27 16:23:51
4786
1
原创 数据结构之堆——从听说到掌握
定义堆其实是用数组实现的二叉树，并不是非常高大上。应用构建优先队列支持堆排序快速找出一个集合中的最小值（或者最大值）在朋友面前装逼:)对的分类堆分两种，其一叫大根堆，另一个叫小根堆。大根堆在大根堆中，父节点的值比每一个子节点的值都要大。也就可以理解为大根堆会对放进里面的数会自动排序。定义：priority_queue<pa,vector<pa>,gre...
2019-12-29 15:13:26
280
原创 电脑常用的快捷键
目录常用篇浏览器篇常用篇信息学三连ctrl+a 全选ctrl+c 复制ctrl+v 粘贴正常ctrl+x 剪切Windows+tab/alt+tab 切换页面ctrl+w 关闭当前页面alt+F4 关闭当前程序ctrl+n 新建ctrl+f 查找ctrl+g 替换ctrl+z 撤销浏览器篇...
2019-12-14 14:39:38
151
原创 二叉树的先序、中序、后序遍历
二叉树，就是每个节点至多只会有两个子节点，如下图就是一个二叉树。接下来就进入正题：在二叉树的遍历中，一共有三种分类：先序、中序、后序遍历。例图：先序遍历先序遍历：根节点，左子树，右子树为了让大家更容易理解，我们来模拟一下。如图，我们走到了根节点1。 1走左子树，到达了2。 1 ， 2再继续走左子树到达了4。 1 ， 2 ， 4这时走到了叶节点，于是回到此节点...
2019-10-18 19:55:49
1778
原创 未来
近日，经朋友推荐，偶阅《未来简史》，感触颇深，因此对未来产生一些 瞎想 遐想，所以写这篇博文娱乐娱乐。引子未来，一种可以想象却又无法想象的东西。人类虽然能预言明天的天气，但却不能预言下次科技革命的时间。所以，下面我所述的东西，你若不相信，可以当作没读过这篇文章；你若相信，说不定未来真有此事。未来的核心技术这一节，我们将会讨论未来的核心技术也许是什么。AI第一种可能，也是最可能的可能...
2019-09-14 14:26:11
256
1
原创 机房小游戏---以io为后缀的
文章目录序starblast.iomope.iodiep.io序首先，文章题目以io为后缀的是指各种以io为后缀的网页小游戏，都比较的简单，推荐一玩。食用方法： 点击标题starblast.io首推此款游戏，比较有科幻感，很不错，有多种模式，享受在太空里的激斗吧！！！mope.io丛林大作战，类似于大鱼吃小鱼，但更有趣，更生动。diep.io一款坦克小游戏，比较好玩。...
2019-07-25 11:27:29
2241
原创 筛法——欧拉筛和埃式筛（详细至极）
文章目录总埃式筛法欧拉筛总首先，筛法是一种用来判断质数的方法，可以刷出一个质数表，所以也叫刷表法。今天我就来给大家讲两种筛法：埃式筛法和线性筛法。埃式筛法基本思想：一个整数的1以上且为整数倍是一个合数。我们可以从小到大枚举n以内的质数，对其不超过n的倍数进行标记，剩下未标记的数即为质数。基本写法：for (int i=2;i<=n;i++){ if(!vis[i]){ ...
2019-07-25 11:11:56
1088
原创 最大约数和
题目：题目描述选取和不超过S的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。输入格式输入一个正整数S。输出格式输出最大的约数之和。输入输出样例输入 #111输出 #19说明/提示样例说明取数字4和6，可以得到最大值(1+2)+(1+2+3)=9。数据规模S<=1000思路：把它当做01背包来做就行了。s为物品个数和背包容量,c[i]为1至...
2019-07-25 09:39:27
358
原创 狼和羊
题目：Description米基家的后院养着一群羊，米基由于疲劳睡着了，这时一群饿狼钻进了后院开始攻击羊群，后院是由许多个方格构成的长方形区域，每个方格中用字符‘?’表示空地，‘#’表示栅栏，‘o’表示羊，‘v’表示狼，羊和狼所在的格子都是空地。如果从一个空地A沿着水平方向或垂直方向经过一系列的空地能够到达空地B，则称空地A和空地B属于同一个羊圈。对于能够逃离后院的空地我们认为它不属于任...
2019-07-22 09:47:48
466
原创 Knight Moves
题目：Description在一个8*8的棋盘上，一只中国象棋中的马要从一个点跳到另一个点。问最少需要多少步。Input整个测试组由多组数据组成，请做到文件底结束。对于每组数据，前两个坐标代表出发点，后两个代表结束点。注意坐标第一位为a至h中某个字母，第二位为1到8某个数字。Output对于每个测试请输出"To get from xx to yy takes n knight mov...
2019-07-17 09:59:11
1206
原创 营救铁达尼号
题目Description铁塔尼号遇险了！他发出了求救信号。距离最近的哥伦比亚号收到了讯息，时间就是生命，必须尽快赶到那里。通过侦测，哥伦比亚号获取了一张海洋图。这张图将海洋部分分化成n * n个比较小的单位，其中用1标明的是陆地，用0标明是海洋。船只能从一个格子，移到相邻的四个格子。为了尽快赶到出事地点，哥伦比亚号最少需要走多远的距离。Input第一行为n,下面是一个n * n的0，1矩...
2019-07-16 11:52:04
1793
原创 细胞&求细胞个数
题目：Description一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。Input整数m,n(m行，n列)1<=N,M<=100Output细胞的个数Sample Input4 100234500067103456050020456006710000000089Sample ...
2019-07-16 11:28:00
325
原创 周末舞会
题目：Description假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。Input第一行两队的人数;第二行舞曲的数目。Output配对情况Sample Input4 67Sam...
2019-07-15 11:28:16
723
原创 强力删除小程序
在用电脑的时候，总是会遇到一些顽固的损坏程序分子，他们删也删不掉。虽然不会有什么问题，但会让人看不顺眼，很恶心。今天，我就来传授大家一个方法。将需要删除的用程序打开即可。网盘下载链接: https://pan.baidu.com/s/1ZdLhEd_7YdSLWJN_ujO1RQ提取码: j8m7...
2019-07-14 13:40:00
1114
原创 一篇日记
今天是7月14日，这样算起来，我当OIer已有将近1年了，也是我们信息学社会团体成立一周年。回望从前，我在家的时间少了一半，这一年OIer，我哭过，笑过，AC过，WA过，认真写过博客，偷偷玩过游戏…OIer，此身无憾！！！...
2019-07-14 10:55:25
201
原创 间隔排列
题目：【题意描述】有2N个木块，每个木块标上1到N的自然数中的一个，每个数字会出现在两个木块上。把这些木块排成一排，要求是：标号为i的两个木块之间要间隔i个其它木块。比如说N=3的情况，下面就是一个可行的排列：3，1，2，1，3，2。编程实现，对给定的N，求出一个可行排列。【输入格式】输入只有一行，给出一个数字N,N<=40【输出格式】输出一个满足题意的排列,任两个数字间用一个空...
2019-07-14 09:23:50
2617
1
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人