- 博客(32)
- 收藏
- 关注
RSS订阅原创 寻找凸包（Graham扫描法）
题意描述：对任意给定的平面上的点集，求最小凸多边形使得点集中的点要么在凸多边形的边上，要么在凸多边形的内部。Graham算法描述：在所有的点中找到一点p0，使得p0的纵坐标值最小，在有多个最小纵坐标的情况下，找横坐标最小的那一个。将所有的点< p0, p1,…pn> 按规则（相对于p0的幅角从小到大，也就是绕p0逆时针，如有幅角相等的点，只保留离p0最远的那个，其他的删除）排序。如果所剩的顶点
2017-04-07 15:43:05
403
原创 求最大流Ford-Fulkerson方法（Edmonds-Karp算法）
基本思路：使用反平行边来模拟残存网络。在残存网络中用广搜来寻找增广路径（用pre数组记录前驱结点）。如找不到增广路径，已达到最大流，结束如找到增广路径，最大流的增值为增广路径上的权值的最小值。更新残存网络（从汇点通过前驱数组沿增广路径向前更新）。更新最大流。转步骤2.example：如下图找出从节点1到6的最大流。 输入： 6 9 1 2 16 2 4 12 4
2017-04-07 12:05:46
894
原创 HDU 2255 奔小康赚大钱(KM)
题目描述传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。 这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。 另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较
2017-04-06 22:31:47
346
原创 最小生成树（Kruskal + 查并集）
题目描述亮亮解出了卷轴隐藏的秘密，来到了一片沼泽地。这里有很多空地，而面试直通卡可能埋在任意一块空地中，好在亮亮发现了一堆木材，他可以将木材铺在两个空地之间的沼泽地上。因为亮亮不知道面试直通卡具体在哪一块空地中，所以必须要保证任意一块空地对于亮亮来说是可以抵达的。 “怎么还有鳄鱼！没办法，看来有些空地不能直接到达了。” 亮亮虽然没有洁癖，但是沼泽地实在太臭了，所以亮亮不会循环利用木材。而且木材不能拼
2017-04-06 18:52:54
785
原创 地铁修建——CCF CSP 201703-4
试题编号： 201703-4 试题名称： 地铁修建 时间限制： 1.0s 内存限制： 256.0MB 问题描述 A市有n个交通枢纽，其中1号和n号非常重要，为了加强运输能力，A市决定在1号到n号枢纽间修建一条地铁。 地铁由很多段隧道组成，每段隧道连接两个交通枢纽。经过勘探，有m段隧道作为候选，两个交通枢纽之间最多只有一条候选的隧道，没有隧道两端连接着同一个交通枢纽
2017-04-06 17:34:39
1708
1
原创 二叉排序树——华中科技大学计算机历年考研复试上机题
题目描述：输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。 输入描述:输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包括n个整数。输出描述:可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。 每种遍历结果输出一行。每行最后一个数据之后有一个空格。输入中可能有重复元素，但是输出的二叉树遍历序列中重复元素不用输出。
2017-04-05 20:59:05
350
原创 楚楚街2016校招 ——礼物（动态规划）
题目描述“呼！！佳慧，我拿到面试直通卡了！”“吓死宝宝了！哦，你拿到直通卡了啊，好哒，进去吧，你可以直接接受老大的面试了”。 亮亮来到老大的办公室，“骚年，你想做什么工作啊？”“我要做大数据分析！！” “哦~~那你先帮我们解决一个问题。是这样的，我们这次招聘会一共有N个人，我们公司给大家准备了一些礼物，但是我们并不知道这些人具体喜欢什么，现在库房共有m种礼物，每种礼物有Ci件，共N件。而我们大致
2017-04-05 14:23:33
1052
原创 文章标题
#include<iostream>#include<string>using namespace std;int main(){ string s; string::iterator itb, it; int len, ans = 0, i, j; int b = 0; cin >> len >> s; itb = s.begin();
2017-04-01 17:48:42
158
原创 tongji 1016: predict
题目描述随着小猪界象征着最高级别的小猪足球世界杯的开打，很多人都加入了猜球的行列，小香猪由于各种原因以球员的身份参赛，但是她也积极加入猜球行列。小猪足球世界杯是分成好几轮来打的，每一轮有特定场次比赛组成，每一场比赛以后，如果你不仅可以通过猜对这一场比赛的胜负而得分，而且如果猜对了比分，还可以得到额外的分数，每一轮结束以后，获得最高分的人会因此而得到特殊的分数，我们把它叫做一摩尔（等一下如果出现平局一
2017-03-31 12:25:22
251
原创 HDU 1269 迷宫城堡（tarjan求连通分量)
题目描述为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在
2017-03-30 20:31:46
268
原创 HDU 1874 畅通工程续(单源最短路径)
题目描述某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。 现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。 输入描述:本题目包含多组数据，请处理到文件结束。 每组数据第一行包含两个正整数N和M(0 < N<200,0 < M<100
2017-03-30 16:47:55
230
原创 HDU 1862 畅通工程（最小生成树prim）
题目描述省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。 输入描述:测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M ( < 100 )；随后的 N 行对应村庄间道路的成本，每行
2017-03-30 14:49:58
200
原创 HDU 1285 确定比赛名次（拓扑排序）
题目描述有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。输入描述 输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着
2017-03-30 13:06:55
398
原创 腾讯笔试——安排座位（动态规划）
题目描述为了给腾讯公司找到更多优秀的人才，HR湫秋最近去某高校组织了一次针对该校所有系的聚会，邀请了每个系的一些优秀学生来参加。 作为组织者，湫秋要安排他们的座位。这并不是一件很简单的事情，因为只有一排位置，并且位置总数恰好等于参加聚会的人数。为了促进交流，两个来自相同系的同学不可以座位相邻。湫秋现在希望知道有多少种不同的合理安排座位的方法（任意两个合理的安排方法，只要有一个位置的同学不同，都被认
2017-03-29 18:33:10
2815
原创 Dijkstra算法求最短路和比最短路长1的路径的数目（单源最短路径plus）
题目描述人类和人鱼拥有共同的祖先，因为某种原因发生了分化，人鱼到了大海里生活。近年来人类对大海及生态的破坏，人鱼族的生存环境受到了严重的影响。最近某地产公司筹备一个填海计划，在附近的大海中装入了声呐系统，这极大地限制了人鱼的活动。人鱼族的居民们为了适应环境，建立了n个聚居点（从1到n编号），m条有一定长度的单向通道，每条由一个聚居点通向另一个聚居点。人鱼族派出了美人鱼珊珊去勾引地产公司的老总刘轩，来
2017-03-28 23:34:14
1003
原创 最大公共子序列，最大子段和（动态规划）
最大公共子序列/*2017.2.28 代文海*//*题意简介：求两个字符串的最大公共子序列 思路：设有字符串X和字符串Y, 数组l[i][j]表示字符串的前i个字符和字符串Y的前j个字符构成的最长公共子序列。 如果有X[i] = Y[j]那么有l[i][j]=l[i-1][j-1],否则l[i][j] = max(l[i][j-1], l[i-1][j]). */#include
2017-02-28 20:16:16
642
原创 计数问题
题目描述： 给定两个整数a和b，计算1在a和b之间出现的次数 输入： 输入不会超过500行，每一行有两个整数a和b，a和b的范围是0-100000000.输入两个0时程序结束。 输出： 对于每一对输入a和b，输出一个数表示1出现的次数 思路： 诸位处理#include <iostream>using namespace std;in
2016-12-11 21:29:15
299
原创 查找等式的解
查找等式的解题目描述： 有三个数列 a b c ，有一个数 x，计算是否存在a b c 中的在3个整数a b c 使得a+b+c=x成立。 输入： 第一行为三个整数，分别为a b c 数列的长度 第二行到第四行分别为a b c 数列中的值 第五行为要测试的 x 的个数 n 接下来的 n 行为 n 个测试数据 输出： n行输出，如果能找到这样的 a b c ，输出yes， 如果不存在这
2016-12-11 21:23:35
315
1
原创 关于"\r","\n","\r\n"区别的实践
\n是换行，即new line\r是回车，即Carriage return回车和换行的概念来自于以前的滚筒打字机，在滚筒打字机中，回车(\r)是将水平位置复位，即把打字的位置移动到本行的行首，滚筒没有滚动(不换行），而换行(\n)是将滚筒打字机滚动一下，即移动到下一行的该位置(不回到行首),所以打字机每打印完一行就要执行两个操作(回车和换行)才能从下一行的行首开始打印。我们现在在计算机
2016-10-30 16:31:56
486
原创 git 入门
安装git redhat系列linux下：yum install git 可完成安装查看当前git版本git --version创建一个文件夹并将它初始化为版本库初始化时git init命令会创建一个隐藏的目录，在项目的顶层目录，名为.git，所有的修订信息都放在这一目录下在文件夹下新建一个文件，并将其添加到版本库中新建的文件只是普通的文件
2016-10-29 20:07:27
199
转载 linux c下的字符串正则替换
代码来自于点击打开链接#include #include #include #include #include //regex#include //cns_reg函数的返回类型typedef struct _reg_rtn_struct{ int rtn; //成功与否标志0 成功， 1失败 int pstart; //匹配到的子串开始位移
2016-10-29 12:14:49
1319
原创 linux TCP套接字编程
服务端：//TCP套接字编程服务端#include #include #include #include #include #include #include #define PORT 8899int main(){ int sockfd,newsockfd; //定义套接字描述符 struct sockad
2016-10-27 21:59:47
436
原创 处理器架构的大端模式和小端模式
字节序 在同一台计算机上通信或不用考虑字节序，字节序是处理器架构的特性，用于指示像整数这样的大字节数据在计算机内部的存储方式，一般在网络通信中要考虑不同的处理器架构的不同存储方式造成数据值的改变，所以在网络通信中要将本地字节序转换为网络字节序再传送。TCP/IP栈使用大端字节序。
2016-10-27 18:34:44
962
原创 linux套接字编程
套接字描述符 套接字是通信端点的抽象，和用文件描述符来访问文件同理，应用程序用套接字描述符来访问套接字，套接字在unix系统中被当做是一种文件描述符。虽然套接字本质上是一种文件描述符，但并不是完全可以当做文件描述符来操作，例如，有些以文件描述符作为参数的函数就不能接受套接字为参数。例如lseek函数就不能以套接字作为参数，因为套接字不支持文件偏移量的概念。我们可以理解套接字是一种添
2016-10-27 17:30:51
225
原创 python学习笔记(2)网络编程
套接字地址：主机-端口对 一个网络地址由主机地址和端口号组成，有效的端口号地址是0-65535（0-1024端口号预留给系统），在POSIX兼容系统中，可以在/etc/services中找到预留的端口号列表（服务器/协议和套接字类型）。 如下图：21号端口是tp服务，22号端口是ssh服务，23号端口是telnet服务也可以在此网站中查看众所周知的服务端口号列表：http
2016-10-22 16:03:26
609
原创 python学习笔记(1)正则表达式
“.”匹配任何字符串（除了\n外） re.match('f.o','f9of23o') re.match('f.o','f9of2o')
2016-10-20 22:45:07
2680
原创 动态规划——收集样本机器人问题
#include using namespace std;int****h, **p;void val(int x1,int y1,int x2,int y2,int v,int n){ if(x1==n||x2==n||y1==n||y2==n) return ; if(x1==x2&&y1==y2) h[x1][y1][x2][y2]=m
2016-07-06 15:21:33
2160
原创 动态规划——矩阵连乘
#include using namespace std;void MatrixMul(int *p,int n,int**m ,int **s)///p记录矩阵维数，m最少乘法次数，s分法{ for(int i=0;i<n;i++) m[i][i]=0; for(int r=1;r<n;r++) for(int i=0;i<n-r;i++)
2016-07-06 13:53:20
352
原创 A*算法解决八数码问题
以下内容仅是我个人对八数码问题和A*寻路算法的理解，因为我是菜鸟一个，所以写的比较通俗。八数码问题： 八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
2016-05-04 21:32:26
31714
2
原创 java swing 文本域中改变字体颜色
我们常用的JTextArea是纯文本组件，不能改变字体的颜色，可以用JTextPane组件，它要比JTextArea功能强大很多，JTextPane的用法可以看java文档：点击打开链接1.用JTextPane的setForeground设置字体颜色。package java;import java.awt.Color;import javax.swing.JFrame;import
2016-05-02 15:42:34
22043
1
原创 贪心算法——单源最短路径
1.算法描述 给定一个带权有向图G={V,E},以及V中的一个顶点，称为源，计算从源到其他各顶点的最短路径。2.Dijkstra算法 Dijkstra算法是解单源最短路径的一个贪心算法，其主要思想是：设置顶点集合S，并不断地扩充该集合S，一个点可以归并到该集合的充要条件是该点到源点的距离已知。用数组dist记录目前所有点到该点的最短路径，循环依次找出不在该集合中
2016-04-28 12:28:57
1544
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人