1 lannister_awalys_pay

尚未进行身份认证

等级
TA的排名 1w+

P1140 相似基因

题目背景大家都知道,基因可以看作一个碱基对序列。它包含了44种核苷酸,简记作A,C,G,TA,C,G,T。生物学家正致力于寻找人类基因的功能,以利用于诊断疾病和发明药物。在一个人类基因工作组的任务中,生物学家研究的是:两个基因的相似程度。因为这个研究对疾病的治疗有着非同寻常的作用。题目描述两个基因的相似度的计算方法如下:对于两个已知基因,例如AGTGATGAGTGATG和GTT...

2019-11-10 12:09:35

Cisco Packet Tracer模拟网络设置与路由器配置

作者:SDUwh计算机合作201700800415CiscoPacketTracer还没有下载的可以通过这个链接https://pan.baidu.com/s/1xm2RDMGjY23iyN5fEsx_4A实验目标,构建出上图所示的网络结构并且分别使用RIP协议和OSPF进行网络互联下面开始模拟现实网络第一步:创建两个主机并连接到交换机并分别打开两个...

2019-11-09 11:56:03

AC自动机

1、概述Aho-Corasick自动机算法(简称AC自动机)1975年产生于贝尔实验室。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。此算法有两个特点,一个是扫描文本时完全不需要回溯,另一个是时间复杂度为O(n),时间复杂度与关键字的数目和长度无关。好了,我们先看下最原始的多模式匹配算法:主串T,n=strlen(T)。模式串Pimi=strlen(pi)[...

2019-10-31 13:57:09

距离向量算法

#include<iostream>#include<algorithm>#include<string>#include<stdio.h>#include<cstring>#include<cctype>#include<cstdio>#include<stack>#...

2019-10-24 23:05:53

P1880 [NOI1995]石子合并

题目描述在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.输入格式数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.输出格式输出共2行,第1行为最小得分,第2行为最大得...

2019-10-23 21:23:45

机器学习对抗性攻击

随着人工智能和机器学习技术在互联网的各个领域的广泛应用,其受攻击的可能性,以及其是否具备强抗打击能力一直是安全界一直关注的。之前关于机器学习模型攻击的探讨常常局限于对训练数据的污染。由于其模型经常趋向于封闭式的部署,该手段在真实的情况中并不实际可行。在GeekPwn2016硅谷分会场上,来自北美工业界和学术界的顶尖安全专家们针对当前流行的图形对象识别、语音识别的场景,为大家揭示了如何通过构造对抗性...

2019-10-10 16:00:17

P1280 尼克的任务

题目描述尼克每天上班之前都连接上英特网,接收他的上司发来的邮件,这些邮件包含了尼克主管的部门当天要完成的全部任务,每个任务由一个开始时刻与一个持续时间构成。尼克的一个工作日为N分钟,从第一分钟开始到第N分钟结束。当尼克到达单位后他就开始干活。如果在同一时刻有多个任务需要完成,尼克可以任选其中的一个来做,而其余的则由他的同事完成,反之如果只有一个任务,则该任务必需由尼克去完成,假如某些任务开...

2019-09-30 09:48:24

P1091 合唱队形

题目描述NN位同学站成一排,音乐老师要请其中的(N−KN−K)位同学出列,使得剩下的KK位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2,…,K1,2,…,K,他们的身高分别为T1,T2,…,TKT1​,T2​,…,TK​,则他们的身高满足T1<...<Ti>Ti+1>…>TK(1≤i≤K)T1​<...<Ti​...

2019-09-29 11:09:49

P1020 导弹拦截(最长上升子序列)

题目描述某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高度数据是≤50000≤50000的正整数),计算这套系统最多能拦截多少导弹,如果...

2019-09-27 11:52:41

P1616 疯狂的采药

题目背景此题为NOIP2005普及组第三题的疯狂版。此题为纪念LiYuxiang而生。题目描述LiYuxiang是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同种类的草药,采每一种都需要一些时间,每一种也有它自身的价值。我会给你一...

