ITeye博客

。。。

追梦-- · 共 16 篇文章

BestCoder Round #6 题解

1001 水题,没有什么陷阱 1002 题意:给你N和K,问你能否将N拆成K个完全不同的正整数,并且满足其中K-1个数的和为完全平方数(i i)。 看到这题,最开始的想法是,枚举完全平方数(n只有200000),则 b = n - i i 就是那个没有被选进去的数,如果k-1个完全不同的正整数最小的和是 s = (k-1) k/2(1,2,3,,,k-1的和)。如果b<k的话,说明b会和前面的数重合,所以我们只能将s+=k-b;(不让它们重合加的最小的值),当s<=i i的话,就是合法的。程序如果写成这样的话,还有过不了一些数据的。 对于 7 3 这组数据,当我们在枚举时,我们枚举到 i i…

2014-08-26 19:29 · ACM-算法-数据结构 · 比赛总结 · 评论(0)

2014武汉邀请赛总结

这次的武大邀请赛算是第一次和那么多学校比赛,一开始已经做好了被踩的准备。但还是比较激动的毕竟能和那么多强队一起比赛。 比赛刚一开始,每个人分别看题,看了几题都觉得无从下手,刷榜一直无人A题,过了一段时间,发现J题有人A了,立马让马去看J题,发现题意有点难懂,于是雷也加入看J题中,讨论然后写出了程序,但是WA了,由于时间拖了比较久,于是我也加入到J题中,发现题意理解错,然后雷重新推了下公式,然后A了,后来看其他题,马觉得D题暴搜能做,于是开始写D题,我和雷开始想其他题,其他的题基本上没有思路了,D题WA。后来马说J题用floyd+暴搜写,没写完,比赛很快就结束了。看了看周围,前面的国防科大队也…

2014-04-17 20:52 · 比赛总结 · 评论(0)

数论基础-欧拉函数

前几天,在杭电oj上碰到一个数论的题目,附链接: http://acm.hdu.edu.cn/showproblem.php?pid=1286 题意很简单,就是求一个数N比他小的与它互素(最大公约数为1)的数有多少个。 刚开始想要暴力的方法去解决这个问题,但后来发现暴力的时间复杂度是O(n^2),而N是32768以内的整数,测试数据有10000组,明显暴力会超时。 后来教练讲了下,说这种题目要用欧拉函数解决,一个很裸的水题。 这里介绍下欧拉函数 Phi(n)=n(1-1/p1) (1-1/p2)….. (1-1/pk) 其中p1, p2 ,pk是n的所有素数因子 Phi(n):所有小于等于n…

2014-03-15 14:03 · ACM-算法-数据结构 · 评论(0)

y=1/x-基于杭电Ranklist的一个探究

题目似乎有点不着边际,请各位耐心的看完,就知道其中的含义了。 已经接触了一段时间的ACM(详见百度百科)了,每回刷杭电oj的题累了的时候,就喜欢去看Ranklist里面的排名,看看前面的牛人的格言,让自己有一点憧憬。有一天突然好奇杭电上的人做的总题数的数量与人数之间有怎样的分布规律,这样就可以知道大多数的人做了多少题就停了下来。 说干就干,我先用用java代码写了一个抓取上面Ranklist网页的程序到本地后,利用正则表达式解析内容并提取其中的数据,最后导入到数据库中。技术方面不想讲的太详细,只想说下其中遇到的问题。 抓取网页速度太慢。近两千个网页似乎抓取了近十分钟,后来采取多线程抓取网页,…

2013-10-23 22:07 · 其他 · 评论(2)

c++-STL-priority_queue(优先队列)

如果我们在竞赛中如果用堆来实现一个优先队列,代码量不说,还有可能出现低级错误。这时候,c++ STL就是我们比赛中的一个好助手了。 和其他STL容器一样,priority_queue一样的又插入和删除元素。顾名思义,priority_queue就是权值大的优先出列,我们只需要插入数据,并拟定规则(重载操作符),priority_queue 自动排序(还是利用大顶堆,原理在此不详述)。 priority_queue 的构造函数有七种,这里只讲述比较重要的 priority_queue que; priority_queue<int,list > (复制构造函数) priority_queue<…

2013-09-04 09:28 · c++ STL · 评论(0)

算法--分治--a^b%m

杭电上有一道十分让初学者十分蛋疼的题 a^b%m,看似很简单,但题目要求b的范围是(0,1000000000],a是32位整数范围,m是小于40000的整数。咋一看这题,貌似要用高精度。但是赤裸裸的用高精度的话,在空间复杂度以及时间复杂度上都是伤不起的!! 让我们来换个思路,有一定数学基础的人都知道,(a b)%m 是等价于 a%m * b%m的,这样好了,可以不用高精度了,但是完全模拟的话,在规定时间内是不可能出解的。 我们再想想,是否可以减小计算量呢?有了!我们可以将 a^b 分解成为 t1 a^1+t2 a^2+t3 a^3+.....(ti=0 或者 1),我们预处理下,算出a^2i…

2013-08-23 19:21 · ACM-算法-数据结构 · 评论(1)

数据结构——并查集

让我们首先了解一下什么是并查集。并查集的英文:Disjoint Set,即“不相交集合“,将编号分别为1…N的N个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合。 常见两种操作: 合并两个集合 查找某元素属于哪个集合 这也就是这种数据结构叫并查集的原因!!!,下面是一种最简单的实现方法。 这种方法合并的时间复杂度是O(n),查找是O(1)的复杂度。伪码如下: 有没有优化的方法呢?当然是有的,因为上面我们合并两个集合必须搜索整个集合。那如果我们采用树结构呢?这的确是个好想法。 大致伪码如下: 还可以优化,路径压缩。 思想:每次查找的时候,如果路径较长,则修改信息,以便下次查找…

