九度笔记之项目安排

“一颗咸鸭蛋”通过精心收集，向本站投稿了8篇九度笔记之项目安排，下面是小编整理后的九度笔记之项目安排，欢迎大家阅读借鉴，并有积极分享。

九度笔记之项目安排

篇1：九度笔记之项目安排

题目描述：

小明每天都在开源社区上做项目，假设每天他都有很多项目可以选，其中每个项目都有一个开始时间和截止时间，假设做完每个项目后，拿到报酬都是不同的，由于小明马上就要硕士毕业了，面临着买房、买车、给女友买各种包包的鸭梨，但是他的钱包却空空如也，他需要足够的money来充实钱包。万能的网友麻烦你来帮帮小明，如何在最短时间内安排自己手中的项目才能保证赚钱最多（注意：做项目的时候，项目不能并行，即两个项目之间不能有时间重叠，但是一个项目刚结束，就可以立即做另一个项目，即项目起止时间点可以重叠）。

输入：

输入可能包含多个测试样例。

对于每个测试案例，输入的第一行是一个整数n(1<=n<=10000)：代表小明手中的项目个数。

接下来共有n行，每行有3个整数st、ed、val，分别表示项目的开始、截至时间和项目的报酬，相邻两数之间用空格隔开。

st、ed、value取值均在32位有符号整数（int）的范围内，输入数据保证所有数据的value总和也在int范围内。

输出：

对应每个测试案例，输出小明可以获得的最大报酬。

样例输入：

1 3 6

4 8 9

2 5 16

1 14 10

5 20 15

15 20 8

18 22 12样例输出：

22算法分析

本题采用回溯法，假定安排了第k个项目后，下一个项目的开始时间肯定在k个项目时间的结束之后。

数据结构

Project

int

代表项目名

Order

int

代表按照项目的开始时间排序后，该项目的序号，从0开始

btime

int

项目起始时间

etime

int

项目结束时间

int

项目收益

在回溯过程中需要查找某个项目的next项目和adjacent项目，为了加快计算速度，所以提前对项目按照开始时间进行排序。

Next项目指某个项目做完后可以接着做的项目

Adjacent项目是指比某个项目开始时间相同或晚一些的项目

现在来讲述具体算法流程

void manageP(int curOrder,int curpf,const std::vector

&pv)

pv为已经排好序的项目列表

假定已经安排了几个项目，最后一个为curOrder(排序序列号), 求得curOrder的Next项目nextOrder

(1)将nextOrder放入计划。

manageP(nextOrder,curpf+pv.at(nextOrder).pf,pv);

在此要判断nextOrder是否存在，也就是计划是否已经满了，是的话就比较当前的获益，如果比allpf大，就更新allpf.

(2)不加入nextOrder,而是加入nextOrder的adjacentOrder

manageP(adjacentOrder,curpf+pv.at(adjacentOrder).pf,pv);

在此也要判断nextOrder是否是最后一个项目，如果是的话就不存在adjacentOrder，计划已经结束，判断当前收益是否大于allpf.

我们还需要考虑另外一种情况，adjacentOrder的开始时间>=nextOrder的结束时间

在这种情况下得到的收益肯定不是最大，因为中间可以插入nextOrder项目

代码

[cpp]

// test1499.cpp : 定义控制台应用程序的入口点。

#include “stdafx.h”

#include

struct Project{

int id;

int order;//记录排序后的位置，便于搜寻下一个项目

int btime;

int etime;

int pf;

};

//std::vector

userp;

int allpf=0;//盈利

bool lessthan(const Project &a,const Project &b){

return a.btime < b.btime;

}

