# TPOJ Round #5 Editorial
###### tags: `Editorial`
## pA. Sleeping Patterns
根據題意，只需要檢查「$\ h2:m2$是否**不**介於 $\ h3:m3$ 和 $\ h4:m4$」及「$\ h4:m4$是否**不**介於 $\ h1:m1$ 和 $\ h2:m2$」即可。一個比較好的實作方式是將所有時間都換成分鐘數，這樣就可以使用整數判斷了。

## pB. Logarithm Game
應該不難想到以下的 Greedy 解：一直選擇加 $\ 1$ ，一旦遇到二個幂次就把它取對數。
幸運的是，這個解法就是對的！以下將證明這是最佳策略：
我們將所有除了 $\ 1$ 以外的正整數分成 $\ [2^0+1,2^1],[2^1+1,2^2], [2^2+1,2^3],[2^3+1,2^4]...$ 這些區塊。令 $\ b_k$ 代表區間$\ [2^{k}+1,2^{k+1}]$。我們對每個 $\ k$ 進行討論：
* 當 $\ k=0$ 時，$\ b_0$ 內只有一個整數 $\ 2$ 。顯然最佳的策略就是取 $\ log$ 一次。
* 討論當 $\ k=t$ 的情形。注意到我們的策略就是將 $\ b_{t}$ 內的所有數字加到 $\ 2^{t+1}$ 以後，然後取對數。注意到 $\ t+1 \leq \frac{2^{t+1}}{2}$，因此每個數字都只會被碰到一次，也就是操作次數不會超過 $\ 2^{t+1}$ 次。如果加到 $\ 2^{t+2},2^{t+3}...$ 再取 $\ log$ ，這樣的操作次數至少就是 $\ 2^{t+2}-2^{t+1} = 2^{t+1}$ 次，並不是最優策略。

Note: 延伸題目: 如果加 $\ 1$ 和取 $\ \log$ 不同權重?

## pC. Edit Distance of Two Multisets

我們首先討論 $\ n=m$ 的情形。
令 $\ occx_i$ 代表 $\ S$ 中 $\ i$ 的出現次數， $\ occy_i$ 代表 $\ T$ 中 $\ i$ 的出現次數。我們計算以下兩個總和：
* $\ pos= \sum\limits_{occy_i>occx_i} occy_i-occx_i$
* $\ neg= \sum\limits_{occx_i>occy_i} occx_i-occy_i$

如果我們只能執行取代，那答案顯然是 $\ c \cdot pos$ (注意到在 $\ n=m$ 下 $\ pos=neg$ ) 。令 $f_1,f_2,f_3$ 分別代表最優策略下添加、刪除、取代的操作次數。注意到 $\ f_1 = f_2$ ，所以我們可以枚舉 $\ f_1$ 的執行次數，就可以用 $\ pos$ 算出 $\ f_3$ 的執行次數，那答案就是所有 $\ f_1 \cdot (a+b) + f_3 \cdot c$ 的最小值。但是注意到 $\ f_1$ 最佳解時一定是 $\ 0$ 或 $\ pos$ ，因此答案又可以寫成 $\ \min(a+b,c) \cdot pos$ 。

當 $\ n>m$ 時，顯然我們一定要執行至少 $\ n-m$ 次刪除操作， 然後就可以變成 $\ n=m$ 的情形了。當刪除時，我們可以永遠刪除 $\ occx_i>occy_i$ 數字 $\ i$，使得當 $\ n=m$ 時還需要 $\ neg$ 的花費，因此最少操作花費為 $\ b \cdot (n-m) + \min(a+b,c) \cdot neg$ 。我們可以類似的手法討論 $\ n<m$ 的情形。

結論：
* 當 $\ n=m$ 時，答案是 $\\min(a+b,c) \cdot pos$ .
* 當 $\ n>m$ 時，答案是 $\ b \cdot (n-m) +\min(a+b,c) \cdot neg$ .
* 當 $\ n<m$ 時，答案是 $\ a \cdot (m-n) + \min(a+b,c) \cdot pos$ .

Note: 延伸題目: 如果 $\ S,T$ 都可以修改?

## pD. Tree Relabeling

首先先找出原本的樹的樹直徑。顯然，這棵樹的樹直徑一定也是編號後的樹直徑。接下來的問題就變成，給定兩個正整數 $\ n,k$ ，找出一個長度為 $\ k+1$ 的序列使得每個整數都介於 $\ 1$ 到 $\ n$ 之間且不重複，並且 $\ \sum\limits_{i=1}^k |a_i-a_{i+1}|$ 達到最大值。

