三校聯考 Day3

大水題

題目描述：給出一個圓及圓上的若干個點，問兩個點間的最遠距離。

solution
按極角排序，按順序枚舉，顯然距離最遠的點是單調的，線性時間可解出答案。

大包子的束縛

題目描述：給出一個圓以及直角坐標系上的若干個點，選擇其中的一些點，使得兩兩相連的線段所在的直線與圓無交，求最多可以選多少個點。

solution
這題的題解有點奇怪，總的來說就是……我還不知道怎么做……

毛毛蟲圖

題目描述：定義毛毛蟲圖為一個無向無環圖，且滿足圖中存在一條路徑，使得每個點到這條路徑的距離都小于等于\(1\).毛毛蟲圖不能有重邊，但可以有自環。現給定一個無向圖，并且定義合并操作：每次選定兩個點u, v，將u, v兩點以及所連的邊刪去，再加入一個新點w，將原來和u, v相連的邊改成跟w相連。問至少需要多少次合并操作才能使無向圖變成一個毛毛蟲圖。

solution
首先，這道題具有以下的幾點性質：
1、如果原圖有環，那么需要花費環內點的個數-1次操作把環消除。
2、不連通的塊需要花費1次操作使其和其它的相連
3、由于以上的兩點操作，剩下的點和邊組成一棵無向樹，設取得那條路徑上有\(len\)個點，這棵樹上度數為\(1\)的點有\(s\)個，那么這幅圖最終可以剩下\(len+s-2\)個點，所以這條路徑應該貪心地取樹的直徑。
有了以上的性質，就可以對圖先雙連通縮點，然后求樹的直徑，統計度數為\(1\)的點的個數，就可以算出答案。

自然的神星樹

題目描述：給出一棵樹與\(m\)種水果，給出若干個操作為將數上的一條路徑上的點的某一種水果的數量加\(1\)，求操作完后，每個點那種水果最多。

solution
對于樹上的路徑，可以嘗試用樹鏈剖分來處理，把樹上的點重標號。由樹鏈剖分修改的操作可以得出，可以將一條路徑分成\(logn\)個分別連續的區間，所以總共有\(nlogn\)個區間。按重標號的標號順序進行掃描，建一棵表示當前每種水果有多少個的線段樹，如果當前掃描到的編號\(i\)為某個區間的開頭，就加入線段樹，如果\(i\)為某個區間的結尾，那么就線段樹中刪去。掃描完后映射回原標號就可以得出答案。

轉載于:https://www.cnblogs.com/GerynOhenz/p/5396944.html

總結

以上是生活随笔為你收集整理的三校联考 Day3的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。