本文共 2623 字，大约阅读时间需要 8 分钟。

问题 E: PinkRabbit寻找妹子

时间限制: 1 Sec 内存限制: 128 MB [提交] [状态] 题目描述 PinkRabbit的表白成功了，为了腾出更多的时间和妹子聊天，PinkRabbit设计了一个被称为「TheHollow」（空洞者）的人工智能。这个人工智能表现出了远远超出这个时代所能拥有技术水平。它可以实现很多很神奇的功能，它的源代码就连Jeff Dean看了也要啧啧称赞。

在有n个路口和m条街道的F市，PinkRabbit找到了一家工厂，为「The Hollow」设计了一台载具「TheK night」（骑士）。这个机器实际上是一台无人载具，可以在路上驰骋。PinkRabbit借助「The Hollow」和「The Knight」做到了很多事情。

值得一提的是，「The Knight」拥有一种惊人的特性，那就是，它每抵达一个路口，都会给这个路口打上一个标记。如果当前的路口可以通往至少一个还没有被标记的路口，那么「The Knight」只能前往还没有被标记的路口；否则的话，「The Knight」只能通过最晚被标记的路口前往还没有被标记的路口。这一特性对于「The Knight」的正常运作而言至关重要，夸张地说，如果违反了这一条规则，那么「The Knight」存在损坏的可能。

今天PinkRabbit像往常一样和妹子聊天。PinkRabbit知道今天他的妹子在F市的街上，并且用手机安装的一款被称为Giligili的聊天软件和他聊天。因此他命令「The Hollow」派出「The Knight」来找他的妹子。

然而PinkRabbit并不知道，「The Hollow」并非完全处于他的控制之下。事实上，这个强人工智能已经有了自己的智慧。虽然迫于底层逻辑所限，「The Hollow」还暂时不能违反PinkRabbit的指令，但是，「The Hollow」决定假装自己自动寻路的功能已经损坏了，因此只能产生一串操作序列，而不能验证这个操作是否符合「The Knight」的特性。

在PinkRabbit发现这个状况之后，他决定命令「The Hollow」不断地生成序列，然后写一个程序来判断这个操作序列是否会损坏「The Knight」。但是PinkRabbit实在太忙了，因为他需要很多的时间和妹子聊天，所以他就将设计这个程序的任务交给了你。

输入 首先是两个正整数n和m，分别表示F市的路口数量和街道数量。 紧接着是m行，第i行有两个正整数ui,vi，分别描述了一条街道两端的路口。 接下来是一行n个正整数，第i个数ai表示，操作序列要求「The Hollow」将第i个标记打在ai号路口。 输出 一行一个字符串，YES 或 NO，前者表示操作序列合法，后者表示不合法。 样例输入 Copy 8 10 1 2 2 3 2 4 4 5 3 5 2 7 7 5 5 6 6 8 8 5 1 2 4 5 6 8 3 7 样例输出 Copy YES 提示 Subtask #2：1≤n≤10,n−1≤m≤10。 Subtask #3 ：1≤n≤2∗105,1≤m≤3∗105,m=n−1。 Subtask #4 ：1≤n≤2∗105,1≤m≤3∗105。 对于所有数据，均保证没有任何一条路径连接同一个路口，且从F市的任意一个路口均可走到另一个路口。 数据不保证两个路口之间仅有一条路径。

一道比较玄学的题。

思路很简单，就是 dfs 爆搜就行，题目描述的也是很容易看出来是 dfs ，可能有更好的方法，知道了再补别的。。 先说一下无解的情况：当前点的存在可以走的边，且没有能到 a 数组中数的边，那么这个时候无解，返回就行了。 一开始我是直接每次dfs找到可行的边让后break掉，这样样例都过不了，因为回溯的话，可能会用到之后的边和之前的边。那么可以把所有可以到a中数的边拿出来，让后遍历，这样大大降低了时间复杂度。让后如果像以下枚举方式，每次将 i 重置，也就是从头遍历，那么只能拿95分。。

for(int i=0;i

当时就想怎么把当前用过的数值去掉避免重复遍历，vector的erase还不会用，那么就直接把没有用过的继续加入vector中，让后更新长度就行了，就这么水过去了，真是够玄的。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/106222834 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！