$\ k$ 個絕對值的總和可以表示成 $k$ 個被減數的總和減去 $k$ 個減數的總和。其中每個整數最多被使用兩次。底下使用紅色的點代表被減數，綠色的點代表減數。我們將 $k$ 分奇偶討論。

1. $k$ 是奇數：

達到最大值時一定是這種情形(畫有點醜請見諒><)：
我們也可以確實找到一種滿足這個最大值的編號方式：6 -> n-5 5 -> n-4 -> 3 -> ... -> 1 -> n 。

2. $k$ 是偶數：

達到最大值時是這種情形：
但是我們找不到一個滿足這個最大值的編號方式。於是我們退而求其次減 $1$ ：
這個就有一種編號方式了： n-4 -> 5 -> n-3 -> 4 -> n-2 -> 3 -> ... -> 1 -> n-5 。

把在樹直徑上的編號確定後，剩下的編號隨意填就是了。

Note: 延伸題目: 如果把這題最大改成最小?(我其實也不會XD)

## pE. Palindromic Substrings

注意到在這個字串中，任意一個回文長度都是奇數。另外也注意到字串中最大的字母只出現一次。綜合以上我們枚舉回文的中心，嘗試使用以下 D&C 算法來計算回文數量：

* 令字串 $\ s_l ... s_r$ 中位置 $\ x$ 的字母是最大的，遞迴計算 $\ s_l ... s_{x-1}$ 及 $\ s_{x+1} ... s_{r}$ 的回文數量。
* 把上面的兩個值加起來，再加上 $\ \min(x-l+1,r-x+1)$ 就是答案了。

以上算法是正確的，但是時間複雜度是 $\ O(n)$ 。但是透過 DP 預處理長度為 $\ 1,2,4,8,...$ 的回文數量，就可以將複雜度降為 $\ O(\lg n)$ 。實作可以參考程式碼：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll mod=1e9+7;
#define int ll

int dp[45],L,t,R;

int solve(int l,int r,int ql,int qr)
{
    if (r<ql||l>qr) return 0;
    else if (l>=ql&&r<=qr) return dp[__lg(r-l+2)-1];
    int m=(l+r)>>1;
    int ret=(m>=ql&&m<=qr ? min(qr-m+1,m-ql+1) : 0);
    return (ret+solve(l,m-1,ql,qr)+solve(m+1,r,ql,qr))%mod;
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    dp[0]=1;
    for (int i=1;i<=40;i++)
        dp[i]=(2*dp[i-1]+(1ll<<i))%mod;
    cin>>t;
    while (t--)
    {
        cin>>L>>R;
        cout<<solve(1,(1<<26)-1,L,R)<<'\n';
    }
}

Note 1: 這題是受到 CatAgain 出的題目啟發的: http://csdc.tw/contest/5/problem/13/
Note 2: 這題是這六題我最喜歡的題目 ><
Note 3: 延伸題目: 如果可以修改字串?

## pF. Cycle Queries

首先注意到，「$\ x,y$間有一個環穿過」相當於 $\ x,y$ 在同一團 BCC 中。所以現在問題變成怎麼維護一張圖中 BCC 的資訊。

注意到在一張圖中，BCC縮點後會成為一棵樹。而在 $\ x,y$ 間加邊就相當於縮點後將 $\ x,y$ 代表的點的路徑全部縮為一團 BCC 。於是解法就出現了：我們可以使用 DSU 維護每團BCC的資訊！詳細作法如下：

* 找出原圖的一顆生成樹。
* 每團 BCC 紀錄編號大小、最小的點、第二小的點、子樹頂端(因為每團BCC都是生成樹的一顆子樹)。
* 當加上一條邊 $\ (x,y)$ 後，把 $\ x$ 到 $\ lca(x,y)$ 和 $\ y$ 到 $\ lca(x,y)$ 合併為同一團。我們可以使用類似 LCA 的寫法：把 $x$ 和 $y$ 提到那團的頂端後，看兩者是否相同；如果不同，把比較低的那個跳一個節點上去。
* 當詢問時，如果該團大小為 $1$ 輸出 $-1$ ；如果詢問點為該團 DSU 最小的，輸出第二小的節點；否則輸出最小的節點。

Note1: 這題的解法可以拿來解CF的這題: https://codeforces.com/gym/100551/problem/B
(雖然那場是時間線段樹的Round就是了XD)
Note2: 延伸題目: 如果可以拔邊?