- 博客(30)
- 收藏
- 关注
RSS订阅原创 POJ1068 Parencodings
作为一个括号匹配问题，大意就是一个string包括左括号和右括号，然后这些括号是匹配的，通过这个string可以得出P和W两个数组，即string的另一种表示形式，P表示的是每个右括号左侧有多少左括号，W表示的是每个右括号和与自己匹配的左括号之间有多少个左括号（包括与自己匹配的）给定P，求W贴代码：懒得想复杂的解法，就直接从P得到括号字符串，再得到W/* author FGTmiao * 2020.5.23 */#define _CRT_SECURE_NO_WARNINGS#incl
2020-05-23 22:26:54
132
原创 poj 2486 Highways
大意就是找一个最小的生成树，然后找到里面的最大边即可简单的一...一塌糊涂，不过还是推荐prim算法，ku...算法适合稀疏图，是根据边算的，毕竟这个算是完全图了一遍AC真实让今天烦恼尽消#pragma warning (disable:4996)/*coded by fgtmiaotime:2019/6/29*///即找到最小生成树的最大边，不过如果是找到能联通的所需要的...
2019-07-03 19:49:53
121
原创 poj2253 Frogger
题目大意是找出一次需要跳的最短的长度，其实是最短路径的变形通过dijs算法找到最短的距离即可开始时sqrt那里用的整数，vs没错poj会报错，有点难受...#pragma warning (disable:4996)/*coded by fgtmiaotime:2019/6/29使用dijstras(?)算法*/#include<iostream>#incl...
2019-07-02 20:28:41
107
原创 poj3259 Wormhole（BF算法，或者弗洛伊德应该也行）
检测负权环的问题用BF算法即可，即每次看能不能更新距离，如果都没有更新，说明算法达到了顶点，直接跳出出了一次bug调了好久...进行了开数组，优化代码，看了好几次...你猜？没错！就是YES写成了Yes！wdnmd...#include<iostream>using namespace std;int F, N, M, W;int dist[10001], u[...
2019-07-01 20:32:36
134
原创 poj 2109 Power of Cryptography
大意就是给定n，p，找到K使得k^n=p我以为有这种函数的23333333，但自己写有点痛苦后来发现了好的办法，而且精度是够的直接p^(1/n)即可，有点好玩#pragma warning (disable:4996)/*coded by fgtmiaotime:2019/6/30*/#include<iostream>#include<algori...
2019-06-30 15:58:01
73
原创 poj1328 Radar Installation小小的贪心
大意是通过最少的雷达控制所有的小岛，本质上是取多个点覆盖所有线段的问题。开始想错了XD以为覆盖了远处的近处的也会被覆盖，后来发现自己傻了233333以每个小岛为中心，dist为半径画圆和x轴相交le与ri两个点，这两点中间放雷达就能够覆盖这个小岛，相当于把问题等价成了线段的相互覆盖的贪心问题。这种贪心方法是把小岛的ri从小到大排列，然后从小向大扫，初始点是第一个的ri，如果发现有一条线...
2019-06-30 15:34:18
89
原创 poj1965 The Pilots Brothers' refrigerator
开始没什么想法...一直想找到简单的方法不用遍历，或者减少遍历的东西和规则然而并没有xswl直接枚举加dfs加回溯，跑一边就完事了，记得最后是+1就好了#pragma warning (disable:4996)/*coded by fgtmiaotime:2019/6/29*/#include<iostream>//dfs & 暴力using nam...
2019-06-29 17:45:37
109
原创 poj1753 Flip Game
好了...本咸鱼受到了leetcode大佬的打击，要日更（？）刷leetcode或者poj了...慢慢从简单的开始吧枚举问题，如果全枚举翻转是2^16个（其实也不是不能计算233333但其实只要第0行确认之后，后续的反转都是固定的（因为上一行只能由下一行翻转变化才能变，只要第0行确定，后续都可以根据这个规则）只需要枚举第0行状态即可，即16种，通过用0~15表示四位，即0000~1111，...
2019-06-29 17:05:25
101
原创 poj拼写检查
现在有一些英语单词需要做拼写检查，你的工具是一本词典。需要检查的单词，有的是词典中的单词，有的与词典中的单词相似，你的任务是发现这两种情况。单词A与单词B相似的情况有三种：1、删除单词A的一个字母后得到单词B；2、用任意一个字母替换单词A的一个字母后得到单词B；3、在单词A的任意位置增加一个字母后得到单词B。你的任务是发现词典中与给定单词相同或相似的单词。 输入第一部分...
2018-12-15 19:26:28
1025
1
原创 poj电话号码 简单的树
给你一些电话号码，请判断它们是否是一致的，即是否有某个电话是另一个电话的前缀。比如：Emergency 911Alice 97 625 999Bob 91 12 54 26在这个例子中，我们不可能拨通Bob的电话，因为Emergency的电话是它的前缀，当拨打Bob的电话时会先接通Emergency，所以这些电话号码不是一致的。输入第一行是一个整数t，1 ≤ t ≤ 40，表示测试...
2018-12-14 10:10:50
1713
1
原创 poj 发型糟糕的一天，骚...
农夫John 的N(1 ≤ N ≤ 80,000)只奶牛中，有一些也许正在经历发型糟糕的一天。每只奶牛对自己乱糟糟的发型都有自知之明，农夫John想知道所有奶牛能看到其他奶牛头顶的数量之和。任意奶牛i身高记为 hi (1 ≤ hi ≤ 1,000,000,000)，所有奶牛面向东方（本题示意图的右面）依次站成一条线。因此，奶牛i能够看到在它前面的（奶牛i+1，i+2…）所有身高比它低的奶牛，直...
2018-12-12 22:11:28
523
原创 poj:Rainbow的商店 奇妙的贪心
Rainbow开了一家商店，在一次进货中获得了N个商品。已知每个商品的利润和过期时间。Rainbow每天只能卖一个商品，并且过期商品不能再卖。Rainbow也可以选择在每天出售哪个商品，并且一定可以卖出。由于这些限制，Rainbow需要制定一份合理的售卖计划。请你计算一下，Rainbow最终可以获得的最大收益。 输入第一行两个整数N。接下来N行每行两个整数，分别表示每个...
2018-12-10 11:53:42
435
1
原创 poj:Freda的越野跑 求正序对数
Freda报名参加了学校的越野跑。越野跑共有N人参加，在一条笔直的道路上进行。这N个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这N个人同时沿着道路向相同的方向跑去。换句话说，这N个人可以看作x轴上的N个点，在比赛开始后，它们同时向x轴正方向移动。假设越野跑的距离足够远，这N个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？输入第一行1个整...
2018-12-10 11:34:33
629
原创 DNA排序，简单的排序题
现在有一些长度相等的DNA串（只由ACGT四个字母组成），请将它们按照逆序对的数量多少排序。逆序对指的是字符串A中的两个字符A[i]、A[j]，具有i < j 且 A[i] > A[j] 的性质。如字符串”ATCG“中，T和C是一个逆序对，T和G是另一个逆序对，这个字符串的逆序对数为2。 输入第1行：两个整数n和m，n(0<n<=50)表示字符串长度，m(0...
2018-12-10 10:57:06
2791
原创 sequence，堆的排序
Sequence题目内容：给定m个数字序列，每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列，显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和，一共会得到n^m个和，请找出最小的n个和 输入格式:输入的第一行是一个整数T，表示测试用例的数量，接下来是T个测试用例的输入每个测试用例输入的第一行是两个正整数m（0 < m ...
2018-12-03 16:47:19
777
原创 促销活动
促销活动题目内容：Great Bytelandish超市联盟想请你编写一个程序模拟计算促销活动的开销促销活动遵守以下规则：参加促销活动的客户，可以在消费结束后将自己的消费账单投入一个指定的投票箱里当一天的促销活动结束时，将从投票箱中选出两份账单：一份是消费金额最大的账单，一份是消费金额最小的账单。最大金额账单对应的客户，将得到一笔奖金，奖金数等于金额最大的账单与金额最小的账单之...
2018-12-03 16:12:40
507
原创 超级快排：Ultra-QuickSort
题目内容：在这个问题中，你需要分析特别的算法。这个算法通过对一个包含n个元素的进行操作，一直交换相邻的两个序列的元素直到整个序列呈升序排列。对于输入序列9 1 0 5 4 ,Ultra-QuickSort最终得到的输出为0 1 4 5 9 .你的任务就是来计算出Ultra-QuickSort 至少需要多少swap操作来最终达到对一个给定的输入序列排好序的目标。 输入格式:输入包括多...
2018-12-03 15:59:06
2980
原创 poj3159 candies能够比前面的小孩最多吃多少糖
大意是有向图，你能比前面的小孩最多吃多少糖，求N的小孩比第一个多多少优先队列实现真的厉害每次取可取的最大路并且更新与原点的距离/*poj 3159 candies稀疏图求单源最短路dijkstra算法肯定是找到第一个差距最大的，后面再有差距最大的不满足了郭老师.jpg优先队列真的太妙了！*/#include<iostream>#include<qu...
2018-11-18 14:46:54
102
原创 poj apple tree 树状数组
树状数组我感觉是真的很神奇，不知道谁被上帝敲了脑门想出来了鬼才办法虽然自己也知道大的数据可以二分，或者尝试log(n)但是不得不说...真的厉害树状数组：适用于区间求和，单点爆破更新，要用到lowbit，即最低位lowbit(x)= x & (x^(x-1)) = x &(-x) ：因为负数补码是正数取反之后加一的，在x中从右向左，只要有出现一个非0位（非0位之前...
2018-11-16 12:24:09
128
原创 poj A bug's life
BackgroundProfessor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gende...
2018-11-16 12:00:36
147
原创 poj 食物链
动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这N个动物所构成的食物链关系进行描述：第一种说法是"1 X Y"，表示X和Y是同类。第二种说法是"2 X Y"，表示X吃Y。此人对N个动物，用上述两种说法，一句接一句地说出K句话，这...
2018-11-16 11:52:08
230
原创 POJ 1988 Cube stacking
题目如下：Sample Input 6 M 1 6 C 1 M 2 4 M 2 6 C 3 C 4 Sample Output 1 0 2有N(N<=30,000)堆方块，开始每堆都是一个方块方块编号1 – N. 有两种操作M x y ：表示把方块x所在的堆，拿起来叠放到y 所在的堆上C x : 问方块x下面有多少个方块操作最多有 P (P<=100,000)次对每次C...
2018-11-16 11:42:59
76
原创 二叉树的层序遍历题目
题目内容：二叉搜索树在动态查表中有特别的用处，一个无序序列可以通过构造一棵二叉搜索树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉搜索树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。 这里，我们想探究二叉树的建立和层次输出。输入格式:只有一行，包含若干个数字，中间用空格隔开。（数...
2018-11-15 14:05:31
328
原创 二叉树求深度（屯着后面用）
题目内容：给定一棵二叉树，求该二叉树的深度二叉树深度定义：从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的节点个数为树的深度输入格式:第一行是一个整数n，表示二叉树的结点个数。二叉树结点编号从1到n，根结点为1，n <= 10接下来有n行，依次对应二叉树的n个节点。每行有两个整数，分别表示该节点的左儿子和右儿子的节点编号。如果第一个（第二个）...
2018-11-15 13:11:42
136
原创 caocao's bridge：无向图求割点或桥
开始想用更简单的方法但是没实现，只能用了二维数组无向图求桥的重点就是边（u，v）(在dfs时的父子边)如果是桥的话有dfn[u]<low[v]求割点是：（非本题但就是想写了XD）如果点u是dfs时的根，u至少有两个子节点（当然总结点数要大于3）那他就是割点如果不是根，有一个子节点v满足dfn[u]>=low[v],比较好理解。其中dfn是访问次序，low是所在连通分...
2018-11-15 12:28:57
374
原创 大整数乘法
具体的方法和加法是类似的不过中间有可以简化的步骤比较巧进位要计算好没有写在小函数里，要用的话在函数里写很方便#include <iostream> #include <string.h>#define maxle 1000 using namespace std;int main(){ char a[maxle], b[maxle]; c...
2018-11-15 11:34:55
107
原创 popular cows：有向图的强连通分量
tarjan算法，即dfs找low和dfn，用timmer表示dfs的时间（经历各个点的次序）开始不明白怎么进行缩点，后来发现就是染色，同一个颜色的点如果有连接到其他颜色的点就算出度不为0如果出度为0的点（染色后）就一个，即为这个连通分量的所有点如果有很多个，说明不存在被所有喜欢的牛（两个出度为0的点不可能相互联系），为0#include<iostream>#inc...
2018-11-15 11:25:02
133
1
原创 切割回文串（动归练习）
题目大意：有n个字符串，每个字符串包含回文子串（单个字符也算回文子串），问对每一个字符串，最少切割多少次才能使子串都是回文串？例如asddsafg可以切割为：asddsa,f,g解题思路：显然，如果一个字符串本身就是回文串，切割次数为0,但是对于似乎没规律的字符串如何？首先，我们需要一个函数判断一段字符串是不是回文串，因为没有特殊的规律，所以需要比较繁琐的判断过程，即把一个字符串从头到尾都...
2018-09-12 09:02:34
691
原创 大整数加法（简单算法）
大整数加法首先要了解加法的算法，具体思路很简单： 从低位到高位开始加，需要进位，正向数组是高位在前，所以需要反向数组开始加法。 代码如下，写的麻烦了一点：#include<stdio.h>#include<iostream>#include<algorithm>#include<string.h>#define M...
2018-07-13 11:04:39
5425
原创 八皇后问题（回溯的算法）
八皇后问题是经典的回溯算法案例，但是对初学者有点难以理解... 基本思路是，从第一个皇后开始放置，同时设置列和左斜和右斜放置标志（如果是从列开始的就设置行的标志） 第i行遍历，如果没有能够放的位置，直接退出函数（也就是不用管），如果没有放到8个，就调用下一个函数，但是仍然在这一级函数之内，所以后续需要回溯以便进行下一个点的搜索。 这样是按照第一行...
2018-07-13 10:15:39
169
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人