暂无个人介绍
poj-1182-食物链 //2014.4.11 HDOJ携程编程大赛预赛第二场第一题 Description 动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述: 第一种说法是"1
poj-1503-Integer Inquiry Description One of the first users of BIT's new supercomputer was Chip Diller. He extended his exploration of powers of 3 to go from 0 to 333 and he explored taking vari
jobdu--1521:二叉树的镜像 时间限制:1 秒内存限制:128 兆特殊判题:否提交:878解决:227 题目描述: 输入一个二叉树,输出其镜像。 输入: 输入可能包含多个测试样例,输入以EOF结束。 对于每个测试案例,输入的第一行为一个整数n(0<=n<=1000,n代表将要输入的二叉树节点的个数(节点从1开始编号)。接下来一行有n个数字,代表第i个二
图论总述 图的存储 图通常用G=(V,E)表示。V为顶点(vertex)集合,E为边(Edge)的集合。 图的物理存储,有两种方法。 1.邻接矩阵,就是二维数组,较直观,但不能存储重边。 2.邻接表,它是一种顺序与链式兼有的存储。 n个顶点的连通图至少有多少条边? 答:至少要有(n-1)条边。对于简单图而言至多有n*(n-1)/2条边,此时即是完全图。 图的遍历
POJ 1401 Factorial 题目略去。题很长,抽象过后就是求一个n的阶乘中0的个数。 分析:10=2*5,所以求最多有几对2和5就行。又考虑到2的个数肯定比5的个数多。所以只需要求5的个数。
jobdu-1188:约瑟夫环-ac 猴子选大王,如此经典的问题
HDOJ 2458 Kindergarten Description In a kindergarten, there are a lot of kids. All girls of the kids know each other and all boys also know each other. In addition to that, some girls and boys k
HDOJ 1068 Girls and Boys . Problem Description the second year of the university somebody started a study on the romantic relations between the students. The relation “romantically involved” is
软件工程 设计模式 适配器:封装一个对象,并提供接口的转换,主要的目的是在不修改已经存在的类的前提下,让他们可以在新的框架下面工作。 装饰者:封装一个对象,并提供额外的行为,用组合的方式来替代继承以扩展类的功能。 代理模式:封装一个对象,并控制它的访问,但是代理和被代理的对象有相同的接口(在c++里面有相同的基类)。 外观模式:封装许多对象,以简化它们的
有关编译原理 编译程序的逻辑结构:词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成。六个阶段。 1.词法分析 目的:识别字符串,识别出关键字、数字、运算符、变量名等,以二元式(类别,值)的形式存储,供后续的语法分析器用。 1.1文法: 一个文法可表示成形如G[S]=(Vn,Vt,P,S)的四元式。 Vn:非终结符号集; Vt:终结符号集; P:产生式集;
vector可以像数组一样使用。 erase()用法
deque queue and priority_queue stl-deque deque 是双端队列,可实现栈与队列的操作。 deque支持deque_ob[i] 形式的随机存取。 stl-queue queue的基本操作有: 入队,如例:q.push(x); 将x 接到队列的末端。 出队,如例:q.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素
查找与散列(Hash) 1.查找的一些概念 查找——在给定集合中查找特定的元素。 在查找的过程中,查找的长度是指关键字间的比较次数,而平均查找长度则是数学上的期望:ASL=P1*C1+P2*C2+...+Pn*Cn。 Pi为查找第i个元素的概率,Ci为查找第i个元素所需的查找长度。一般认为每个元素查找概率相同。平均查找长度分为查找成功和查找不成功长度两种。 对于顺序查找来说。ASL
stl-set set/multiset会根据待定的排序准则,自动将元素排序。两者不同在于前者不允许元素重复,而后者允许。 1) 不能直接改变元素值,因为那样会打乱原本正确的顺序,要改变元素值必须先删除旧元素,则插入新元素 2) 不提供直接存取元素的任何操作函数,只能通过迭代器进行间接存取,而且从迭代器角度来看,元素值是常数 3) 元素比较动作只能用于型别相同的容器(即元素和排序准
二叉树的非递归遍历 java的非递归后续遍历
和的加数分解
内存管理 对进程按固定大小进行划分,单位为页;对主存按同样大小进行划分,叫页框。一个页刚好对应一个页框。 那么进程内的指令或数据的地址表示为:页号,页内偏移量。 操作系统为每个进程分配一张页表,内容为:页号,该页内存地址。用于实现逻辑地址到物理地址的映射。 页面置换算法:LRU。 LRU是Least Recently Used 近期最少使用算法。即把最久未访问的页框置换出去
二叉搜索树 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树。 搜索:从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右
n个结点的二叉链表中含有n+1(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附加的指针称为"线索")。
阿里2014实习生招聘 问:某国家非常重男轻女,若一户人家生了一个女孩,便要继续生,直到得到男孩为止。假设生男生女概率相等,请问平均每户人家有(1)个女孩。 答:此题即高数中的级数。 引申: int f(int x){ int s=0; while(x--) s+=f(x); return max(x,1); } //若调用f(35)
静态成员: 友元函数与友元类: 常对象 与常成员 只有类的常成员函数才能访问该类的常对象,但也只能读不能改。 常对象只能调用常成员函数。
对以往数据分析结果表明,当机器调整得良好时,产品的合格率为98%,而机器发生某一故障时,产品的合格率为55%,每天早上机器开动时,机器调整达良好的概率为95%。试求已知某日早上第一件产品是合格品时,机器调整达良好的概率是多少? 答: 设事件A:产品合格;B:机器调整良好。已知P(A|B)=0.98,P(A|B的逆)0.55,P(B)=0.95。 求P(B|A)。 P(B|A)=P(
数字机内存储 原码(true form)是一种计算机中对数字的二进制定点表示方法。原码表示法在数值前面增加了一位符号位(即最高位为符号位):正数该位为0,负数该位为1(0有两种表示:+0和-0),其余位表示数值的大小。 反码表示法规定:正数的反码与其原码相同;负数的反码是对其原码逐位取反,但符号位除外。 补码(two's complement)——在计算机系统中
字节对齐 c++的字节对齐可以提高数据的存取效率。 1.默认情况 类中或结构体中各成员变量在存放的时候根据在结构中声明的顺序依次申请空间,其在结构体中相对于始址的偏移量必须为自身所占字节的整数倍,否则编译器会为上个成员变量追加内存分配。 类的嵌套定义、静态成员、函数等均不算进sizeof()里面。 同时VC为了确保结构体的大小为结构的字节边界数(即该结构体中占
assert ()断言,为真继续,为假终止。 异常处理更为高级,可处理相应异常。 C++的异常处理引入了三个关键字 try(检测异常)、throw(抛出异常)、catch(捕获异常)。 try 负责监视可能出现异常的程序段。若该段出现异常,程序将不再按原有流程走,而是被throw抛出异常,程序控制权交给catch子句,然后从catch块处顺序执行。 try 与 catch 语
位运算 我们先来看看位运算操作符:& (按位与)、| (按位或)、^ (按位异或)、~ (按位取反)、>> (按位右移)、<< (按位左移)。 位运算符优先级比+低,注意加小括号! 1、&(按位与) 从概念上来讲,就是将参与运算的两个分量对应的每一位来做逻辑与运算,若两者都为真(等于1),则结果才为真(等于1)。否则都为假(等于0)。
题目1459:Prime ring problem 时间限制:2 秒内存限制:128 兆特殊判题:否提交:747解决:306 题目描述: A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ..., n into each circle separately, and the sum
十进制转二进制 安全性检查略 atoi 基本版:抛出异常 int f_convert(char *str) throw (char*) { //数字字符串转换为int型 if(!str){ char*a="pointer is NULL\n"; throw(a); } int tmp=0; int len
二叉树的性质 二叉树是图的一种特殊情形。 二叉树与有序树:在只有一个孩子结点的情况下,二叉树有左右之分、有序树无左右之分。 非空二叉树中,共有n个结点,度为0的结点有n0个,度为1的结点有n1个,度为2的结点有n2个,则n0=n2+1; 推导:n=n0+n1+n2; n-1=n1+2*n2; 联立得解。(最爱考这个了...) 非空二叉树第i层
二叉树相关函数小汇 到处都是递归,真妙! int ask_height(node *);// 求二叉树的高度 bool is_balanced(node* ,int &);//判断是否为平衡二叉树 node * tree_build(string ,string );//根据先序和中序遍历,建立二叉树 void tree_back_travel(node*);//后序
题目1078:二叉树遍历 时间限制:1 秒内存限制:32 兆特殊判题:否提交:2013解决:1212 题目描述: 二叉树的前序、中序、后序遍历的定义: 前序遍历:对任一子树,先访问跟,然后遍历其左子树,最后遍历其右子树; 中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树; 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。 给定一棵二叉树的
1045: [HAOI2008] 糖果传递http://www.lydsy.com/JudgeOnline/problem.php?id=1045 Time Limit: 10 Sec Memory Limit: 162 MB Submit: 1416 Solved: 658 [Submit][Status] Description 有n个小朋友坐成一圈,每人有ai个糖果
积累(一) C++的多态——编译时多态与运行时多态。前者指重载(同名函数对应不同的函数体定义);后者指虚函数(动态绑定)。 struct的成员默认是public,class的成员默认是private。 对于派生类的构造函数,在定义对象时构造函数的执行顺序为? 答:1.基类的构造函数 2.成员对象所在类的构造函数 3.派生类自己的构造函数。 定义一个函数指针,指向的函数有两个in
分治的思想,即把大问题分解成子问题加以解决。 代码
虚函数、抽象类及虚基类 虚函数及抽象类: 派生类经常(但不总是)覆盖它继承的虚函数。如果没有覆盖,派生类会直接继承其在基类中的版本。 派生类可以在它覆盖的函数前使用virtual关键字,但不是非得这么做。 C++11允许派生类使用override关键字,显式地注明它重写了基类中的某个虚函数。 常见的不能声明为虚函数的有:非成员函数(含友元函数);静态成员函数;构造函数。
1.类的定义与使用 C++还支持类的嵌套定义。 类中除了能定义成员,还可以定义类型。 class A{ public: typedef int cc_int; }; int main(int argc, char *argv[]) { A::cc_int x=1; cout<<x; //1 return 0;
1.变量的声明、定义、初始化 一个程序可由多个源文件实现。 变量可以多次声明,但只能被定义一次。 声明通过extern关键字实现。 extern int i; //声明 int j; //定义 2.变量的内存存放 全局变量与局部变量在没有初始化时,取初值的方式不同。前者是全0. c++内存分为代码、堆、栈、常量和全局//静态存储区。 不同变量的存储位置: 全局/
(字符)数组、指针与引用类型 指针、引用 在函数形参中的作用 : 指针与引用有何区别? 1.从内存上来讲,系统为指针分配内存空间,而引用与绑定的对象共享内存空间,系统不为引用变量分配内容空间。 2.指针初始化以后可以改变指向的对象,而引用定义的时候必须要初始化,且初始化以后不允许再重新绑定对象。 引用作函数的返回值 以引用类型作为函数的返回值,在函数调用时,若接受返回
函数 函数就是能够执行特定功能的有名字的语句块。 函数声明中的参数叫形参,函数调用中的参数叫实参。 整个cpp源文件中,除了声明以外的语句必须放在函数体中。 x/0会导致 RunTime Error。 数组越界可能会改到合法数据,埋下隐患,或直接崩溃。 调用函数的过程: 1.将调用语句的下一个语句地址入栈,以便调用后返回;将实参从右往左入栈;2.实参出栈,值给形参;函数执行;3
数据类型与表达式 cout操纵符:hex,十六进制 oct八进制 dec十进制(默认) 进制表示:八进制以数字0为前缀;十六进制以0X或0x做前缀。(是数字0,不是字母o) double型数字判断相等可以用 fabs(a-b)<1e-6 转义符:反斜线\ \a为响铃 一个语句太长可以分行写,行尾要用‘\’(注意其后不能有空格) 注意区分逻辑运算符与关系运算符。
题目1530:最长不重复子串 时间限制:1 秒内存限制:128 兆特殊判题:否提交:816 解决:263 题目描述: 最长不重复子串就是从一个字符串中找到一个连续子串,该 子串中任何两个字符都不能相同,且该子串的长度是最大的 。 输入: 输入包含多个测试用例,每组测试用例输入一行由小写英文 字符a,b,c...x,y,z组成的字符串,字符串的长度不大于 10000。
数学 字符相关 字符串相关 随机数及atoi 注意C++11有更强大的方法! time相关
#include <set> 一个集合(set)是一个容器,存储的多个元素不允许重复。 集合中的元素默认按升序排列。一个集合通过一个链表来组织,在插入操作和删除操作上比向量(vector)快,但查找或添加末尾的元素时会有些慢。具体实现采用了红黑树的平衡二叉树的数据结构。 集合不能随机存储,只能通过iterator++来遍历。 成员函数: begin() 返回指向第一个
题目1537:买卖股票 时间限制:1 秒内存限制:128 兆特殊判题:否提交:616解决:164 题目描述: 给定一个大小为n的数组,数组的元素a[i]代表第i天的股票价格。 设计一个算法,计算在最多允许买卖k次(一买一卖记为一次)的条件下的最大收益。 需要注意的是,你不能同时拥有两份股票。也就是说在下次买入前,你必须把手头上原有的股票先卖掉。 输入: 输入可能包含多个测试案
题目1552:座位问题 时间限制:1 秒内存限制:128 兆特殊判题:否提交:313 解决:95 题目描述: 计算机学院的男生和女生共n个人要坐成一排玩游戏,因为计算机的女生都非常害羞,男生又很主动,所以活动的组织者要求在任何时候,一个女生的左边或者右边至少有一个女生,即每个女生均不会只与男生相邻。现在活动的组织者想知道,共有多少种可选的座位方案。例如当n为4时,共有 女女女女,
cin/printf 重定向 OJ 重定向模板 IO重定向 重定向后如何恢复到 控制台IO ? 答:需在重定向前做好备份。 fstream inFile,outFile; streambuf *stdcin,*stdcout; stdcin=cin.rdbuf(); stdcout=cout.rdbuf(); //提前备份 inFile.open
jobdu----题目1527:首尾相连数组的最大子数组和 时间限制:1 秒内存限制:128 兆特殊判题:否提交:1769 解决:335 题目描述: 给定一个由N个整数元素组成的数组arr,数组中有正数也有负数,这个数组不是一般的数组,其首尾是相连的。数组中一个或多个连续元素可以组成一个子数组,其中存在这样的子数组arr[i],…arr[n-1],arr[0],…,arr[j
题目1551:切蛋糕 时间限制:1 秒内存限制:128 兆特殊判题:否提交:266 解决:90 题目描述: 有如下图半价为R的圆形蛋糕,被切一刀后(图中红色直线 ),分成两个部分(黄色和绿色),已知其比例为r,求刀 痕长度(图中红色直线)。 输入: 输入包括多组测试数据,包括一个整数R(1<=R<=1000),和一 个浮点数r(0<r<1),精确到
题目1049:字符串去特定字符 时间限制:1 秒内存限制:32 兆特殊判题:否提交:4840解决:2166 题目描述: 输入字符串s和字符c,要求去掉s中所有的c字符,并输出结果。 输入: 测试数据有多组,每组输入字符串s和字符c。 输出: 对于每组输入,输出去除c字符后的结果。 样例输入: heallo a 样例输出: hello 来源: 2009年哈尔滨工业
题目1076:N的阶乘 时间限制:3 秒 内存限制:128 兆 特殊判题:否 提交:3986 解决:1304 题目描述: 输入一个正整数N,输出N的阶乘。 输入: 正整数N(0<=N<=1000) 输出: 输入可能包括多组数据,对于每一组输入数据,输出N的阶乘 样例输入: 4 5 15 样例输出: 24 120 130767