談談樹形結構的應用

2021-02-09 15:43 作者:非知名科技區(qū)UP 0人讀過 | 我要投稿

好久不見！有些人一直在問我為什么停更了。這里面的原因一方面是因為我期末確實比較忙。另一方面我也要用一些時間積累一些有難度的題目，提升一下文章的思維含量。讓我們點開上面的音樂，享受今天的內(nèi)容吧！

今天的題來自USACO

Secretpal正在領導奶牛們逃跑。為了聯(lián)絡，奶牛們互相發(fā)送秘密信息。
信息是二進制的，共有 N 條。反間諜能力很強的約翰已經(jīng)部分攔截了這些信息，知道了第 i 條二進制信息的前 bi位。他同時知道，奶牛使用 M 條密碼。但是，他僅僅了解第 j 條密碼的前 cj ?位。

對于M條密碼 j ，他想知道有多少截得的信息能夠和它匹配。也就是說，有多少信息和這條密碼有著相同的前綴。當然，這個前綴長度必須等于密碼和那條信息長度的較小者。

第一行輸入 N 和 M，之后 N 行描述秘密信息，之后 M 行描述密碼．每行先輸入一個整數(shù)表示信息或密碼的長度，之后輸入這個信息或密碼。所有數(shù)字之間都用空格隔開。
共 M 行，輸出每條密碼的匹配信息數(shù)。

示例輸入：

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

對于這樣的題，首先一點就是要讀題。這道題目的本質(zhì)是要求出后面M行中某一行在前N行的前綴總數(shù)和以它為前綴的前M行中信息數(shù)量的合（這句話建議多讀幾遍）。

這樣題目就對我們提出了一個要求：即要統(tǒng)計出指定密碼的前綴數(shù)量，又要到消息里面找出以該密碼為前綴的消息數(shù)量。對于后者，我們可以通過字典樹上面畫一個“線路圖”來解決問題，如下圖所示，橙色的點是代表消息的關鍵點，每當經(jīng)過一個節(jié)點的時候，我們就在該節(jié)點的“l(fā)ine”變量上加一。每當?shù)竭_路徑終點的時候(也就是圖中的橙色點)，則pointgarde++;

UP主個人在做題的時候曾經(jīng)試過這樣一個方法：用N行消息建樹完成后再用后M行的路徑再完善字典樹。然后再用函數(shù)將各個橙色終結點的子樹上各節(jié)點line變量再+1。

如此運算，遞歸是肯定逃不掉了。而眾所周知輸入數(shù)據(jù)的最大位數(shù)是50萬。這樣的情況下最大節(jié)點數(shù)量我估計怎么著也得有個10萬（純屬盲猜，UP畢竟數(shù)學一般）遇上一些比較刁鉆的數(shù)據(jù)，遞歸節(jié)點數(shù)量完全可以達到這個數(shù)值。再乘上輸入數(shù)據(jù)的最大值50000，運算量就是 $10%5E9%20%20$ *5了······

于是乎

通過參考其他巨佬的題解，我得到了一個重要的，避免遞歸的思路。字典樹里“橙色結點”遞歸擴張其實和將密碼插入樹中的時候數(shù)出它經(jīng)過的終結點數(shù)有著一樣的效果，而且后者在針對性上也有大幅的提升。再輸入后M行密碼時只需記住一行的輸入。按照輸入的路徑將密碼插入字典樹，在此期間遇到上圖的橙色節(jié)點就在ans上加上該點的“pointgrade”，密碼插入完成后再讀取一下密碼終點的“l(fā)ine”，ans上加上line即得到答案。

文章最后再提醒一個極其重要的點：我之所以將我的“pointgrade”變量設為int,其原因就在于有些消息是完全重合的。但是如果我們把這些消息看作一個終結點的話就會造成輸出數(shù)據(jù)偏小。最后只能得到一個測試點的分數(shù)。

代碼如下圖：