2019-09-23 08:25:42

P1049 装箱问题

题目描述有一个箱子容量为VV(正整数,0≤V≤200000≤V≤20000),同时有nn个物品(0<n≤300<n≤30,每个物品有一个体积(正整数)。要求nn个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。输入格式11个整数,表示箱子容量11个整数,表示有nn个物品接下来nn行,分别表示这nn个物品的各自体积输出格式11个整数,表示箱子剩余空间。...

2019-09-20 11:52:48

P1048 采药

题目描述辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,这个山洞里有一些不同的草药,采每一株都需要一些时间,每一株也有它自身的价值。我会给你一段时间,在这段时间里,你可以采到一些草药。如果你是一个聪明的孩子,你应该可以让采到的草药的总价值最大。”如果你是...

2019-09-20 11:17:54

P1064 金明的预算方案

题目描述金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过NN元钱就行”。今天一早,金明就开始做预算了,他把想买的物品分为两类:主件与附件,附件是从属于某个主件的,下表就是一些主件与附件的例子:主件附件电脑打印机,扫描仪书柜图书书桌台灯,文具工...

2019-09-20 10:39:37

第九讲 背包问题问法的变化

以上涉及的各种背包问题都是要求在背包容量(费用)的限制下求可以取到的最大价值,但背包问题还有很多种灵活的问法,在这里值得提一下。但是我认为,只要深入理解了求背包问题最大价值的方法,即使问法变化了,也是不难想出算法的。例如,求解最多可以放多少件物品或者最多可以装满多少背包的空间。这都可以根据具体问题利用前面的方程求出所有状态的值(f数组)之后得到。还有,如果要求的是“总价值最小”“总件数最小...

2019-09-12 11:17:55

第八讲 泛化物品

定义考虑这样一种物品,它并没有固定的费用和价值,而是它的价值随着你分配给它的费用而变化。这就是泛化物品的概念。更严格的定义之。在背包容量为V的背包问题中,泛化物品是一个定义域为0..V中的整数的函数h,当分配给它的费用为v时,能得到的价值就是h(v)。这个定义有一点点抽象,另一种理解是一个泛化物品就是一个数组h[0..V],给它费用v,可得到价值h[V]。一个费用为c价值为w的物品...

2019-09-12 11:17:23

第七讲 有依赖的背包问题

简化的问题这种背包问题的物品间存在某种“依赖”的关系。也就是说,i依赖于j,表示若选物品i,则必须选物品j。为了简化起见,我们先设没有某个物品既依赖于别的物品,又被别的物品所依赖;另外,没有某件物品同时依赖多件物品。算法这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法,将不依赖于别的物品的物品称为“主件”,依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有...

2019-09-12 11:16:50

第六讲 分组的背包问题

问题有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。这些物品被划分为若干组,每组中的物品互相冲突,最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。算法这个问题变成了每组物品有若干种策略:是选择本组的某一件,还是一件都不选。也就是说设f[k][v]表示前k组物品花费费用v能取得的最大权值,则有:f[k][v]=ma...

2019-09-12 11:16:19

第五讲 二维费用的背包问题

问题二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最大值(两种背包容量)分别为V和U。物品的价值为w[i]。算法费用加了一维,只需状态也加一维即可。设f[i]...

2019-09-12 11:15:47

第四讲 混合三种背包问题

问题如果将P01、P02、P03混合起来。也就是说,有的物品只可以取一次(01背包),有的物品可以取无限次(完全背包),有的物品可以取的次数有一个上限(多重背包)。应该怎么求解呢?01背包与完全背包的混合考虑到在P01和P02中给出的伪代码只有一处不同,故如果只有两类物品:一类物品只能取一次,另一类物品可以取无限次,那么只需在对每个物品应用转移方程时,根据物品的类别选用顺序或逆序的循环...

2019-09-12 11:15:12

第三讲 多重背包问题

题目有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。基本算法这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背...

2019-09-12 10:42:36

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。