int getNextP(int curOrder,const std::vector

&pv){//得到和项目cur时间不重叠的下一个项目

if(curOrder==-1)

return 0;

std::vector

::const_iterator cit = pv.begin + curOrder +1;

for(;cit!=pv.end();cit++){

if(cit->btime >= pv.at(curOrder).etime){

return cit->order;

}

if(cit==pv.end()){

return -1;

}

int getAdjacentP(const Project &cur, const std::vector

&pv){//得到开始时间在项目cur开始时间之后或重合的下一个项目

if(cur.order == pv.size()-1)

return 0;

else

return cur.order+1;

}

void manageP(int curOrder,int curpf,const std::vector

&pv){//已经加入了k-1个项目，k-1为cur项目

//加入

int nextOrder;

nextOrder = getNextP(curOrder,pv);

if(nextOrder==-1){

if(curpf>allpf)

allpf = curpf;

return;

}else{

manageP(nextOrder,curpf+pv.at(nextOrder).pf,pv);

}

if(nextOrder == pv.size()-1){ //nextOrder是最后一个项目

if(curpf+pv.at(nextOrder).pf > allpf){

allpf = curpf+pv.at(nextOrder).pf;

return;

}

}else{

int adjacentOrder = nextOrder+1;

if(pv.at(adjacentOrder).btime >= pv.at(nextOrder).etime){ //adjacentOrder开始时间在nextOrder结束时间之后

//得到的利润肯定没有加上nextOrder的多

return;

}else{

manageP(adjacentOrder,curpf+pv.at(adjacentOrder).pf,pv);

}

void test1499(int n){

int i = 0;

Project p;

std::vector

pv;

while(i++

std::cin>>p.btime>>p.etime>>p.pf;

p.id = i;

p.order = 0;

pv.push_back(p);

}

std::sort(pv.begin(),pv.end(),lessthan);

for(std::vector

::size_type st = 0;st

pv.at(st).order = st;

}

manageP(-1,0,pv);

std::cout<

}

int _tmain(int argc, _TCHAR* argv[])

{

int n =0;

while(std::cin>>n){

test1499( n);

}

return 0;

}

// test1499.cpp : 定义控制台应用程序的入口点，

#include “stdafx.h”

#include

struct Project{

int id;

int order;//记录排序后的位置，便于搜寻下一个项目

int btime;

int etime;

int pf;

};

//std::vector

userp;

int allpf=0;//盈利

bool lessthan(const Project &a,const Project &b){

篇2：九度笔记之 1252：回文子串

题目描述：

输入一个字符串，输出该字符串中对称的子字符串的最大长度，

比如输入字符串“google”，由于该字符串里最长的对称子字符串是“goog”，因此输出4。

输入：

存在多组数据，每组数据一行字符串，长度不大于100。

输出：

输出回文子串的最大长度。

样例输入：

google

样例输出：

算法分析：

本来打算用《最长合法括号序列1》中的算法，利用动态规划做，但是对于例如“aaa”的情况该算法就无效了

因为括号必须是左右一对同时出现，左边的必为”(“，右边的必为”)“，所以当出现str[pos]==”(”或 str[sympos]<0 或str[sympos]==”)”的情况时，str[pos]位置的符号不可能再和dp[pos-1]合法子括号序列的子字符串构成合法括号序列。

(()(

)()(

())

)())

对于回文字符串，则会出现以下情况

aaa

dp[1]=2 ,

pos==2时，sympos== -1,得到dp[pos]=1 实际上dp[pos]=3

因为a[1]相当于一个回文字符串，str[0]==str[2]，dp[pos]=3

abadabad

dp[6]=7,

pos==8时，sympos== -1,得到dp[pos]=1 实际上dp[pos]=5

因为abadaba中的子字符串aba为一个回文字符串，str[3]==str[7],故dp[pos]=5

公共子序列查找

新的思路就是，如果字符串s中含有回文字符串，回文字符串一定为该字符串的逆序列rs和该字符串s的公共子序列，如下所示。

google s

elgoog sr

abamngnm s

mngnmaba sr

算法实现就很简单了，从sr的某个位置开始，s从0开始逐个字符比较，记录最长的公共序列。

源代码：

程序中需要注意的是srbegin的每次循环，temLen都要重新置为0

srid的每次循环结束后，也要判断一下temLen和maxLen的大小，

google s

elgoog sr

在sid==3,srid==5时，

sr.at(srid)==s.at(sid)

temLen++;

srid++;sid++;

循环退出，此时temLen==4,maxLen==0

还有就是考虑到sr需要前向错位，后向错位来比较，所以需要将s,sr反过来比较一下。参看int getMaxNum(std::string &s)

#include

using namespace std;

int getMaxNum(std::string &s,std::string &sr){

int sLen = s.size();

int maxLen = 0;

int temLen = 0;

* google s

* elgoog sr

* abacdefgfedcmnm

* mnmcdefgfedcaba

int srbegin = 0;

while(srbegin < sLen){// sr start from i compare s

int srid = srbegin;

int sid = 0;

temLen = 0; //attention

while(srid < sLen){

if(sr.at(srid)==s.at(sid)){

temLen++;

}else{

if(temLen > maxLen)

maxLen = temLen;

temLen=0;

//break;

}

srid++;

sid++;

}//while(srid < sLen)

if(temLen>maxLen) //attention srid==sLen must be considered for “google”

maxLen = temLen;

srbegin++;

}

return maxLen;

}

int getMaxNum(std::string &s){

std::string sr(s.rbegin(),s.rend());

int maxLen = 0;

maxLen = getMaxNum(s,sr);

int rMaxLen = getMaxNum(sr,s);

if(rMaxLen>maxLen)

return rMaxLen;

else

return maxLen;

}

void test(){

std::string s = “ab”;

std::string sr(s.rbegin(),s.rend());

std::cout<<

}

void judo(){

std::string s;

//int temLen = 0;

while(std::cin>>s){

std::cout<<

}

int main() {

//cout << “!!!Hello World!!!” << endl; // prints !!!Hello World!!!

judo();

return 0;

}

/**************************************************************

Problem: 1252

User: KES

Language: C++

Result: Accepted

Time:10 ms

Memory:1520 kb

****************************************************************/

篇3：“笔记”之死得其所

“笔记”之死得其所

中午，我去买了支笔芯，写起了日记。刚开始还满好的，可是好景不长任性的笔芯，它却不奉献了――故意不捐“血”――写不出字。

我给它戴上“保护盖”和“帽子”好，我虐待似的.把它“倒立”――笔尖朝下只敲，看能否有效。我一试，它像怕我似的“大出血”。可一会儿又开始反抗了，我把全身的力量转向右手，用力一敲。我正心想它应该会乖乖的听话了吧，谁知道笔尖和身子一分为二了！唉，怎么又坏了。可“死”也死的光荣，如人死了可以捐器官，它死了就可以把“衣服”留给后来人。

然后，以中国化的形式把它勾勒出，再加以装饰打扮，一个个颇具高贵品质的梅，松，竹，菊都问世了！

我想这就是“死得其所”了吧！

篇4：Linux学习笔记之――Linux相关

简单的来说，操作系统主要分为两个东西，一个是内核、一个是一堆核心提供的工具、这一堆工具组成的就是所谓的操作系统。

内核负责控制硬件资源分配，而如果只有内核，则只能让计算机硬件运行，而不能有任何功能，因此需要系统调用提供给开发者使用，从而开发应用程序；内核能够控制硬件，比如：让CPU可以运算、让硬盘可以读写数据等；只有内核的话，只能让计算机运行，但是我们不能控制计算机。

而系统调用是操作系统提供给开发者的调用接口。任何硬件都不会默认就作系统控制，而需要开发商根据操作系统提供的接口开发驱动程序，只有安装了驱动程序才能够控制硬件设备。

篇5：Linux学习笔记之――Linux相关

1、Linux起源

Unix操作系统在20世纪60年代构思完成并实现，并在1970年首次发布。它因容易获取与可移植性高而广泛被学术机构和工商企业采用、复制和修改。它的设计对其他系统的作者影响很大。

在1983年，RichardStallman创建了以创建一个自由软件，类Unix，与POSIX兼容的操作系统为目标的GNU计划。作为这个计划其中的一部分，他又写了GNU通用公共许可证（GPL）。20世纪90年代初，已经有足够的软件去创建一个完整的操作系统。但是，GNU的内核，GNU Hurd没能够充分吸引开发者；这导致了GNU的未能完成。

在20世纪80年代还有另外一个关于自由操作系统的项目，伯克利软件包。这是由UC Berkeley从AT&T的第六版Unix开发而来的。因为它包含了AT&T所拥有的的Unix代码，所以AT&T在20世纪90年代初对加利福尼亚大学提起了法律诉讼。这严重限制了BSD的发展与应用。

1987年安德鲁·斯图尔特·塔能鲍姆发布一个用于教学的类Unix系统。虽然系统的源代码容易得到，但是对源代码的修改与再发布却受到了限制。另外，MINIX的16位的设计与当时日渐便宜及受欢迎的、个人电脑的Intel 80386架构兼容得不好。

这些因素使得Torvalds开始了他的项目。他曾说过，如果那时候有可用的GNU或者386BSD内核的话，他很可能就不会去写他自己的内核了。

2、Linux诞生：

1991年，在赫尔辛基，LinusTorvalds开始那个后面成为了Linux内核的项目。最初它只一个Torvalds用来访问大学里的大型的Unix服务器的虚拟终端。他专门写了一个用于他当时正在用的硬件的，与操作系统无关的程序，因为他要用他那用80386处理器的新PC机的功能。开发是在Minix上，用至今仍为首先的编译器——GCC——来完成的。

Torvalds在他的书只为欢乐中说过，他最后才意识到自己写了一个操作系统内核。1991年8月25日，他在发布到新闻组“comp.os.minix.”的Usenet上发布了这个系统：

“ 使用minix操作系统的各位，大家好！

我正在为386（486）AT clones写一个（自由的）操作系统（只是爱好而已，不会和GNU一样成为广泛且专业的操作系统）。这个计划从4月份开始酝酿，现在已做好准备。我希望得到人们关于minix优缺点的任何反馈意见，因为我的操作系统和它有类似的方面（因为可行性方面的原因，两者的文件系统物理布局相同）。我刚刚把bash(1.08)和gcc(1.40)移植到了系统上，而且看来运行得很好。这意味着我可以在几个月内我就可以把它变得有实用性了。我想知道大家想要些什么特色。欢迎提任何的建议，但是我不保证我会实现你的建议:-)

Linus (torvalds@kruuna.helsinki.fi)

另：是的，它没有包含任何minix的代码；它的文件系统还是一个多线程的。它没有可移植性（它利用了386的任务调度算法等），而且它很可能永远只会支持AT的硬盘（我只有这种硬盘:-( ）

”

——Linus Torvalds

3、Linux名称的由来

Linus Torvalds本要把他的发时叫做Freax——“fread”，“free”和“x”（暗指Unix）的合成词。在开发系统的前半年里，他把文件以文件名“Freax”存储。Torvalds考虑过Linux这个名字，但是因为觉得它过于自我本位而放弃了使用它。

为便于开发，在1991年9月，他把那些文件上传到了赫尔辛基工业大学（HUT）的FTP服务器（ftp.funet.fi)。Torvalds在HUT负责管理那个服务器的同事Ari Lemmke，觉得“Freax”这个名字不是很好，就在不咨询Torvalds的情况下，把项目的名字改成了“Linux”。但是之后，Torvalds也同意“Linux”这个名字了：“经过多次讨论，他承认Linux这个名字更好。在0.01版本Linux的源代码的makefile里仍然使用‘Freax'这个名字，在之后‘Linux'这个名字才被使用，

所以，Linux这个名字并不是预先想好的，只是它被广泛接受了而已”。

4、Linux吉祥物的由来

Linux的吉祥物是企鹅（英文名：Tux），因为Torvalds在小时候被企鹅咬过，因此印象非常深刻；

5、Linux的优缺点

优点：

a）稳定的系统：Linux 本来就是建立在 Unix 上面发展出来的操作系统，因此，Linux 具有与 Unix 系统相似的的程序接口跟操作方式，当然也继承了 Unix 稳定并且有效率的特点。常听到安装 Linux 的主机连续运做一年以上而不曾当机、不必关机是稀松平常的事；

b）免费或少许费用：由于 Linux 是基于 GPL 的基础下的产物，因此任何人皆可以自由取得 Linux ，至于一些『安装套件』的发行者，他们发行的安装光盘也仅需要些许费用即可获得！不同于 Unix 需要负担庞大的版权费用，当然也不同于微软需要一而再、再而三的更新你的系统，并且缴纳大量费用！

c）安全性、漏洞的修补：如果你常玩网络的话，那么你最常听到的应该是『没有绝对安全的主机』！没错！不过 Linux 由于支持者日众，有相当多的热心团体、个人参与其中的开发，因此可以随时获得最新的安全信息，并给予随时的更新，亦即是具有相对的较安全！

d）多任务、多使用者：与Windows 系统不同的， Linux 主机上可以同时允许多人上线来工作，并且资源的分配较为公平，比起 Windows 的单人假多任务系统要稳定的多！这个多人多任务可是 Unix-Like 上面相当好的一个功能，怎么说呢？你可以在一部 Linux 主机上面规划出不同等级的使用者，而且每个使用者登入系统时的工作环境都可以不相同，此外，还可以允许不同的使用者在同一个时间登入主机，以同时使用主机的资源。

e）使用者与群组的规划：在 Linux 的机器中，档案的属性可以分为『可读、可写、可执行』等参数来定义一个档案的适用性，此外，这些属性还可以分为三个种类，分别是『档案拥有者、档案所属群组、其它非拥有者与群组者』。这对于项目计划或者其它计划开发者具有相当良好的系统保密性。

f）相对比较不耗资源的系统

缺点：

a）有些专业软件没有Linux版本；

b）图形接口作的还不够好

6、Linux的发展史

20世纪60年代，MIT开发分时操作系统（CompatibleTIme-Sharing System），支持30台终端访问主机；

～主机负责运算，而终端负责输入输出；

1965年，Bell实验室、MIT、GE（通用电气公司）准备开发Multics系统，为了同时支持300个终端访问主机，但是1969年失败了；

～刚开始并没有鼠标、键盘，输入设备只有卡片机，因此如果要测试某个程序，则需要将读卡纸插入卡片机，如果有错误，还需要重新来过；

～Multics：MultiplexedInformation and Computing Service

1969年，Ken Thompson（C语言之父）利用汇编语言开发了FIle Server System（Unics，即Unix的原型）

～因为汇编语言对于硬件的依赖性，因此只能针对特定硬件；

～只是为了移植一款“太空旅游”的游戏；

1973年，Dennis Ritchie和Ken Thompson发明了C语言，而后写出了Unix的内核

～将B语言改成C语言，由此产生了C语言之父；

～90%的代码是C语言写的，10%的代码用汇编写的，因此移植时只要修改那10%的代码即可；

1977年，Berkeley大学的Bill Joy针对他的机器修改Unix源码，称为BSD（BerkeleySoftware Distribution）

～ Bill Joy是Sun公司的创始人；

1979年，Unix发布System V，用于个人计算机；

1984年，因为Unix规定：“不能对学生提供源码”，Tanenbaum老师自己编写兼容于Unix的Minix，用于教学；

1984年，Stallman开始GNU（GNU's NotUnix）项目，创办FSF（Free Software Foundation）基金会；

～产品：GCC、Emacs、Bash Shell、GLIBC；

～倡导“自由软件”；

～ GNU的软件缺乏一个开放的平台运行，只能在Unix上运行；

～自由软件指用户可以对软件做任何修改，甚至再发行，但是始终要挂着GPL的版权；

～自由软件是可以卖的，但是不能只卖软件，而是卖服务、手册等；

1988年，MIT为了开发GUI，成立了XFree86的组织；

1991年，芬兰赫尔辛基大学的研究生LinusTorvalds基于gcc、bash开发了针对386机器的Lniux内核；

1994年，Torvalds发布Linux-v1.0；

，Torvalds发布Linux-v2.0，确定了Linux的吉祥物：企鹅；

7、Linux内核版本的介绍

Linux的内核版本分为稳定版本和开发版本；

此版本如果是偶数，则为稳定版本，如果是奇数，则为开发版本，内核开发人员使用；

释放版本为对次版本的改动，即加入一些功能；

修改版本为编译的次数，每次加一；

篇6：简化“之”的笔记(网友来稿)

湖北谷城三中胡文勇

“之”在文言文中用法灵活，出现频率高，特别是做助词时，用法繁多，初学者做起笔记来，如果不运用正确的简化方法，要么空耗时间，要么效果不佳，甚至多走弯路。

笔者认为要简化其笔记，首先要掌握其做助词的基本用法：

①用在定语和中心语之间，相当于“的”。例如：古之学者。②用在主谓语之间，取消句子的独立性。例如：师道之不传也久矣。③定语后置的.标志，用在中心语与定语之间。例如：蚓无爪牙之利，筋骨之强。④宾语前置的标志，用在宾谓之间。例如：句读之不知，惑之不解。⑤补语的标志，用于谓语与补语之间。例如：以其求思之深而无不在也。⑥用在表示时间的副词之后，补足音节，没有实在意义。例如：顷之，久之。

掌握了以上用法，做笔记时先可以简化为：①定中之间。②主谓之间。③中定之间。④宾谓之间。⑤谓补之间。⑥音节助词。熟练了，还可以简化为：定中、主谓、中定、宾谓、谓补、音节。

世上无难事，只怕有心人，只要掌握了规律，方法得当，“之”的用法也容易掌握。

作者邮箱： SANREN123456@TOM.COM

篇7：Python笔记之文件

1，文件打开和创建#file用于文件管理file(name, mode [, buffering]])name为文件名，存在－打开；不存在－创建mode为打开模式，r, r+, w, w+, a, a+, b, U等

2，读取文件

#open（）读取文件data=open(‘file_name’) #打开一个文件print( data.redline, end=‘ ‘) #用readline()读取一个数据行data.seek(0) #回到文件起始位置for line in data print(line, end=‘ ‘)data.close() #关闭文件

读取文件的方式#1）按行读取

f = open(“file.txt”)while True: line = f.readline() if line: print line else: break;f.close()

#2)多行读取

f = open(‘file.txt’)lines=f.readlines() #readlines() 存下了f的全部内容for line in lines print line

#3）一次性读取read（）

f = open(‘file.txt’)content = f.read()print contentf.close()

3，文件写入

#write（），writelines（）写文件f = file(‘file.txt’, ‘w+’) #w+读写方式打开，先删除原来的，再写入新的内容line = [“hello n”, “world n”]f.writelines(li)f.close()#追加新内容f = file(‘hello.txt’, ‘a+’)content = “goodbye”f.write( content )f.close()

4，文件删除#需要使用 os 模块和 os.path 模块#os模块的 open（）和 file（）函数和Python内建的用法不同

import osfile(‘hello.txt’, ‘w’)if os.path.exists(‘hello.txt’) os.remove(‘hello.txt’)

5，文件复制

#用read（）和write（）实现拷贝src = file(“hello.txt”, “r”)dst = file(“hello2.txt”,”w”)dst.write( src.read() )src.close()dst.close()#shutil模块 copyfile（）函数#copyfile( src, dst) ＃文件复制shutil.copyfile(“hello.txt”, “hello2.txt”)#move( src, dst) #文件剪切，移动shutil.move(“hello.txt”, “../“) #移动到父目录下shutil.move(“hello2.txt”, “hello3.txt”) #移动＋重命名

6，文件重命名

#修改文件名 os模块的rename（）函数import osos.rename(“hello.txt”, “hi.txt”)#修改后缀名import sfiles = os.listdir(“.”)for filename in files: pos = filename.find(“.”) if filename[ pos+1 :] == “html”: newname = filename[ :pos+1] + “jsp” os.rename( filename, newname)

7，文件内容查找

#文件查找import ref1 = file(“hello.txt”, “r”)count = 0for s in f1.readlines() : li = re.findall(“hello”, s) #findall（）查询变量s，查找结果存到li中 if len( li) >0 : count = count + li.count(“hello”)print count,”hello”f1.close()#文件替换f1 = file(“hello.txt”, “r”)f2 = file(“hello2.txt”, “w”)for s in f1.readlines(): f2.write( s.replace(“hello”, “hi”) )f1.close()f2.close()

8，文件比较#difflib模块用于序列，文件的比较

9，配置文件的访问#Python标准库的ConfigParser模块用语解析配置文件

10，文件和流

#sys模块中提供了stdin，stdout，stderr三种基本流对象import sys#stdin表示流的标准输入sys.stdin = open(“hello.txt”, “r”) #读取文件for line in sys.stdin.readlines() print line#stdout重定向输出，把输出结果保存到文件中sys.stdout = open(r”./hello.txt”, “a”)print “goodbye”sys.stdout.close()