您好、欢迎来到现金彩票网!
当前位置:秒速快三开奖 > 双连通度 >

hdu4511---小明系列故事——女友的考验(AC自动机+dp)

发布时间:2019-05-20 11:45 来源:未知 编辑:admin

  终于放寒假了,小明要和女朋友一起去看电影。这天,女朋友想给小明一个考验,在小明正准备出发的时候,女朋友告诉他,她在电影院等他,小明过来的路线必须满足给定的规则:

  1、假设小明在的位置是1号点,女朋友在的位置是n号点,则他们之间有n-2个点可以走,小明每次走的时候只能走到比当前所在点编号大的位置;

  2、小明来的时候不能按一定的顺序经过某些地方。比如,如果女朋友告诉小明不能经过1 - 2 - 3,那么就要求小明来的时候走过的路径不能包含有1 - 2 - 3这部分,但是1 - 3 或者1 - 2都是可以的,这样的限制路径可能有多条。

  特别说明,如果1 2 3这三个点共线继续,那么此种情况是不认为小明经过了2这个点的。

  现在,小明即想走最短的路尽快见到女朋友,又不想打破女朋友的规定,你能帮助小明解决这个问题吗?

  输入包含多组样例,每组样例首先包含两个整数n和m,其中n代表有n个点,小明在1号点,女朋友在n号点,m代表小明的女朋友有m个要求;

  接下来n行每行输入2个整数x 和y(x和y均在int范围),代表这n个点的位置(点的编号从1到n);

  再接着是m个要求,每个要求2行,首先一行是一个k,表示这个要求和k个点有关,然后是顺序给出的k个点编号,代表小明不能走k1 - k2 - k3 ……- ki这个顺序的路径;

  对于每个样例,如果存在满足要求的最短路径,请输出这个最短路径,结果保留两位小数;否则,请输出”Can not be reached!” (引号不用输出)。

  告诉你某些路径不能存在,这是个很明显的提示,就是个自动机dp,dp[i][j]表示在自动机节点i,并且在点j时的最短路径,一开始我的循环方式可能不对,后来换了下就可以了,注意坐标还是直接用double 读入吧

  Description终于放寒假了,小明要和女朋友一起去看电影。这天,女朋友想给小明一个考验,在小明正准备出发的时候,女朋友告诉他,她在电影院等他,小明过来的路线必须满足给定的规则: 1、假设...博文来自:那些年

  题目链接:Clickhere~~题意:中文题。抽象问题:给一个有向无环图,问从1号点到n号点的最短路径,路径中不能包含某些子串。解题思路:其实也不算难,如果能从“不能包含某些子串”联想到AC自动机,这...博文来自:nyist_xiaod

  题意:给你n个点,你在1号点,要到n号点,有m种路径不能走,求1到n的最短路长度。思路:m种路径不能走,很容易想到AC自动机。求距离最短。还是将m种路径建立成自动机, 一个结点非法,不仅他是m种路径的...博文来自:aozil_yang的博客

  限制条件用AC自动机找出合法状态但是这题的DP并不是矩阵加速的那种,转移需要涉及到实际点所以定义dp[i][j]:当前点为i,状态为j的最小路程,枚举点转移顺带一提,枚举转移是n^2*自动机size,...博文来自:Master.Yi的博客

  hdu4511题目中文题目思路AC自动机好久以前看的了,都要忘了。。。。正好复习以下。dp[i][j]表示在i点,状态在j的距离,转移比i大的点k,判断下一个状态ss是否可行,可行则转移到dp[k][...博文来自:天道酬勤

  题意:终于放寒假了,小明要和女朋友一起去看电影。这天,女朋友想给小明一个考验,在小明正准备出发的时候,女朋友告诉他,她在电影院等他,小明过来的路线号...博文来自:Ezereal的博客

  ProblemDescription终于放寒假了,小明要和女朋友一起去看电影。这天,女朋友想给小明一个考验,在小明正准备出发的时候,女朋友告诉他,她在电影院等他,小明过来的路线必须满足给定的规则:...博文来自:Tisuama

  AC自动机首先是一个多模式匹配算法,简单来说就是有多个模式串,然后查询的结果就是被查询串中有多少个模式串。模式串之间可以互相重叠。实际上,AC自动机就是在一颗Trie树上添加了一fail指针,这个指针...博文来自:limn204的专栏

  第一道AC自动机上的dp题意是给出一些字符串,求长为m的字符串包含这些的一共有多少个,字符集A-Z首先运用补集转换,转而求不含这些串的个数,最后用26^M减掉就行根据输入的字符串建立AC自动机dp[i...博文来自:thchuan2001的博客

  题意:题目链接:给出m个单词,要构造出长度为2*L的包含这全部m个单词的字符串,并且保证这个字符串非对称,其...博文来自:Bahuia的博客

  有些时候,我们会碰到这样的一类问题:给定n个字符串,求长度为m的(不)包含这n个字符串的字符串个数。即字符串匹配的计数问题。我们先来看这样一道题:【poj2778】给出m个疾病基因片段(ma...博文来自:C20181503csy的博客

  题目描述终于放寒假了,小明要和女朋友一起去看电影。这天,女朋友想给小明一个考验,在小明正准备出发的时候,女朋友告诉他,她在电影院等他,小明过来的路线必须满足给定的规则: 1、假设小明在的位置是...博文来自:Tomcat的Tom

  题目链接(第十届四川省赛C题) 挺好的一道题,就是要做一个last优化,每次的last要返回到之前的有值节点,也就是单词的尾的对应节点,然后就不会超时了……呜呜呜,之前一直超时,以为是初始化的mems...博文来自:既然弱小,就只顾变强就是了

  首先简要介绍一下AC自动机:Aho-Corasickautomation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让...博文来自:西红柿爱炒番茄

  自动机是一种用于解决多模式串匹配问题的工具。模板题:给定个模式串和个母串(由小写字母组成),将母串中包含模式串的部分变为号。判断一个串是不是另一个串的子串,我们首先会想到算法,但算法需要逐个处理每一个...博文来自:pig_dog_baby的博客

  其实就是求1到n的最短路,且不包含特定子串,可以利用ac自动机构建不可到达的状态我们可以设dp【i】【j】来表示到达i节点时候位于自动机j节点的花费ACcode:#includeconstdouble...博文来自:MY Blog

  题目链接:点击打开链接AC自动机上的最短路问题,题目要求所经过结点升序,且规定某些线路是不合法的,对应于AC自动机上的非法状态。这道题目大部分题解是用DP来做的,而我是用Dijstra变形来解决这个题...博文来自:的博客

  题解:将字符串都放在AC自动机上然后看一下到达每个位置能增加多少权值,最后转移的时候跟根据权值大小,字典序大小更新一下即可.dp一维表示长度,二维表示到达哪个结点,一开始把所有的结点初始化成-表示不可...博文来自:Soul

  题意Alice有n个字符串S_1,S_2…S_n,Bob有一个字符串集合T,一开始集合是空的。接下来会发生q个操作,操作有两种形式:“1P”,Bob往自己的集合里添加了一个字符串P。“2x”,Alic...博文来自:beginend

  题目大意:给一些字母串,问长度为L【以内】的全部字母串中,有多少个字母串,【包含】给定的字母串。答案mod2^64首先,对于答案mod2^64,只要全部使用unsignedlonglong进行运算,就...博文来自:ACMer不要报考高校代码为13627的移通学院!

  前言KMP是一个经典的字符串匹配算法。然后AC自动机是基于KMP思想的一个多模板匹配算法。trie图是AC自动机的一个优化。fail树是AC自动机中fail指针构成的有特殊性质的树。KMP算法算法原理...博文来自:少主大人殿下的博客

  在用BFS的时候可访问的点要用四个状态去记录,0代表一个都没找到,1代表找到了大明,2代表找到了二明,3代表都找到。因为在BFS的过程中访问各节点时,因为访问时的状态不同,所以过程中包含有回路。我的代...博文来自:Neutralzz的博客

  fail树定义把所有fail指针逆向,这样就得到了一棵树(因为每个节点的出度都为1,所以逆向后每个节点入度为1,所以得到的是一棵树)还账…有了这个东西,我们可以做很多事…对于AC自动机的构造前面的文章...博文来自:在思索中前行!

  点击打开链接这个题让我发现了我的一个缺点就是看见搜索题走不动真心想ac因为我自己的bfsdfs自我感觉学的还可以然后就一直wa这道题最后和我学长交流的时候我才知道这个题没那么简单因为这个搜索并不是搜过...博文来自:的博客

  ProblemDescription小明的妈妈生了三个孩子,老大叫大明,老二叫二明,老三…,老三自然就叫小明了。一天,小明的妈妈带小明兄弟三人去公园玩耍,公园里面树木很多,有很多地方可以藏身,于...博文来自:riba2534的博客

  分析:巨恶心的一题双代码题。对于前半部分,把禁止出现的字符串建一颗AC自动机。然后枚举每个位置用了某个模板串后转移到哪里。然后直接DP即可。但是对于后半部分数据,则必须写一个矩阵加速。。。因为模板串长...博文来自:氧化钠的博客

  解题思路:题目要求至少含有一个单词的方案数,可以转化成总方案数(26m26^m)减去不含有单词的方案数。接下来把单词插到AC自动机上进行dp。f[i][j]表示走到AC自动机的j号结点当前单词长度为i...博文来自:cdsszjj的博客

  小明系列故事——捉迷藏小明的妈妈生了三个孩子,老大叫大明,老二叫二明,老三...,老三自然就叫小明了。一天,小明的妈妈带小明兄弟三人去公园玩耍,公园里面树木很多,有很多地方可以藏身,于是他们决定...博文来自:YOONGI

  这个题还是比较好想的。首先将所有不可行方案建立AC自动机,然后跑最短路。首先将小明放在(sta=0,pos=0)处,sta表示AC自动机上点的编号,pos表示坐标点的编号。根据pos枚举下一次可以到达...博文来自:自在飞花

  链接:做这道题首先要对ac自动机理解透彻!!蛮好的一道题目,每一天字符串除了会在尾部扩展一个,开头的字符还会...博文来自:努力奋斗才能梦想成真

  给n个字母,构成长度为m的串,总共有n^m种。给p个字符串,问n^m种字符串中不包含(不是子串)这p个字符串的个数。将p个不能包含的字符串建立AC自动机,每个结点用val值来标记以当前节点为后缀的字符...博文来自:的博客

  Description最终放寒假了,小明要和女朋友一起去看电影。这天,女朋友想给小明一个考验,在小明正准备出发的时候。女朋友告诉他。她在电影院等他,小明过来的路线必须满足给定的规则: 1、如果...博文来自:weixin_33676492的博客

  题目链接:Clickhere~~题意:给m个带权值的串,构造一个长度为n的串,使总串的权值和最大,并输出字典序最小的方案。解题思路:令dp[i][j]表示长度为i,位于自动机节点j所能构成的最大权值。...博文来自:nyist_xiaod

  题目链接:点击这里题意:给出n个01串,要构造一个最长的串使得这个串不包含所有出现过的串,无解输出-1.首先把所有的点扔进自动机,因为出现过的串不能在我们构造的串中出现,所以事先把某些”坏点”标记,坏...博文来自:morejarphone~

  在没学ac自动机之前,觉得ac自动机是个很神奇,很高深,很难的算法,学完之后发现,ac自动机确实很神奇,很高深,但是却并不难。我说ac自动机很神奇,在于这个算法中失配指针的妙处(好比kmp算法中的ne...博文来自:creatorx的博客

  AC自动机总结0.引言:   由于大连现场赛的一道AC自动机+DP的题目(zoj3545RescuetheRabbit)被小媛同学推荐看AC自动机。经过一段时间的努力,终于把shǎ崽神牛的AC自动机专...博文来自:小白菜又菜

  因为公司有个项目有webapp的需求,在前期准备的期间考虑过使用ionic,毕竟该项目web端的框架使用的是Angular,项目组的人也都比较熟悉,但是我们毕竟只是做个移动的网页,不想用ionic那么...博文来自:zhangl的博客

  Arduino环境下开发NodeMCU(ESP8266)   以前用过ESP8266,只是一些简单的应用。将ESP8266与单片机相连,使用AT指令进行串口通信,从而达到发送信息、接收信息一些目...博文来自:Little_Body的博客

  用以前以前写过的自定义课表软件 ,Android 自定义View课程表表格 原生View截图合成分享的图片 看到的是图片只显示到11节处,下面的没有...博文来自:ShallCheek

  上一篇博客介绍了如何解决Fragment重叠的问题,有需要的同学可以看一下,底部有demo下载。 直通车:完美解决Fragment重叠本篇博客我们来说一下怎么让fragment重新加载布局资源文件。...博文来自:喻志强的博客

  最近比较有空,大四出来实习几个月了,作为实习狗的我,被叫去研究Docker了,汗汗! Docker的三大核心概念:镜像、容器、仓库 镜像:类似虚拟机的镜像、用俗话说就是安装文件。 容器:类似一个轻量...博文来自:我走小路的博客

  卷积的概念       线性滤波可以说是图像处理最基本的方法,它可以允许我们对图像进行处理,产生很多不同的效果。做法很简单。首先,我们有一个二维的滤波器矩阵和一个要处理的二维图像。然后,对于图像的每一...博文来自:HAHA的专栏

  tableView中添加按钮触发不了点击事件的解决办法博文来自:CN_DS的博客

  公司产品之前使用xmpp作为底层库,之前同事编译自己的sdk静态库想生成.a库,但是各种编译问题(其实耐心修改配置都能解决),但是从百度找到方案用framework可以解决,所以最终使用的是frame...博文来自:mingming24的专栏

  java.lang.NoClassDefFoundError错误产生的原因: NoClassDefFoundError错误产生的原因是:JVM在编译的时候能找到调用方法或静态变量所在的类,但在运行的时...博文来自:追着梦跑的博客

  扫二维码关注,获取更多技术分享 本文承接之前发布的博客《 微信支付V3微信公众号支付PHP教程/thinkPHP5公众号支付》必须阅读上篇文章后才可以阅读这篇文章。由于最近一段时间工作比较忙,...博文来自:Marswill

  花了几天,终于把matlab版的人脸检测运行成功了,虽然正确率不是很高,看着各种论文上的人脸检测正确率都出奇的高,我是不怎么相信的,有的论文连基于平均脸的人脸检测正确率都能达到98%,汗啊~~  也许...博文来自:海海人生

  阅读内容为:FX系列微型可编程控制器用户手册(通讯篇)中计算机链接功能章节。 采用本方法通信,pc端的实现,其实就是,把操作按照协议(2种)翻译成相应的字符串,通过串口发送给plc。 编写一应用程...博文来自:pengjc2001的博客

  强连通分量: 简言之 就是找环(每条边只走一次,两两可达) 孤立的一个点也是一个连通分量   使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点)   定义: int Ti...博文来自:九野的博客

  jquery/js实现一个网页同时调用多个倒计时(最新的) 最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦! //js ...博文来自:Websites

  前言:       博主在自主学习粒子滤波的过程中,看了很多文献或博客,不知道是看文献时粗心大意还是悟性太低,看着那么多公式,总是无法把握住粒子滤波的思路,也无法将理论和实践对应起来。比如:理论推导过...博文来自:知行合一

  自己整理编写的逻辑回归模板,作为学习笔记记录分享。数据集用的是14个自变量Xi,一个因变量Y的australian数据集。 1. 测试集和训练集3、7分组 australian ...博文来自:Tiaaaaa的博客

http://cellmall.net/shuangliantongdu/57.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有