谈谈树形结构的应用

2021-02-09 15:43 作者:非知名科技区UP 0人读过 | 我要投稿

好久不见！有些人一直在问我为什么停更了。这里面的原因一方面是因为我期末确实比较忙。另一方面我也要用一些时间积累一些有难度的题目，提升一下文章的思维含量。让我们点开上面的音乐，享受今天的内容吧！

今天的题来自USACO

Secretpal正在领导奶牛们逃跑。为了联络，奶牛们互相发送秘密信息。
信息是二进制的，共有 N 条。反间谍能力很强的约翰已经部分拦截了这些信息，知道了第 i 条二进制信息的前 bi位。他同时知道，奶牛使用 M 条密码。但是，他仅仅了解第 j 条密码的前 cj 位。

对于M条密码 j ，他想知道有多少截得的信息能够和它匹配。也就是说，有多少信息和这条密码有着相同的前缀。当然，这个前缀长度必须等于密码和那条信息长度的较小者。

第一行输入 N 和 M，之后 N 行描述秘密信息，之后 M 行描述密码．每行先输入一个整数表示信息或密码的长度，之后输入这个信息或密码。所有数字之间都用空格隔开。
共 M 行，输出每条密码的匹配信息数。

示例输入：

4 5
3 0 1 0
1 1
3 1 0 0
3 1 1 0
1 0
1 1
2 0 1
5 0 1 0 0 1
2 1 1

示例输出：

1
3
1
1
2

答案链接如下，各位请在思考完成后浏览一下这个程序，然后再看解析。

http://124.205.120.153/blog/dingzhaoyu/blog/1333

对于这样的题，首先一点就是要读题。这道题目的本质是要求出后面M行中某一行在前N行的前缀总数和以它为前缀的前M行中信息数量的合（这句话建议多读几遍）。

这样题目就对我们提出了一个要求：即要统计出指定密码的前缀数量，又要到消息里面找出以该密码为前缀的消息数量。对于后者，我们可以通过字典树上面画一个“线路图”来解决问题，如下图所示，橙色的点是代表消息的关键点，每当经过一个节点的时候，我们就在该节点的“line”变量上加一。每当到达路径终点的时候(也就是图中的橙色点)，则pointgarde++;

UP主个人在做题的时候曾经试过这样一个方法：用N行消息建树完成后再用后M行的路径再完善字典树。然后再用函数将各个橙色终结点的子树上各节点line变量再+1。

如此运算，递归是肯定逃不掉了。而众所周知输入数据的最大位数是50万。这样的情况下最大节点数量我估计怎么着也得有个10万（纯属盲猜，UP毕竟数学一般）遇上一些比较刁钻的数据，递归节点数量完全可以达到这个数值。再乘上输入数据的最大值50000，运算量就是 $10%5E9%20%20$ *5了······

于是乎

通过参考其他巨佬的题解，我得到了一个重要的，避免递归的思路。字典树里“橙色结点”递归扩张其实和将密码插入树中的时候数出它经过的终结点数有着一样的效果，而且后者在针对性上也有大幅的提升。再输入后M行密码时只需记住一行的输入。按照输入的路径将密码插入字典树，在此期间遇到上图的橙色节点就在ans上加上该点的“pointgrade”，密码插入完成后再读取一下密码终点的“line”，ans上加上line即得到答案。

文章最后再提醒一个极其重要的点：我之所以将我的“pointgrade”变量设为int,其原因就在于有些消息是完全重合的。但是如果我们把这些消息看作一个终结点的话就会造成输出数据偏小。最后只能得到一个测试点的分数。

代码如下图：