2013-08-09 20:08 · ACM-算法-数据结构 · 评论(0)

数据结构——堆栈

对于栈,想必大家都十分熟悉了,也能很快的答出栈是一个先进后出的队列。但是在平常编程的生活中应用的十分少。在ACM中,栈是一种十分重要的数据结构(其他领域也一样),我们可以用这种数据结构解决一些十分棘手的问题,大大提高了程序的效率。 有这样一道名为Software BUGs 的题。题目的意思简要来说就是去除一篇文章中的所有 ”BUG” 字段。 有些人可能认为这是一道水题,直接扫描文章,将其中的 ”BUG” 去掉就行。这样很容易就落进了陷阱。例如对于一个字符串 “ BBUBUGGG” 直接扫描过去得到 “BBUGGG” ,我们发现字符串中还有 ”BUG”(解决了一个BUG,又出现了一个BUG),…

2013-08-08 22:16 · ACM-算法-数据结构 · 评论(0)

算法的时间复杂度

算法的时间复杂度 分析一个算法的好坏,时间复杂度是一个非常重要的标准。我们一般用O()表示一个算法的复杂度。 常见的算法时间复杂度有(由小到大): O(1)常数阶 O(logn)对数阶 O(n)线性阶 O(nlogn) O(n^2) O(n^3) | -------- p问题(时间复杂度为上) -----------| O(2^n) O(n!) |-NP问题(复杂度为上)-| 计算时间复杂度可分为递归和非递归两种: 举一个简单的例子:计算斐波拉契数列 f (n) = f (n-1) +f (n-2) (n < 45) 有些人第一眼看到这个问题,觉得用递归十分方便,便毫不犹豫的用了递归(这是某…

2013-08-07 18:32 · ACM-算法-数据结构 · 评论(0)

C# Xml文档操作快速上手

现在各大数据库公司都在开发Xml数据库(非关系型),而C#将对Xml的操作集成到了语言中,使得程序操作Xml 十分简便,现在让你快速上手Xml操作。 首先我们要知道Xml是树形结构,所以节点的概念十分重要。我们先要知道这些方法和类,具体的应用见下面的代码。 XmlDocument Xml文档类 重要方法有: Load(xmlPath); //载入Xml文档,xmlPath为路径 Save(xmlPath); //保存Xml文档 重要属性 DocumentElement //根节点 XmlElement 节点类 重要方法: PrependChild(XmlElement childNode);…

2013-07-21 13:39 · c # · 评论(0)

C++图形边缘检测与区域提取

边缘检索与区域提取是我们的课程设计的一个课题。看到这个课题感到十分新颖,因为以前从未接触过这方面的知识。而且由于课程作业要求的语言是c++,所以选择了 c++ 的一个界面类函数库easyX 下载可见官网 http://www.easyx.cn/ 我们将这个课题分为两部分,一是边缘检测,一是区域提取。 关于边缘检测:图像的边缘形成的原因是图像的灰度在某一区域的突然变化使得人眼才有了识别轮廓的功能。所以对于计算机识别边缘我们也可以用数学的方法定量的找出图像中灰度阶跃不连续或是线条不连续的地方,比如说一阶导数的极值点或二阶导数的零点的方法找到边缘。(图片摘自百度)。 当我们继续往下学时,越来越多的…

2013-07-21 10:42 · 算法 c++ · 评论(0)

分形基础及实例(java)

在我们这个美丽的世界,哪里都能够看到分型的影子,小到花草树木的花纹图案,大到宇宙万物。从大到小看来,它们都满足同样的规律,也就是迭代,用计算机的语言来说,这就是递归的内涵所在。 首次接触分形,就发现了它的魅力真的很大,一个对你来说似乎毫无意义的公式,通过用计算机根据这个公式不断迭代画上几十万个点后,竟然形成了想也想不到的美丽图形,如下图 如何画一个雪花曲线呢?对于新手来说,的确十分难。但彻底理解了递归的概念后,加上一点数学知识以及足够的耐心是能够画出来的,下面给出源代码及注释。 /********************************************************…

2013-03-21 14:47 · java基础 · 评论(0)

用java实现简单五子棋人人对战

用java实现简单五子棋人人对战,对于初学者还是比较好玩的。 接下来 看下我写的五子棋程序 我们将它分为三个类 1.主窗体类 2.鼠标事件处理器 3.判断一方是否胜利 比较简单,望大家多多指正 1.主窗体类 /**************************************************************************************************************************************/ package cn.lantian.Fivezq; import java.awt.Color; import j…

2013-01-18 20:47 · java基础 · 评论(0)

用java可视化编程实现计算器

我们可以用java实现一个简单的计算器 我们把它分为两个java文件一、计算器窗体部分,二、按键事件处理器部分。经过多次测试,解决了绝大部分bug,也许还有一些bug未发现,欢迎指正。 :D 下附计算器截图,有点丑,呵呵,但是是可以用的 :wink: 一、计算器窗体部分 /*****************************************************************/ package cn.lantian.Jisuan; import javax.swing.JButton; public class Jisuan{ public static void …

2013-01-17 19:19 · java基础 · 评论(0)

构造函数和图形界面开发

构造函数和图形界面开发。知道并理解了构造函数及重载的概念。 构造函数及重载的代码如下 public class Student{ //定义时不传入参数 public Student(){} //定义时传入名字 public Student(String name){ this.name=name; } //定义时传入学分 public Student(int score){ this.score=score; } //定义时传入名字和学分 public Student(String name,int score){ this.name=name; this.score=score; } } …

2013-01-17 12:20 · java基础 · 评论(0)