net_assassin的专栏

原创 COCI ‘20 Contest 1 #1 Patkice

COCI '20 Contest 1 #1 Patkice题目描述输入输出说明样例输入1样例输出1样例输出1的说明样例输入2样例输出2样例输出2的说明样例输入3样例输出3解释solution题目描述       不久前，在一个遥远的热带土地上，生活着三只橡皮鸭。 在一个炎热的夏日，鸭子躺在沙滩上时，他们决定前往附近的一个小岛。 由于鸭子喜欢冒险，所以他们决定利用洋流在旧的黑色雨伞中旅行。   &nbsp

翻译 [Usaco2011 November]Contest Timing比赛时间 Bronze

Problem 1: Contest Timing 比赛时间 [Brian Dean]Bessie正在参加在线编程比赛，比赛开始时间是2011年上午11点11分(D/H/M)（11/11/11），给定她结束比赛（最终提交）的时间，计算她本场比赛共花费多少分钟？ Bessie the cow is getting bored of the milk production industry, a...

转载 详解Bellman-Ford

一、Bellman-Ford算法：     为了能够求解边上带有负值的单源最短路径问题，Bellman(贝尔曼)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。    Bellman-ford算法是求解连通带权图中单源最短路径的一种常用算法，它允许图中存在权值为负的边。 同时它还能够判断出图中是否存在一个权值之和为负的回路。如果存在的话，图中就不存在最短路径(因

原创 短小精悍的线性筛法求素数

输入n，求n以内的所有素数算法用两个数组存储数据:一个是prime[]，存储n以内所有的素数，其index为pi，初值为0一个是is_prime[i]，表示自然数i(i

原创 快速幂

快速幂取模算法在网站上一直没有找到有关于快速幂算法的一个详细的描述和解释，这里，我给出快速幂算法的完整解释，用的是C语言，不同语言的读者只好换个位啦，毕竟读C的人较多~所谓的快速幂，实际上是快速幂取模的缩写，简单的说，就是快速的求一个幂式的模(余)。在程序设计过程中，经常要去求一些大数对于某个数的余数，为了得到更快、计算范围更大的算法，产生了快速幂取模算法。[有读者反映在讲快速幂部分时有点含糊，所

转载 扩展欧几里德算法求解线性同余方程

欧几里德算法　　欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：　　定理：gcd(a,b) = gcd(b,a mod b)　　证明：a可以表示成a = kb + r，则r = a mod b　　假设d是a,b的一个公约数，则有　　d|a, d|b，而r = a - kb，因此d|r　　因此d是(b,a mod b)的公约数　　假设d是(b,a mod

原创 N皇后问题

#include#include#includeusing namespace std;int search(int);int print();int n,sum = 0;int f[1001],b[1001] = {0},c[2002] = {0},d[2002] = {0};int main(){ cin>>n; search(1); s

原创 noip2010普及 排队接水问题

Description校里有一个水房，水房里一共装有 m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为 1。 现在有 n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从 1到 n 编号，i号同学的接水量为 wi。 接水开始时，1 到 m号同学各占一个水龙头，并同时打开水龙头接水。 当其中某名同学 j 完成其接水量要求 wj 后，下一名排队等候接水的同学 k

原创 2014年华为上机题目

华为2014校园招聘的机试题目和2013年的完全一样。一、题目描述（60分）：通过键盘输入一串小写字母(a~z)组成的字符串。请编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。比如字符串“abacacde”过滤结果为“abcde”。要求实现函数：void stringFilter(const char *pInputStr, long lInputL

原创 各种内部排序

#include using namespace std;void swap(int &x,int &y){ if (x != y) { int temp = x; x = y; y = temp; }}/////////////////////////////////////////////////////////////////////////InsertSor

原创 排序题目一网打尽

排序一、选择题1．某内排序方法的稳定性是指(    )。A．该排序算法不允许有相同的关键字记录      B．该排序算法允许有相同的关键字记录C．平均时间为0（n log n）的排序方法        D．以上都不对2．下面给出的四种排序法中(    )排序法是不稳定性排序法。    A. 插入           B. 冒泡              C. 二路归并   

原创 qq机制问题

登陆采用TCP协议和HTTP协议，你和好友之间发送消息，主要采用UDP协议，内网传文件采用了P2P技术。总来的说：1.登陆过程，客户端client 采用TCP协议向服务器server发送信息，HTTP协议下载信息。登陆之后，会有一个TCP连接来保持在线状态。2.和好友发消息，客户端client采用UDP协议，但是需要通过服务器转发。腾讯为了确保传输消息的可靠，采用上层协议来保证可靠传输。如

原创 华为2012上机题

输入一个int N   ，统计1-N中含有7或能被7整除的数的个数思路： 能被7整除的数很好求       N/7 个    。 再求1-N中含有7的数字个数。最后要减去重叠部分检测含有7的个数的代码如下：#include #include #include #include using namespace std;clock_t start,finish;int

原创 Effective C++ 读书笔记（七） 模板与泛型编程

7 模板与泛型编程面向对象virtual         运行时多态     显示接口     重载、template和泛型   编译期多态      隐式接口•    条款41：了解隐式接口和编译期多态                    Understand implicit interfaces and compile-time polymorphism.–

原创 Effective C++ 读书笔记（六） 继承与面向对象设计

条款32：确定你的pubilc继承塑模出is-a关系                                   Make sure public inheritance models “is-a”–  C++进行(OOP)面向对象编程,最重要的一个规则是：public inheritance （公开继承）意味“is - a”(是一种)关系。–  如果你令class D(“de

转载 编程之美3.6——编程判断两个链表是否相交

问题：给出两个单向链表的头指针，而两个链表都可能带环，判断这两个链表是否相交，并且给出他们相交的第一个节点。解法：参考http://blog.csdn.net/ldong2007/article/details/4544203(1)判断链表是否存在环设置两个链表指针(fast, slow)，初始值都指向链表头结点，然后连个指针都往前走，不同的是slow每

转载 数组分割

问题：1. 有一个无序、元素个数为2n的正整数数组，要求：如何能把这个数组分割为两个子数组，子数组的元素个数不限，并使两个子数组之和最接近。1. 解法1：由于对两个子数组和最接近的判断不太直观，我们需要对题目进行适当转化。我们知道当一个子数组之和最接近原数组之和sum的一半时，两个子数组之和是最接近的。所以转化后的题目是：从2n个数中选出任意个数，其和尽

转载 最长递增子序列 O(NlogN)算法 （ DP + 二分查找）

今天看编程之美，看到最长递增子序列问题。解法二看了两遍感觉越来越糊涂。感觉表述有欠妥之处。它不应该说长度为i的最大值的最小值，应该说成长度为i的序列中尾端最小的值。不知道表达明白了没有。看下面这个帖子吧，感谢felix的分享。看了好久好久，现在终于想明白了。试着把它写下来，让自己更明白。最长递增子序列，Longest Increasing Subsequence 下面我们简

转载 算法-求二进制数中1的个数

问题描述任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4这也是一道比较经典的题目了，相信不少人面试的时候可能遇到过这道题吧，下面介绍了几种方法来实现这道题，相信很多人可能见过下面的算法，但我相信很少有人见到本文中所有的算法。如果您上头上有更好的算法，或者本文没有提到的算法，请不要吝惜您的代码，分享的

转载 九种常用排序的性能分析总结

间间断断的将9种排序实现，并且将其以博客笔记的形式记录下来；现在就该来综合的分析这九种排序，让我们先来看看其算法复杂度和稳定性的分析结果：算法复杂度以及稳定性分析算法名称平均时间辅助空间稳定性冒泡排序O(n2)O(1)是选择排序O(n2)O(1)否插入排序O(n2)O(1)是

转载 求一个字符串中连续出现次数最多的子串

/* Author: Mcdragon Date: 15-07-11 21:17 Description: 求一个字符串中连续出现次数最多的子串. 基本算法描述: 给出一个字符串abababa 1.穷举出所有的后缀子串 substrs[0] = abababa; substrs[1] = bababa; substr

翻译 Chapter 3 | Stacks and Queues

Whether you are asked to implement a simple stack / queue, or you are asked to implement a modified version of one, you will have a big leg up on other candidates if you can flawlessly work with stack

转载 Const 重载解析(const参数重载 和 const成员函数重载)

书上和网上在很多地方都对const 的重载做了一些解释，但感觉都不是很详细。还有很多同学在不同的地方发问关于const 重载的问题，这里我又重新看了一下，做了一个简单的分析也可能有不对的地方，欢迎讨论。所谓重载，是指允许存在多个同名函数，而这些函数的参数表不同，即函数名相同但函数的签名不同。重载并不是面向对象编程的特有属性，这是因为重载是在编译阶段实现的，编译器根据函数不同的参数表，对同名函数

翻译 Chapter 2 | Linked Lists Cracking

2.1 Write code to remove duplicates from an unsorted linked list.FOLLOW UPHow would you solve this problem if a temporary buffer is not allowed?译文：从一个未排序的链表中移除重复的项进一步地，如果不允许使用临

翻译 Solutions to Chapter 1 | Arrays and Strings

1.1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?译文：实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)

原创 设计模式 连连看

原创 Proxy 模式

作用:为其他对象提供一种代理以控制对这个对象的访问#include using namespace std; class Subject{public: Subject(){} virtual ~Subject(){} virtual void request() = 0;private:};class RealSubject:public Su

原创 Effective C++ 读书笔记（五） 实现

5 实现          大多数情况下，适当提出拟的类定义以及函数声明，是花费最多心力的两件事。尽管如此，还是有很多东西需要小心：太快定义变量可能造成效率上的拖延；过度使用转型（casts）可能导致代码变慢又难维护，又招来微妙难解的错误；返回对象“内部数据之号码牌（handls）”可能会破坏封装并留给客户虚吊号码牌；为考虑异常带来的冲击则可能导致资源泄漏和数据败坏；过度热心地inlining

原创 Template Method 模式

Method模式作用:定义一个操作中的算法的骨架，而将一些步骤延迟到子类中。TemplateMethod 使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。UML结构图:现在看具体例子  泡茶喝泡咖啡

原创 Singleton模式

单线程singleton模式#include using namespace std; template class Singleton { public: static T* getInstance() { if( !instance ) { instance = new T(); } retu

原创 Effective C++读书笔记（四） 设计与声明

4 设计与声明•    软件设计，是“令软件做出你希望它做的事情”的步骤和做法，通常以颇为一般性的构想开始，最终演变成十足的细节，以允许特殊接口(interface)的开发，这些接口而后必须转换为C++声明式。条款18：让接口容易被正确使用，不易被误用               Makeinterfaces easy to use correctly and hard to use

转载 C++ 模板类型萃取技术 traits

自从C++中引入了template后，以泛型技术为中心的设计得到了长足的进步。STL就是这个阶段杰出的产物。STL的目标就是要把数据和算法分开，分别对其进行设计，之后通过一种名为iterator的东西，把这二者再粘接到一起。设计模式中，关于iterator的描述为：一种能够顺序访问容器中每个元素的方法，使用该方法不能暴露容器内部的表达方式。可以说，类型萃取技术就是为了要解决和iterator有关的

原创 Effective C++读书笔记

Effective C++ 改善程序与设计的55个具体做法让自己习惯C++条款01：视C++为一个语言联邦条款02：尽量以const，enum，inline替换#define条款03：尽可能使用const条款04：确定对象被使用前已被初始化构造、析构、赋值条款05：了解C++默认编写并调用哪些函数条款06：若不想使用编译器自动生成的函数，就该明确拒绝条款07：为

原创 Effective C++读书笔记（三） 资源管理

3 资源管理所谓资源就是，一旦用了它，将来必须还给系统。C++程序中最常使用的资源就是动态分配内存(如果你分配内存却从来不曾归还它，会导致内存泄露)，但内存只是你必须管理的众多资源之一。 条款13:以对象管理资源            Use object to manage resources.•    把资源放进对象内，我们便可依赖C++的“析构函数自动调用机制”确保资源被

原创 public、protected、private继承

C++类继承关系问题    在C++中继承主要有三种关系：public、protected和private。这三种继承关系中public继承是最为常用的一种继承关系，代表了接口继承含义，而他们分别具体代表了什么含义呢？1. public   从语义角度上来说，public继承是一种接口继承，根据面向对象中的关系而言就是，子类   可以代替父类完成父类接口所声明的行为，也就是

转载 C++的名称查找顺序

1。符号查找（对于函数此时只看名字，不看参数）    大致顺序是    (1)如果有限定名( XXX:: )那么就直接在XXX里查找    (2)函数局部名字空间    (3)(如果是成员)类名字空间    (4)递归向上至所有基类的名字空间    (5)当前名字空间    (6)递归向外至所有外层名字空间,    在任一层里, 用using导入的符号和该层的其他符

原创 Effective C++读书笔记（二）构造、析构、赋值

•条款05：了解C++默默编写并调用哪些函数•Know whatfunctions C++ silently writes and calls–C++会为默认的空类(emptyclass)添加•Default 默认构造函数•Copy 构造函数•析构函数•Copy assignment 复制赋值操作符–唯有这些函数被调用时，它们才会被编译器创建出来。–•条款06：

原创 设计模式——装饰者模式（Decorator）

装饰模式：动态地给一个对象添加一些额外的职责。就增加功能来说，装饰模式相比生成子类更为灵活。有时我们希望给某个对象而不是整个类添加一些功能。类继承可能会带来类数量爆炸等问题，设计死板。巴克莱咖啡，分店几乎开遍世界各地。他们发展的实在是太快了，所以他们此时正在急于实现一套由计算机管理的自动化记账系统。在第一次研究了他们的需求以后，开发者设计了如下图的类结构：

原创 Effective C++ 读书笔记（一）让自己习惯C++

1 让自己习惯C++条款01:  视C++为一个语言联邦        View C++ as a federation oflanguages           –  C。说到底C++仍是以C为基础。区块(blocks)、语句(statements)、预处理器(preprocessor)、内置数据类型(built-in data types)、数组(arrays)、指针(p

转载 C++拾遗

因为C++实在是过于复杂了，时不时都会碰见一些晦涩的细节，因此特意发个帖子，留好位置，随时添加Item 1    前置声明    当不需要class A的完整定义而只需要其名称时，可以通过前置声明函数来避免包含class A对应的头文件，这样可以减少编译依赖关系    然而，需要注意的是，string和iostream不是类型名，而是typedef;由于标准不允许向st